Hoja 8 (20 de Abril de 2010)

P1: Sea C = {a,b,c,d,e,f,g,h} un conjunto (de letras), y sea R = {(a, d), (b, e), (c, a), (d, b), (e, c), (f, g), (g, h)} ⊂ C × C una relación sobre C.

  • Construye las relaciones Ri para todos los i = 0, . . . , ∞.
    • R0 ={(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(g,g),(h,h)}   (Las relaciones de todos los elementos consigo mismo)
    • R1={(a,d),(b,e),(c,a),(d,b),(e,c),(f,g),(g,h)} (La relación que nos dan)
      • (a,d) de R1  y (d,b) de R1 generan (a,b).
      • (b,e) de R1 y (e,c) de R1 generan (b,c).
      • (c,a) de R1 y (a,d) de R1 generan (c,d).
      • (d,b) de R1 y (b,e) de R1 generan (d,e).
      • (e,c) de R1 y (c,a) de R1 generan (e,a).
      • (f,g) de R1 y (g,h) de R1 generan (f,h).
      • (g,h) de R1 no genera nada.
    • R2={(a,b),(b,c),(c,d),(d,e),(e,a),(f,h)} <–( la unión de las relaciones generadas en R1)
      • (a,b) de R2 y (b,e) de R1  generan (a,e).
      • (b,c) de R2 y (c,a) de R1 generan (b,a).
      • (c,d) de R2 y (d,b) de R1 generan (c,b).
      • (d,e) de R2 y (e,c) de R1 generan (d,c).
      • (e,a) de R2 y (a,d) de R1 generan (e,d).
      • (f,h) de R2  no genera nada
    • R3={(a,e),(b,a),(c,b),(d,c),(e,d)} <– ( la unión de las relaciones generadas en R2)
      • (a,e) de R3 y (e,c) de R1 generan (a,c).
      • (b,a) de R3 y (a,d) de R1 generan (b,d).
      • (c,b) de R3 y (b,e) de R1 generan (c,e).
      • (d,c) de R3 y (c,a) de R1 generan (d,a).
      • (e,d) de R3 y (d,b) de R1 generan (e,b).
    • R4={(a,c),(b,d),(c,e),(d,a),(e,b)} <– (la unión de las relaciones generadas en R3)
      • (a,c) de R4 y (c,a) de R1 generan (a,a).
      • (b,d) de R4 y (d,b) de R1 generan (b,b).
      • (c,e) de R4 y (e,c) de R1 generan (c,c).
      • (d,a) de R4 y (a,d) de R1 generan (d,d).
      • (e,b) de R4 y (b,e) de R1 generan (e,e).
    • R5={(a,a),(b,b),(c,c),(d,d),(e,e)} <– (la unión de las relaciones generadas en R4)
      • (a,a) de R5 y (a,d) de R1 generan (a,d).
      • (b,b) de R5 y (b,e) de R1 generan (b,e).
      • (c,c) de R5 y (c,a) de R1 generan (c,a).
      • (d,d) de R5 y (d,b) de R1 generan (d,b).
      • (e,e) de R5 y (e,c) de R1 generan (e,c).
    • R6={(a,d),(b,e),(c,a),(d,b),(e,c)} <– (la unión de las relaciones generadas en R5)
      • (a,d) de R6  y (d,b) de R1 generan (a,b).
      • (b,e) de R6 y (e,c) de R1 generan (b,c).
      • (c,a) de R6 y (a,d) de R1 generan (c,d).
      • (d,b) de R6 y (b,e) de R1 generan (d,e).
      • (e,c) de R6 y (c,a) de R1 generan (e,a).
    • R7={(a,b),(b,c),(c,d),(d,e),(e,a)} <– (la unión de las relaciones generadas en R6)
      • (a,b) de R7 y (b,e) de R1  generan (a,e).
      • (b,c) de R7 y (c,a) de R1 generan (b,a).
      • (c,d) de R7 y (d,b) de R1 generan (c,b).
      • (d,e) de R7 y (e,c) de R1 generan (d,c).
      • (e,a) de R7 y (a,d) de R1 generan (e,d).
    • R8={(a,e),(b,a),(c,b),(d,c),(e,d)} ==R3 <– (la unión de las relaciones generadas en R7)
    • R9==R4
    • R10=R5
    • R11=R6
    • R12=R7
    • R13=R3
    • Rn=  R (n-3) mod 5+3
  • Construye la relación R∗.

Basta con unir todas las relaciones hasta R5 ( a partir de R7 el resto estarán repetidas y R5,R6 y R7 son subconjuntos)

R*={(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(g,g),(h,h),(a,d),(b,e),(c,a),(d,b),(e,c),(f,g),(g,h),(a,b),(b,c),(c,d),(d,e),(e,a),(f,h),(a,e),(b,a),(c,b),(d,c),(e,d),(a,c),(b,d),(c,e),(d,a),(e,b)}

  • Argumenta si R∗ es reflexiva, simétrica , y/o transitiva.
    • Reflexiva: Si porque todo elemento estan relacionados consigo mismo al pertenecer R0 a R*.
    • Simétrica:
      • (a,d) y (d,a) V
      • (b,e) y (e,b) V
      • (c,a) y (a,c) V
      • (d,b) y (b,d) V
      • (e,c) y (c,e) V
      • (f,g) no existe (g,f) F
      • (g,h) no existe (h,g) F
      • (a,b) y (b,a) V
      • (b,c) y (c,b) V
      • (c,d) y (d,c) V
      • (d,e) y (e,d) V
      • (e,a) y (a,e) V
      • (f,h) no existe (h,f) F
    • Transitiva: Si, porque hemos relacionado todas los pares entre si
  • ¿Cuál pareja (o parejas) deberíamos añadir a la relación R para que R∗ sea simétrica (si piensas que R∗ no es simétrica en el apartado anterior)?
    • (g,f), (h,g) y (h,f)

Hoja 7 (13 de Abril de 2010)

P1: Determina una expresión regular α que define el mismo lenguaje aceptado por el autómata de la Hoja 5, digamos M , es decir, se tiene que cumplir L(α) = L(M ). Documenta tu construcción suficientemente (tienes dos lados de una hoja).

partimos del autómata de la hoja 5

Automata Inicialpara transformar nuestro AFND en una expresión regular necesitamos crear un AFNDG que este cumpla una serie de caracteristicas:

  1. El estado inicial no puede tener transiciones entrantes.
  2. El estado inicial debe de contar con transiciones salientes a los otros estados.
  3. Solo puede existir un estado final.
  4. El estado final no puede tener transiciones salientes.
  5. El estado final tiene que recibir transiciones entrantes de los otros.
  6. Excepto los estados inicial y final, cada estado tiene una única transición a los otros estados.

Transformando un AFND a un AFNDG

  1. Añadimos un nuevo estado inicial s con una transición epsilon  al viejo estado inicial.
  2. Añadimos un nuevo estado final f con transiciones epsilon entrantes de los viejos estados finales.
  3. Si dos estados están conectados con múltiples transiciones, las reemplazamos por una única transición en la que su etiqueta es la unión de las etiquetas reemplazadas.
  4. Si dos estados no están conectados, añadimos una transición etiquetada con ∅ entre ellos (en ambas direcciones).
  • Las transiciones ∅ nunca serán usadas.

Empezamos la transformación.

Paso 1:

AFND a AFNDG paso 1Paso 2:

AFND a AFNDG paso 2

Paso 3:

No existen multiples transiciones que conecten 2 estados nuestro automata sigue como esta.

Paso 4:

Vamos a dejar las transiciones ∅ sin poner.

De AFNDG a Expresión Regular

Para convertir un AFNDG con k estados en una expresión regular:

  1. Si k=2, solo tenemos los estados f y s. La etiqueta de la transición de s a f es la expresión regular equivalente al AFNDG
  2. Si k>2 , entonces construimos un AFNDG con k-1 estados.
    1. a) Escogemos un estado distinto de s y f.
    2. b) Eliminamos el estado seleccionado del autómata
    3. c) Reconectamos las transiciones sueltas de forma apropiada.
      1. Para cada par de estados, qi y qj, cambiamos la etiqueta de la transición por una que pueda tomar el AFNDG desde qi a qj de forma directa o a través del estado que estamos seleccionado

