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 .