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

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 .

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

Hoja 3 (9 de Marzo de 2010)

P1: Calcula, paso a paso, el resultado de la función  para el autómata de la hoja anterior y la palabra de entrada w=0100110, es decir, .

w=0100110

P2: Escribe la tabla para la función de transición  del AFND con el siguiente grafo:

Calcula, paso a paso, el resultado de la función para este autómata y la palabra de entrada w=0100110, es decir, . Averigua una palabra sobre {0,1} que el autómata no acepta.

Como el autómata acepta.

Una palabra que el autómata no aceptaria seria cualquiera que acabara con mas de dos ceros.

Gracias a melasuda por la resolución.