Comenzamos eliminando el estado marcado como 1

  • no tiene transiciones consigo mismo
  • las transiciones entrantes provienen  del estado  {s}
  • las transiciones salientes se dirigen a los estados {2,6}

por lo tanto debemos crear los transiciones {s,2} y {s,6}

  • la transición {s,2} es ε
  • la transición {s,6} es a

las modelamos en el automata

Estado 1 eliminado

no tenemos transiciones que tengan el mismo origen y destino continuamos

Eliminamos el estado marcado como 2:

  • tiene transiciones consigo mismo.
  • las transiciones entrantes provienen del conjunto de estados {s}
  • las transiciones salientes se dirigen a los estados {3,f}

por lo tanto tenemos que generar las transiciones {s,3} y {s,f}, como hay transición consigo mismo debemos ingresar (b)* en el medio

  • la transición {s,3} es (b)*.a
  • la transición {s,f} es (b)*

tras la eliminación del estado 2 nuestro autómata toma la siguiente forma

no tenemos transiciones que tengan el mismo origen y destino continuamos

Eliminamos el estado marcado como 3

  • no tiene transiciones consigo mismo
  • las transiciones entrantes provienen de {s,4,5}
  • las transiciones salientes se dirigen a {4,6}

por lo tanto debemos generar las transiciones {s,4},{s,6},{4,4},{4,6},{5,4},{5,6}

  • la transición {s,4} genera (b)*.aa
  • la transición {s,6} genera (b)*.a
  • la transición {4,4} genera b.a
  • la transición {4,6} genera b
  • la transición {5,4} genera a.a
  • la transición {5,6} genera a

