TAREA 1 FUNDAMENTACIÓN

MISHELL KARINA ROJAS MONTEALEGRE

CODIGO: 1010142031

  
z
UNIVERSIDAD NACIONAL ABIERTA Y A
DISTANCIA UNAD

301405_19, AUTOMATAS Y LENGUAJES

FORMALES

VERMEN RAINER AYALA

07 DE SEPTIEMBRE DEL 2020

 z EJERCICIOS A DESARROLLAR

 Ejercicio 1: Realizar una línea del tiempo que permita observar la historia y evolución de la
teoría de autómatas y lenguajes formales, se debe tener en cuenta los orígenes, los precursores y
los distintos campos en los que repercute esta área del conocimiento (Ingeniería, lenguajes y 2
gramáticas, matemáticas y computabilidad) y directa de las ciencias computacionales.
z
z
 z
EJERCICIO 2: REALIZAR LA PRESENTACIÓN CON LA
CONCEPTUALIZACIÓN Y EJEMPLOS DE:

 ALFABETO: Es un conjunto finito de símbolos, no vacio. Para definir que un

símbolo a pertenece a un alfabeto V se utiliza la notación a Î V. Los alfabetos se
definen por enumeración de los símbolos que contienen, así por ejemplo se
presentan a continuación varios alfabetos.
 Ejemplo:

 V1 = { A , B , C , D , E , F, G , H , . . . , X , Y ,Z }
 V2 = { a , b , c , d , 0 , 1 , 2 , 3 , 4 , * , # , + } V3 = { 0 , 1 }
 V4 = {if, then, begin, end, else, a, b, ; , =, > }
También se puede definir las tablas ASCII y EBCDIC como los
alfabetos de distintos ordenadores.
 z
PALABRA O CADENA

 Palabra o Cadena: Una cadena es una secuencia finita de símbolos de un

determinado alfabeto.
 Ejemplo:

Se utilizan los vocabularios de los ejemplos del epígrafe 2.2.1.

abcb es una cadena del alfabeto V2 a+2*b es una

cadena del alfabeto V2 000111 es una cadena del
alfabeto V3
if a>b then b=a; es una cadena del alfabeto V4
 z
LENGUAJE

Lenguaje: Se denomina lenguaje sobre un alfabeto V a un subconjunto del universo del discurso. También se puede definir como un
conjunto de palabras de un determinado alfabeto. Alguien puede pensar que los lenguajes se pueden definir porenumeración de las
cadenas que pertenecen a dicho lenguaje, pero este método además de ineficiente, es en muchos casos imposible (habitualmente un
lenguaje tiene infinitas cadenas). Así los lenguajes se definen por las propiedades que cumplen las cadenas del lenguaje.
Ejemplo:

El conjunto de palíndromos (cadenas que se leen igual hacia adelante, que hacia atrás) sobre el alfabeto {0,1}. Evidentemente este
lenguaje tiene infinitas cadenas.
Algunas cadenas de este lenguaje son:
l
0
1
00
11
010
0110
000000
101101
111111
 z
LENGUAJE REGULAR

 en la jerarquía de Chomsky se refiere a los lenguajes de tipo 3, aquellos que

pueden representarse mediante gramáticas regulares, autómatas
finitos o expresiones regulares.
 Ejemplo:
 z
EXPRESIÓN REGULAR

 Las expresiones regulares están estrechamente relacionadas con los autómatas finitos no
deterministas y pueden considerarse una alternativa, que el usuario puede comprender
fácilmente, a la notación de los AFN para describir componentes de software. Por tanto, las
expresiones regulares sirven como lenguaje de entrada de muchos sistemas que procesan
cadenas.
 Ejemplo: Encuentra la expresión regular para el conjunto de cadenas de 0’s y 1’s tal que cada
par de 0’s adyacentes aparece antes de cualquier par de 1’s adyacentes.
Solución:
(10 + 0) ∗ (ε + 1)(01 + 1) ∗ (ε + 1)
(10 + 0) ∗ (ε + 1) es el conjunto de cadenas que no tienen dos 1’s adyacentes. La segunda parte es
el conjunto de cadenas que no tienen dos 0’s adyacentes. De hecho ε + 1 lo podríamos  eliminar
porque se puede obtener el 1 de lo que sigue, por lo que podemos simplificarlo a: (10 + 0) ∗ (01 +
1) ∗ (ε + 1).
 z
EXPRESIÓN DE CONJUNTO POR EXTENSIÓN

 En Teoría de Conjuntos se definen los conjunto por extensión como aquellos

conjuntos cuya notación indica cada uno de los elementos que los componen.
 Ejemplo:

 A = {a, e, i, o, u} es un conjunto en el que se indican todos sus elementos, por lo

tanto se trata de un conjunto por extensión.
 A = {2, 4, 6, 8, 10} es un conjunto en el que se indican todos sus elementos, por lo
tanto es un conjunto por extensión
 z
EXPRESIÓN DE CONJUNTO POR INTENCIÓN

 Construir o definir un conjunto por intención consiste en declarar cuáles

elementos de un cierto conjunto son seleccionados. Esto se lleva a cabo por una
propiedad o predicado P(x).
{x ∈ D|P(x)}
 Ejemplo:

{x ∈ R| − 2 < x}
“Todos aquellos números reales que son mayores que -2.”
 z
PALABRA NULA O VACÍA ʎ

 La palabra que no contiene símbolos. λ no ϵ ∑

 Ejemplo:
 z
OPERACIÓN REGULARES - UNIÓN

 La unión de dos lenguajes regulares es otro lenguaje regular. Se utiliza la operación de unión de
conjuntos; así, para el alfabeto S ={x,y} si L1 = {x,xy} y L2 = {yz,yy} entonces su unión será
L1 È L2 = {x,xy,yz,yy }.
Para modificar los diagramas de transiciones deberemos conseguir que se vaya a una u otra de las
estructuras originales, pero sin mezclarlas (si se mezclan, se admitirían cadenas que no pertenecen al
lenguaje). Para ello cogeremos los diagramas originales de los dos lenguajes. Se dibuja un estado
nuevo:
a. Será el nuevo estado inicial

b. Será de aceptación si alguno de los estados iniciales de los diagramas originales lo era

c. Por cada uno de los arcos que hay desde los estados iniciales originales hacia otros (puede ser el
mismo), se dibuja desde el nuevo estado inicial un arco hacia el estado destino del arco
correspondiente en el diagrama original y se etiqueta con el mismo símbolo
d. A continuación se elimina la característica de inicio de los estados iniciales originales
 z
OPERACIÓN REGULARES - UNIÓN
 Ejemplo:

Para diseñar el autómata finito que admite el lenguaje unión aplicamos:

• Dibujamos un estado nuevo que va a ser el nuevo estado inicial y
será de aceptación si alguno de los estados iniciales de los
diagramas originales lo era.
En nuestro caso el segundo diagrama original tiene un estado inicial
que es de aceptación, con lo cual también lo será el nuevo estado.
• Por cada uno de los arcos que hay desde los estados iniciales
originales hacia otros (puede ser el mismo), se dibuja desde el
nuevo estado inicial un arco hacia el estado destino del arco
correspondiente en el diagrama original y se etiqueta con el mismo
símbolo.
• A continuación se elimina la característica de inicio de los estados
iniciales originales.
 z
OPERACIÓN REGULARES - CONCATENACIÓN

 La concatenación de dos lenguajes regulares es otro lenguaje regular. Se concatenan

una cadena del primer lenguaje y una cadena del segundo. Con L 1 y L2 anteriores la
concatenación (que se denota °) será L1 ° L2 ={xyx,xyy,xyyz,xyyy}. La concatenación
no es conmutativa (L1 ° L2 ¹ L2 ° L1 ).
 Cogemos los diagramas originales de los dos lenguajes:
a. Se dibuja el diagrama original de L1

b. desde cada estado de aceptación del diagrama de L 1 se dibuja un arco hacia cada estado
de L2 que sea el destino de un arco del estado inicial de L 2 y se rotula con el mismo
símbolo
c. Dejar que los estados de aceptación de L 1 lo sean si el estado inicial de L2 también lo es.
 z
OPERACIÓN REGULARES - CONCATENACIÓN

 Ejemplo:

Para diseñar el autómata finito que admite el lenguaje

concatenación aplicamos:

• Se dibuja el diagrama original de L1

• desde cada estado de aceptación del diagrama de L 1 se dibuja un

arco hacia cada estado de L2 que sea el destino de un arco del
estado inicial de L2 y se rotula con el mismo símbolo

• Dejar que los estados de aceptación de L1 lo sean si el estado

inicial de L2 también lo es. Este es el caso del ejemplo, en caso
contrario se debería eliminar esta característica de todos los
estados de aceptación de L1.
 z
OPERACIÓN REGULARES - ESTRELLA DE KLEENE

La estrella de Kleene de cualquier lenguaje regular también es regular. Se caracteriza por que se utiliza solo un lenguaje en
lugar de dos. Se logra formando todas las concatenaciones de cero (cadena vacía) o más cadenas del lenguaje que se amplía.
La operación se representa con el asterisco supraíndice ( * ).
Como se vio al principio de este apartado, la cadena vacía, l, no se consideraba como uno de los bloques de formación de
lenguajes, y es porque se genera a partir de Æ por medio de la estrella de Kleene; la cadena vacía pertenece a la estrella de
Kleene de cualquier lenguaje posible y por lo tanto debe pertenecer a Æ* y, por tanto, Æ**={l }.
 Para modificar el diagrama de transiciones, se coge el diagrama:
a. Se añade un nuevo estado que va a ser el de inicio

b. Este nuevo estado inicial también lo marcaremos como de aceptación (para que así puede aceptar la cadena vacía)

c. Por cada uno de los arcos que hay desde el estado inicial original hacia otros (puede ser el mismo), se dibuja desde el nuevo
estado inicial un arco hacia el estado destino del arco correspondiente en el diagrama original y se etiqueta con el mismo
símbolo
d. Desde cada estado de aceptación se dibuja un arco por cada uno de los que salen desde el estado inicial original hacia
otros (puede ser el mismo). Este sale hacia el estado destino del arco correspondiente que salía del estado inicial en el
diagrama original y se etiqueta con el mismo símbolo.
e. Se quita la característica de inicio del estado inicial original.
 z
OPERACIÓN REGULARES - ESTRELLA DE KLEENE

Para diseñar el autómata finito que admite el lenguaje concatenación

aplicamos:

• Se añade al diagrama un nuevo estado que va a ser el de inicio y lo

marcaremos como de aceptación

• Por cada uno de los arcos que hay desde el estado inicial original hacia
otros (puede ser el mismo), se dibuja desde el nuevo estado inicial un
arco hacia el estado destino del arco correspondiente en el diagrama
original y se etiqueta con el mismo símbolo

• Desde cada estado de aceptación se dibuja un arco por cada uno de los
que salen desde el estado inicial original hacia otros (puede ser el
mismo). Este sale hacia el estado destino del arco correspondiente que
salía del estado inicial en el diagrama original y se etiqueta con el
mismo símbolo.

• Se quita la característica de inicio del estado inicial original.

 z
OPERADORES

Las expresiones regulares denotan lenguajes. Por ejemplo, la expresión regular 01*+10* define el lenguaje que consta de
todas las cadenas que comienzan con un 0 seguido de cualquier número de 1s o que comienzan por un 1 seguido de
cualquier número de 0s.

Antes de describir la notación de las expresiones regulares, tenemos que estudiar las tres operaciones sobre los lenguajes
que representan los operadores de las expresiones regulares. Estas operaciones son:
 Ejemplo:

1. La unión de dos lenguajes L y M, designada como L ∪ M, es el conjunto de cadenas que pertenecen a L, a M o a
ambos. Por ejemplo, si L={001,10,111} y M = {ε ,001}, entonces L ∪ M = {ε ,10,001,111}.

2. La concatenación de los lenguajes L y M es el conjunto de cadenas que se puede formar tomando cualquier cadena
de L y concentrándola con cualquier cadena de M. Para designar la concatenación de lenguajes se emplea el punto o
ningún operador en absoluto, aunque el operador de concatenación frecuentemente se llama “punto”. Por ejemplo, si
L={001,10,111} y M = {ε ,001}, entonces L.M, o simplemente LM, es {001,10,111,001001,10001,111001}. Las
tres primeras cadenas de LM son las cadenas de L concatenadas con ε . Puesto que ε es el elemento identidad para la
concatenación, las cadenas resultantes son las mismas cadenas de L. Sin embargo, las tres últimas cadenas de LM se
forman tomando cada una de las cadenas de L y concatenándolas con la segunda cadena de M, que es 001. 
 z
OPERADORES

3. La clausura (o asterisco, o clausura de Kleene) de un lenguaje L se designa mediante

L^*y representa el conjunto de cadenas que se pueden formar tomando cualquier número de
cadenas de L, posiblemente con repeticiones (es decir, la misma cadena se puede seleccionar
más de una vez) y concatenando todas ellas. Por ejemplo, si L = {0,1}, entonces L^*es igual
a todas las cadenas de 0s y 1s. Si L = {0,11}, entonces L^(* )constará de aquellas cadenas de
0s y 1s tales que los 1s aparezcan por parejas, como por ejemplo 011,11110 y ε , pero no
01011 ni 101. Más formalmente, L* es la unión infinita ∪ (i≥0) L^i, donde L^0=(ε),L^1=L y
L^i, para i>1 es LL• • •L (la concatenación de i copias de L).
 z
PRECEDENCIA DE LOS OPERADORES
Como con otras álgebras, los operadores de las expresiones regulares tienen un orden de “precedencia” prefijado, lo que
significa que se asocian con sus operando en un determinado orden. El orden de precedencia de los operadores es el
siguiente:

 Ejemplo:

1. El operador asterisco (*) es el de precedencia más alta. Es decir, se aplica sólo a la secuencia más corta de símbolos a su
izquierda que constituye una expresión regular bien formada.
2. El siguiente en precedencia es el operador de concatenación, o “punto”. Después de aplicar todos los operadores * a sus
operando, aplicamos los operadores de concatenación a sus operando. Es decir, todas las expresiones yuxtapuestas
(adyacentes sin ningún operador entre ellas). Dado que la concatenación es una operación asociativa, no importa en qué
orden se realicen las sucesivas concatenaciones, aunque si hay que elegir, las aplicaremos por la izquierda. 
3. Por último, se aplican todos los operadores de unión (+) a sus operando. Dado que la unión también es asociativa, de
nuevo no importa en que orden se lleven a cabo, pero supondremos que se calculan empezando por la izquierda.
 En ocasiones no se desea que una expresión regular sea agrupada según la precedencia de los operadores. En dicho caso,
se puede emplear paréntesis ( ) para agrupar los operando de la forma que se desee. Además, nunca está de más encerrar
entre paréntesis los operando que se quieran agrupar, incluso aunque la agrupación deseada sea la prevista por las reglas
de precedencia.
 z
BIBLIOGRAFIAS

 Carrasco, R. C., Calera Rubio, J., & Forcada Zubizarreta, M. L. (2000). Teoría de lenguajes,
gramáticas y autómatas para informáticos. Digitalia. (pp. 127 - 142). Recuperado de 
[Link]
.[Link]/[Link]?direct=true&db=nlebk&AN=318032&lang=es&site=ehost-live&eb
v=EB&ppid=pp_Cover
 Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales. Universidad de
Extremadura. Servicio de Publicaciones. (pp. 39 - 70). Recuperado de 
[Link]
=true&db=edsbas&AN=edsbas.62161440&lang=es&site=eds-
 González, A. [Ángela]. (2018, junio 1). Lenguajes Regulares. [Archivo web]. Recuperado de 
[Link]
 González, A. [Ángela]. (2020, julio 14). Lenguajes Regulares. [Archivo web]. Recuperado de 
[Link]