|
![]() TEMA 2.- LENGUAJES REGULARES |
||||
![]() |
|||||
![]() |
|||||
![]() |
|||||
![]() |
|||||
![]() |
|||||
![]()
|
|||||
![]() Al lenguaje generado por medio de una gramática regular. Son aquellos lenguajes cuyas cadenas está formadas por la concatenación de símbolos, en las cuales no hay relación entre una parte de la cadena y otra parte de la cadena. |
|||||
|
Vemos que una gramática regular o de tipo 3 es aquella gramática donde las reglas de producción siguen la siguiente estructura: A→ uB o A→ u donde u∈ T* y A,B∈ V | ||||
![]() |
|||||
![]() ![]() |
|||||
|
|||||
![]() |
|||||
DEFINICIÓN: Un autámata finito es una quintupla M=(Q,A, d ,q0,F) en la cual: | |||||
Q es un conjunto finito llamado conjunto de estados. | |||||
A es un alfabeto llamado alfabeto de entrada. | |||||
d es una aplicación de la forma siguiente d : Q x A→ Q de modo que dado un estado y un símbolo del alfabeto se produce otro estado. A esta función se le llama función de transición. | |||||
q0 es un elemento de Q, llamado estado inicial. | |||||
F es un subconjunto de Q, llamado conjunto de estados finales. | |||||
El autómata es un mecanismo con 2 partes: | |||||
|
q0......................................qn |
|
|
|
|
|
|
|
|
FUNCIONAMIENTO: En la cinta se escribe la cadena de caracteres de la que queremos determinar si pertenece al lenguaje regular que poseemos. En cada paso el autómata lee un símbolo y segn el estado en el que se encuentre, cambia de estado y pasa a leer el siguiente símbolo. Así hasta acabar de leer todos los símbolos de la cadena, en ese momento si el estado en que está la flecha o cabeza de lectura es un estado final entonces ACEPTA LA CADENA. Si no es un estado final entonces RECHAZA LA CADENA, es decir, la cadena no pertenece a ese lenguaje regular. | ||||||
![]() ![]()
|
|||||||
|
![]() |
||||||
El lenguaje que reconoce el autómata está formado por todas aquellas cadenas que se construyen de la siguiente forma: el autómata parte de q0, lee un símbolo u cualquiera y alcanza un estado final. | |||||||
Esto se nota de la siguiente forma: L(M)={u∈ A* / d (q0,u)∈ F}, donde M es el autómata finito definido como M=(Q,A, d ,q0,F) . | |||||||
Ejemplo 1: Qué lenguaje reconoce el autámata dibujado abajo? | |||||||
![]() |
|||||||
Ejemplo 2 :Qué lenguaje reconoce el autómata dibujado abajo? | |||||||
![]() |
|||||||
![]() ![]()
|
|||||||
![]() |
|||||||
Existen dos formas de representar los autómatas: | |||||||
|
|||||||
|
|||||||
|
|||||||
EJEMPLO: Realizar el grafo de transición del autómata especificado de la siguiente forma: M=(Q, A, q0, d , F) donde Q={q0, q1, q2} A={a,b} F={q2} | |||||||
d(q0,a)=q1 | d(q0,b)=q2 | d(q1,a)=q1 | d(q1,b)=q2 | d(q2,a)=q1 | d(q2,b)=q0 |
|
|
Con este otro modo de representar los autómatas solamente se especifica la tabla de las transiciones poniendo en la primera fila el alfabeto de entrada y en la primera columna el conjunto de estados Q, de modo que para cada símbolo y estado se asocia un estado al cual se va a ir. |
d | A | b |
q0 | q1 | q2 |
q1 | q1 | q2 |
q2 | q1 | q0 |
|
![]() ![]()
|
|||
![]() Si tenemos un lenguaje L1 que es aceptado por un autómata finito no determinístico AFND 1 y otro lenguaje L2 que es aceptado por un autómata finito no determinístico AFND2, entonces podemos: Ejemplo: Construir un AFND con TN que reconozca L1�/font>L2 siendo L1={u10v / u, v∈ {0,1}*} y L2={u00v /u, v∈ {0,1}*} donde sus AFND son los siguientes: AFND
1 Y AFND2 |
||||
Ejemplo:
Construir
un AFND con TN que reconozca la concatenación de L1 y L2
|
||||
![]() ![]()
|
||||
![]() |
||||
![]() |
||||
![]() |
||||
![]() |
||||
![]() |
||||
![]() |
||||
Son aquellos que tienen un número finito de estados, q0, .....,qn donde n∈ Ν. Dentro de estos autómatas llamaremos AUTÓMATA FINITO DETERMINÍSTICO MINIMAL a aquel que tiene el menor nmero de estados posibles y sigue reconociendo las cadenas del lenguaje regular. | ||||
![]() |
||||
|
||||
![]() |
||||
Son aquellos que tienen un nmero finito de estados, q0, .....,qn donde n∈ N, y es no deteminístico porque no para todo estado y todo símbolo se tiene una acción a realizar. Es decir de un nodo no pueden salir varios arcos con la misma etiqueta y ni para un nodo existen arcos para todos los símbolos del alfabeto | ||||
![]() |
||||
![]() L={u∈ {a,b,c}* / u=abic i=0} |
||||
![]() |
||||
Son
aquellos que pueden realizar una transición sin consumir entrada.
Estas transiciones se etiquetan con el símbolo de vacíe
en el grafo. En la definición,
habr�que cambiar la funci� de transición definida
como
d : Q x A→ Q de la siguiente forma d : Q x (A∪{ε }) →Q. Las transiciones nulas hacen que el autómata pueda quedarse en el estado en el que está o cambiar de estado sin consumir ningn símbolo de la palabra de entrada. Sin embargo el conjunto de lenguajes aceptado por este tipo de autómata es el mismo que para los AFD. |
||||
![]() |
||||
![]() L={u∈
{0,1,2}* /u=0i1j2k; i,j,k∈
N}
|
||||
![]() ![]()
|
||||
![]() |
||||
![]() |
||||
Sea un AFND con TN especificado por la quintupla M=(Q,A,q0,d ,F) el AFND equivalente es M`=(Q`, A`, q0`,d `,F`) donde: | ||||
Q`=sería el mismo conjunto de estados que se tiene en el AFND con TN, por tanto , Q. | ||||
A`=A. | ||||
q0`=q0. | ||||
d`(q,u) = conjunto de estados al que se puede pasar leyendo el símbolo u y aquellos estados a los que se llegue mediante ε después o viceversa. | ||||
F`= FU{q0; si puedes llegar desde el estado q0 al estado final solamente usando transiciones nulas} | ||||
![]() |
||||
M=(Q={q0,q1,q2,q3}, A={a,b,c,d}, d , q0, F={q3}) | ||||
![]() |
||||
![]() |
||||
Sea un AFND especificado por la quintupla M=(Q,A,q0,d ,F) el AFD equivalente es M`=(Q`, A`, q0`,d `,F`) donde: | ||||
Q`= conjunto de estados formado por todos los subconjuntos que se puedan formar con los elementos de Q, es decir P(Q). | ||||
A`= el alfabeto del AFND, A. | ||||
q0`= es el subconjunto de P(Q) que contiene todos los estados iniciales del AFND de partida. | ||||
d`(A,a)= ∪ d(x,a) ∀x ∈ A donde A= subconjunto de estados. | ||||
F`= todos los subconjuntos de estados que contienen al menos un estado final del AFND. | ||||
![]() |
||||
M=(Q={q0,q1},
A={a,b}, {q0,q1},d
, F={q1})
|
1.- Eliminar del AFD los estados innacesibles, es decir, que no se pueden alcanzar, desde el estado inicial. 2.- para cada pareja de estados (qi, ql): |
||
![]() |
||
3.- Para cada pareja que aún no se ha marcado como V (verdad): 3.1- Para cada símbolo del alfabeto a∈ A. 3.1.1.- Determino que pareja de estados se puede llegar leyendo a (qi,qj)→a (qk,ql) 3.1.2.- Si Distinguible (qk,ql)=V y qk ≠ql entonces Distinguible(qi,qj)=V también marcamos como distinguibles todas las parejas de la lista asociada a qi, qj equivalente L(qi,qj) 3.1.3.- Si qk ≠ql y Distinguible (qk,ql)=F entonces 3.1.4.- Si qk= ql no se hace nada. Estos pasos se repiten hasta que todas las parejas de estados tengan en la tabla V. |
||
|
![]() |
|
Dado
el AFD![]() Obtener el AFD minimal. |