tras la eliminación del estado 3 nuestro autómata toma la siguiente forma.

Estado 3 eliminado

tenemos transiciones con mismo origen y destino, {s,6} las unimos y nuestro autómata toma la siguiente forma

Estado 3 eliminado y transiciones

Eliminamos el estado marcado como 4

  • tiene transiciones consigo mismo
  • las transiciones entrantes provienen de {s,5,6}
  • las transiciones salientes se dirigen a{5,6,f}

por lo tanto debemos generar las transiciones {s,5},{s,6},{s,f},{5,5},{5,6},{5,f},{6,5},{6,6},{6,f} como 4 tiene transición consigo mismo tenemos que insertar (ba)* en el medio

  • la transición {s,5} genera (b)*aa(ba)*b
  • la transición {s,6} genera (b)*aa(ba)*b
  • la transición {s,f} genera (b)*aa(ba)*
  • la transición {5,5} genera aa(ba)*b
  • la transición {5,6} genera aa(ba)*b
  • la transición {5,f} genera aa(ba)*
  • la transición {6,5} genera (ba)*b
  • la transición {6,6} genera (ba)*b
  • la transición {6,f} genera  (ba)*

tras la eliminación del estado 4 nuestro autómata toma la siguiente forma.

Estado 4 eliminado

tenemos transiciones con el mismo origen y destino las unimos y nuestro autómata queda así

Estado 4 eliminado y transiciones

Eliminamos el estado marcado como 5

  • tiene transiciones consigo mismo
  • las transiciones entrantes provienen de {s,6}
  • Las transiciones salientes se dirigen  a {f,6}

las transiciones que debemos de crear son {s,f},{s,6},{6,f},{6,6} como  tiene transiciones consigo mismo debemos insertar (aa(ba)*b)* en medio

  • la transición {s,f} genera  (b)*aa(ba)*b(aa(ba)*b)*aa(ba)*
  • la transición {s,6} genera (b)*aa(ba)*b(aa(ba)*b)* (a+(aa((ba)*b)))
  • la transición {6,f} genera  (b+((ba)*b))(aa(ba)*b)*aa(ba)*
  • la transición {6,6} genera (b+((ba)*b))(aa(ba)*b)*(a+(aa((ba)*b)))

tras la eliminación del estado 5 nuestro autómata toma la siguiente forma

Estado 5 eliminadotenemos transiciones con el mismo origen y destino así que las unimos

la transición {s,6} quedara ((b)*aa(ba)*b(aa(ba)*b)*(a+(aa((ba)*b)))+((a+((b)*a))+(b)*aa(ba)*b)) ==s6

la transición {s,f} quedara (((b)*aa(ba)*b(aa(ba)*b)*aa(ba)*)+((b)*+(b)*aa(ba)*)) == sf

la transicion {6,6} quedara (((b+((ba)*b))(aa(ba)*b)*(a+(aa((ba)*b))))+((ba)*b)) == 66

la transición {6,f} quedara (((b+((ba)*b))(aa(ba)*b)*aa(ba)*)+((ba)*)) == 6f

Eliminamos el estado marcado como 6

  • tiene transiciones consigo mismo.
  • las transiciones entrantes provienen de {s}
  • las transiciones salientes se dirigen a {f}

por lo tanto deberemos de generar las transiciones {s,f} teniendo el cuenta como existe transición consigo mismo tenemos que insertar (66)* en medio

la transición {s,f} genera (sf)+((s6)(66)*(6f))

tras la eliminación del estado 6 nuestro autómata ya es la expresión regular.

((((b)*aa(ba)*b(aa(ba)*b)*aa(ba)*)+((b)*+(b)*aa(ba)*)))+((((b)*aa(ba)*b(aa(ba)*b)*(a+(aa((ba)*b)))+((a+((b)*a))+(b)*aa(ba)*b)))((((b+((ba)*b))(aa(ba)*b)*(a+(aa((ba)*b))))+((ba)*b)))*((((b+((ba)*b))(aa(ba)*b)*aa(ba)*)+((ba)*))))

introducimos a expresión regular en JFlap la transformamos es un AFND y comparamos la equivalencia con el AFNDG y………………………

Good Luck bad nigth

vamos que esta bien 🙂 a la 2ª fue la vencida

Fuentes:

http://vega.icu.ac.kr/~jiae/Automata_spring2008/DFA2RE.pdf

Practica 6 Talf

El enunciado aquí Practica 6 Talf

1.-Minimiza el autómata A1 = ({0,1},{q0, q1, q2, q3, q4}, f, q0,{q1, q2}) en donde f se define como:

  • f(q0, 0) = q3
  • f(q0, 1) = q2
  • f(q1, 0) = q4
  • f(q1, 1) = q1
  • f(q2, 0) = q0
  • f(q2, 1) = q3
  • f(q3, 0) = q0
  • f(q3, 1) = q2
  • f(q4, 0) = q4
  • f(q4, 1) = q1

modelamos el autómata en JFlap

modelado automata ejercicio 1para minimizarlo vamos al menu “Convert”->”minimize DFA”

minimizando paso 1obviamente los estados q1 y q4 quedan fuera porque no están asociados al grafo del estado inicial.

Pinchamos en el botón “Finish”

minimizado paso 2pinchamos en “complete” y en “done?” por lo que se mostrara el autómata minimizado en una nueva ventana

afd minimo

2. Indica cuáles de los siguientes autómatas son equivalentes entre sí:

  • AF1={{a,b},{p,q,r,s,t,u}, f1, p, {q,r}}
  • AF2={{a,b},{p,q,r,s,t,u}, f2, p, {u}}
  • AF3={{a,b},{p,q,r,s,t,u}, f3, p, {s,t,u}}
  • AF4={{a,b},{p,q,r,s,t,u}, f4, p, {r,s}}
  • AF5={{a,b},{p,q,r,s,t}, f5, p, {r,s}}

Autómata 1

F1 a b
p q p
q r s
r q t
s t u
t s u
u q u

modelamos el autómata en JFlap

automata 1

autómata 2

F2 a b
p q u
q r t
r s t
s r t
t u s
u u q

modelamos el autómata en JFlap

automata 2

autómata 3

F3 a b
p u q
q t r
r s r
s t r
t u q
u s p

modelamos el autómata en JFlap

automata 3

autómata 4

F4 a b
p r q
q r q
r s t
s r t
t t q
u u p

modelamos el autómata en JFlap

automata 4

autómata 5

F5 a b
p q r
q q t
r s q
s r q
t r q

modelamos el autómata en JFlap

automata 5

En la ventana de JFlap donde esta contenido el aútomata pintamos en “Test -> Compare Equivalence” y nos dice si es equivalente o no.

de la comprobación sacamos la siguiente tabla

@ AF1 AF2 AF3 AF4 AF5
AF1 F F V F
AF2 F F V
AF3 F F
AF4 F
AF5

Por lo tanto los autómatas equivalentes son AF1 con AF4 y AF2 con AF5

Mi examen practico de TALF

Recién sacadito del horno.

1º Ejercicio:

Obtener las trazas para las siguientes palabras en este autómata :

automata examenLas palabras de las que se deben obtener las trazas son:

  • aabbaabb: Acepta la palabra, Genera 3 trazas.
  • aaabbbaaa: No acepta la palabra.

2º Ejercicio: Crea un AFND que acepte los números binarios en los que la tercera cifra por la derecha sea diferenta a la segunda por la izquierda.

Resuelto aquí con muchas mas soluciones de otros modelos de examen.

Que tengáis mucha suerte.

Posibles preguntas para el primer examen practico de TALF

tirando de archivo me encontre unas preguntitas de exámenes prácticos de talf:

Modelar el autómata tal que acepte el lenguaje que contenga palabras con 2 o más pares de ceros consecutivos .

Ej 0000 , 100100100 , 111111001100 , 11111100100100100

autómata que contenga dos pares de ceros consecutivos

Tomado de la corrección en el primer comentario

Modelar el autómata tal que acepte el lenguaje que contenga palabras con como mínimo 4 ceros .

minimo 4  cerosModelar el autómata tal que acepte el lenguaje tal que { a^n b^m / n>= 1 y m>=2 }

una a dos besModelar el autómata tal que acepte el lenguaje tal que formula_3

tres a dos b alguna cModelar el autómata tal que acepte el lenguaje tal que acepte todos los binarios excepto los que contengan la subcadena 101.

Lo hacemos por el método del complemento primero modelamos un autómata que acepte palabras que contengan la subcadena 101.

acepta subcadena 101aplicamos el metodo del complemento (los estados finales se transforman en no finales y viceversa)

no acepta subcadena 101

Modelar el autómata tal que acepte el lenguaje binario tal que la tercera cifra por la derecha sea distinta a la segunda cifra por la izquierda.

segundo izquierda distinto tercero derechaDado un alfabeto {a, b, c}, construir un AFD que acepte aquellas palabras que contengan al menos dos ‘a’, una ‘b’ y una ‘c’

dos a una b una cteneis aqui el Autómata

Practica 5 TALF

Enunciado practica 5

Autómatas finitos no deterministas

1.- Dado el autómata finito no determinista descrito por la siguiente tabla, obtener el autómata finito determinista y posteriormente minimizarlo. El alfabeto que usa el autómata se compone de los símbolos: ∑ = {a,b}; el estado inicial es q0; y los estados finales q2 y q4.

tabla autómata 1modelamos el autómata en JFlap

autómata sin minimizar 1Ahora es el momento de minimizarlo, primero debemos transformarlo en un AFD. para eso seleccionamos la opción (“Convert to DFA”) del menú Convert.

convirtiendo a AFD

Pinchamos en Complete y finalmente en Done? lo que nos creara un AFD en una nueva ventana.

AFD convertido

Pinchamos en la opción minimize DFA del menú convert para obtener el AFD mínimo

minimizando

Pinchamos en el primer elemento del árbol de estados y pinchamos en el botón “Complete Subtree” para posteriormente pinchar en el botón “finish”

Esto creara una nueva ventana con el conjunto de estados.

conjunto de estados

pinchamos en “complete” para que cree los enlaces

enlaces creados

y finalmente en “done” que nos mostrara una ventana con el AFD minimizado.

AFD minimo

2.- Dado el autómata finito no determinista descrito por la siguiente tabla, obtener el autómata finito determinista y posteriormente minimizarlo. El alfabeto que usa el autómata se compone de los símbolos: ∑ = {0,1}; el estado inicial es q0; y el estado final q1.

tabla autómata 2

modelamos el autómata en JFLAP

lo transformamos en un AFD siguiendo los pasos del ejercicio anterior.

y lo minimizamos igual que en el ejercicio anterior.

Hoja 6 (6 de Abril de 2010)

P1: ¿Qué lenguajes definen las siguientes expresiones regulares?

  • Expresión regular numero 1: (((0.1)∗ + (0.1)∗ .0) + ((1.0)∗ + (1.0)∗ .1))
    Descomponemos la expresión regular

primera formula despiece webempezamos a descomponer la expresión regular a partir de los nodos finales (marcados en rojo).

Primera Formula Nodos finales marcadosPaso 1:  intentamos minimizar los nodos finales: en esta expresión no se puede

Paso 2:Describimos el lenguaje de cada nodo final:

  • :  cero o mas repeticiones  de la cadena 01
  • :cero o mas repeticiones de la cadena 01
  • : Cadena 0
  • formula 1 nodo final 4:cero o mas repeticiones de la cadena 10
  • formula 1 nodo final 5: Cadena 1

subimos al nivel anterior y unimos los nodos en los que sus elementos siguientes estén descritos hasta que lleguemos a la raíz del árbol.

formula 1  primera iteracion miramos si podemos minimizar los nodos a describir (marcados de rojo), en este caso no podemos.

asi que describimos los nodos en los que nos encontramos

  • formula 1 segunda interacion nodo 1: cero o mas repeticiones  de la cadena 01 unidas con 0
  • formula 1 segunda iteracion nodo 2:cero o mas repeticiones de la cadena 10 unidos con 1

nueva iteración. subimos al nivel superior

formula 1 tercera iteracion nodo 1

miramos si podemos minimizar los nodos a describir (marcados de rojo), en este caso no podemos.

asi que describimos los nodos en los que nos encontramos

  • formula 1 tercera iteracion nodo 1: cero o mas repeticiones de la cadena 01 ó cero o mas repeticiones  de la cadena 01 unidas con 0

subimos

ultima subida

Describimos la expresión regular  uniendo los elementos anteriores (+=0) (*=y)

cero o mas repeticiones de la cadena 01 ó cero o mas repeticiones  de la cadena 01 unidas con 0, o cero o mas repeticiones de la cadena 10 unidos con 1

Expresión regular numero 2: expresion regular numero dos

Paso 1: Descomponemos la expresión regular en pequeñas expresiones.

expresion regular numero 2 descompuesta

marcamos los nodos finales

expresion regular numero 2 nodos finalesMinimizamos los nodos finales, en este caso no se puede

Describimos los nodos finales

  • expresión_2_nodo_1:  la cadena 1 o nada
  • expresion numero 2 nodo 2: cero o mas repeticiones de la cadena 01
  • expresion 2 nodo 3:la cadena 0 o nada

subimos al siguiente nivel de la estructura

expresion regular numero 2 segunda iteracion

intentamos minimizar la expresión actual: no se puede

Describimos la expresión actual.

  • expresion regular numero dos:la cadena 1 o nada unida a cero o mas repeticiones de la cadena 01 unida a la cadena 0 o nada

  • Expresión regular numero 3 expresion regular numero 3

Paso 1: Descomponemos la expresión regular en pequeñas expresiones.

Arbol tercera expresion regular

marcamos los nodos finales

Arbol 3 era expresion nodos finales marcadosintentamo minimizar algún nodo final en este caso si que podemos

  • primera equivalencia
  • segunda equivalencia

empezamos a minimizar hacia arriba y nos queda la siguiente expresión minimizada

expresion regular numero 3 minimizada

describimos las expresiones del segundo nivel

  • minimizados primer elemento: la cadena 01
  • minimizado segundo elemento: cero o mas repeticiones de la cadena  con 0 o mas repeticiones de cero o de la cadena 01
  • : la cadena 1

por lo tanto el lenguaje que define esta expresión regular es: la cadena 01 o cero o mas repeticiones de la cadena  con 0 o mas repeticiones de cero o de la cadena 01 unido a la cadena 1

P2: Escribe una expresión regular sobre el alfabeto {a, b, c} que define todas las palabras que tengan dos a’s consecutivos o dos b’s consecutivos.

(a+b+c)*.((aa)+(bb)).(a+b+c)*

P3: Construye según procedimiento visto en clase un AFND–ε que acepta las mismas palabras que define la expresión regular de P1 apartado 2.
modelamos  las pequeñas expresiones el las que hemos descompuesto la expresión 2:

expresión_2_nodo_1

primer subautomata

expresion numero 2 nodo 2

2a_parte

expresion 2 nodo 3

Ahora unimos las partes en un autómata .

Practica 4 TALF

Enunciado Practica 4

afnd1

1.- Dado el AFND- ε afnd1
a. Marcar los estados no deterministas

Pinchamos en Test ->  Highlight NonDeterminism

Estados no deterministas marcados

b. Marcar las transacciones ε (λ)

Pinchamos en Test ->  Highlight λ-Transitions

transiciones epsilon

c. Indica la traza de todos los caminos recorridos hasta aceptar o no aceptar
las palabras:

  • aaabbaab
    • No existen trazas en las que  acepte el automa
    • Trazas que no aceptan
  • aaaaaabbbbbb
    • Trazas que Acepta
    • Trazas que no Acepta

NOTA: utiliza para ello todas las opciones del Step by State (Step,Reset,Freeze,Thaw,Trace, Remove)

2.-Modela un autómata sobre el paso de una persona de un estado civil a otro: tener en cuenta al menos los estados civiles “soltero”, “casado”, “divorciado”, “viudo”. Considere al divorcio como un proceso con duración (instantáneo).

estados civiles

3.-Diseñar usando el método del complemento un AFD que acepte las palabras en {a, b} que no inicien con abab.

metodo complemento

4.- Construir autómatas finitos deterministas que acepten cada uno de los lenguajes siguientes.
a.

no 4 as

b. Los números binarios en los que la primera cifra es diferente de la última.

numeros binarios
c. Todas las cadenas sobre  que contienen al menos una vez cada símbolo de  .

todos los símbolos del alfabeto

Practica 3 TALF

Enunciado de la practica Enunciado Practica 3 Talf.

1.-Introduce en JFlap el siguiente autómata e intenta averiguar que lenguaje describe

autómata ejercicio 1Para averiguar que lenguaje genera el autómata la forma mas intuitiva es transformarlo en una expresión regular,  en el menu de JFlap seleccionamos “Convert->Convert FA to RE”

Convert FA to REpinchamos en el boton “Do It” el cual generara transiciones vaciás entre estados

Empty trasitions addedVolvemos a pinchar en “Do It” para eliminar estados no iniciales o no finalesintermediate states eliminated

la etiqueta de informacion situada debajo de la pestaña de conversión nos indica que la transformación de autómata finito a expresion regular esta completada, por lo tanto ya podemos pinchar en el botón Export el cual creara una nueva ventana mostrándonos la expresión regular

expresión regular

por lo tanto el lenguaje que crea este autómata  esta compuesto por un numero de caracteres (a>=0)  una letra b y un numero de repeticiones de la cadena bb>=0

2.- Modela el autómata que reconozca cadenas con un número par de “0”s y “1”s

Partimos de que 0 es par por lo tanto ε es una palabra valida, y el estado inicial.

Los posibles estados para este autómata son:

  • Numero de 1’s par y numero de 0’s par
  • Numero de 1’s par y numero de 0’s impar
  • Numero de 1’s impar y numero de 0’s par
  • Numero de 1’s impar y numero de 0’s impar

creamos un nuevo autómata en JFlap introduciendo los cuatro posibles estados:

estados autómatahabíamos quedado en que ε tiene un numero par de 0’s y un numero par de 1’s por lo tanto 1P0P es estado inicial y final. Asi que lo que nos queda es completar las transiciones.

automata numero de unos paresy numero de  ceros pares3.- Autómata que reconozca cadenas impares de de “0”s y “1”s

igual que el apartado anterior pero cambiando el estao final en lugar de 1P0P es 1I0I

automata unos impares ceros impares4.- Construye un AFD que acepte identificadores, con las siguientes características
a. Solo letras vocales minúsculas
b. Es válido el carácter de subrayado, con la condición que como máximo exista uno
c. No se permiten espacios en blanco
d. También puede tener números, pero no pueden estar al principio ni al final del identificador, ni haber más de tres consecutivos

automata 4

Hoja 5 (23 de Marzo de 2010)

P1: Convierte el siguiente AFND–ε en un AFND (incluye todas las tablas, grafos, quintuplas, y el cálculo de la clausura transitiva necesario). El estado inicial es el estado 1.

AFND-E hoja 5

Hagamos memoria una quintupla se representa por esta formula Quintupla base donde:

  • Alfabetoes un alfabeto
  • conjunto de estadoses un conjunto finito no vació de estados
  • funcion de Transiciones una función de transición
  • conjunto de estados inicialeses el estado inicial
  • F es el conjunto de estados finales

Para el AFND–ε la quintupla estará formada por:

  • Alfabeto={a,b,ε}
  • conjunto de estados={1,2,3,4,5,6}
  • funcion de Transicionla tabla de transición
  • conjunto de estados iniciales={1}
  • F={2,4}

Creamos la tabla de transición para el AFND-ε

Elemento a b

epsilon

1

{6} {emptyset} {2}

2

{3} {2} {emptyset}

3

{4} {emptyset} {6}

4

{emptyset} {3,5} {emptyset}

5

{3} {emptyset} {emptyset}

6

{emptyset} {5} {4}

ahora calculamos las clausuras para cada elemento

Por clausura de un elemento entendemos el conjunto de estados a los que podemos acceder sin consumir ninguna símbolo , el propio elemento al que le calculamos su clausura  pertenecerá a la misma.

para que quede mas claro, para el elemento 3 su clausuara estara compuesta por 3, 6 “(3,ε)=6” y 4 “(6,ε)=4”

Elemento a b epsilon clausura
1 {6} {emptyset} {2} {1,2} = Cl(1)
2 {3} {2} {emptyset} {2} = Cl(2)
3 {4} {emptyset} {6} {3,6,4} = Cl(3)
4 {emptyset} {3,5} {emptyset} {4} = Cl(4)
5 {3} {emptyset} {emptyset} {5} = Cl(5)
6 {emptyset} {5} {4} {6,4} = Cl(6)

Ahora creamos una nueva tabla eliminando la columna de ε  y substituyendo  los estados de destino para cada elemento del alfabeto por la unión de los estados de destino de la clausura. Por ejemplo para el elemento 1 la clausura es {1,2} y para la transición con a debemos incluir 6 para el estado 1 y 3 para el estado 2. por lo tanto nos queda el conjunto {6,3}.

delta a b
Cl(1)

{6,3}

{2}

Cl(2)

{3}

{2}

Cl(3)

{4}

{3,5}
Cl(4) {emptyset} {3,5}
Cl(5)

{3}

{emptyset}
Cl(6) {emptyset} {3,5}

una vez realizada esta tabla creamos la ultima tabla substituyendo cada estado destino de la  tabla anterior por la clausura del mismo

delta a b
Cl(1)

{3,4,6}

{2}

Cl(2)

{3,4,6}

{2}

Cl(3)

{4}

{3,4,5,6}

Cl(4)

{emptyset}

{3,4,5,6}

Cl(5)

{3,4,6}

{emptyset}

Cl(6)

{emptyset}

{3,4,5,6}

Ahora ajustamos los estados para añadir los iniciales y los finales. Si en la clausura de un  elemento existe un estado inicial este es inicial (marcados verde en la segunda tabla) y si existe un estado final este es final (marcados de rojo en la segunda tabla) con esto ya tenemos el AFND sin transiciones epsilon

delta a b
*->Cl(1)

{3,4,6}

{2}

*Cl(2)

{3,4,6}

{2}

*Cl(3)

{4}

{3,4,5,6}

*Cl(4)

{emptyset}

{3,4,5,6}

Cl(5)

{3,4,6}

{emptyset}

*Cl(6)

{emptyset}

{3,4,5,6}

Para el AFND la quintupla estará formada por:

  • Alfabeto={a,b}
  • conjunto de estados={1,2,3,4,5,6}
  • funcion de Transicionla tabla de transición
  • conjunto de estados iniciales={1}
  • F={1,2,3,4,6}

Modelamos el nuevo autómata en JFlap

AFND Cargamos el otro en JFlap

dos autómatasEn la ventana de cualquier autómata seleccionamos el menú  test y la opción “compare equivalence” y seleccionamos el otro automata

comparar dos autómatas

pinchamos en aceptar y son equivalentes

son equivalenteslo que significa que aceptan el mismo lenguaje