Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Transformacion de un automata finito a una expresion regular

No description

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Transformacion de un automata finito a una expresion regular

El objetivo de las expresiones regulares es representar todos los posibles lenguajes definidos sobre un alfabeto , en base a una serie de lenguajes primitivos, y unos operadores de composición.

Concepto de Expresion Regular
Transformacion de un automata finito a una expresion regular y viceversa
Lenguajes primitivos: el lenguaje vacío, el lenguaje formado por la palabra vacía, y los lenguajes correspondientes a los
distintos símbolos del alfabeto.

Operadores de composición: la unión, la concatenación y el cierre.

Estos son algunos lenguajes primitivos
1. Lenguaje formado por las cadenas que terminan en 01:
{0,1}*.{01}=
({0}∪{1})*.{01}
Expresión regular: (0+1)*01
2. Lenguaje formado por palabras de longitud par sobre a’s y b’s:
{aa,ab,ba,bb}*=
({aa}∪{ab}∪{ba}∪{bb})*
Expresión: (aa+ab+ba+bb)*
EJEMPLO
Observación:

De este modo sólo se puede demostrar que dos
expresiones regulares son equivalentes. Sin embargo, mediante este método, no es posible demostrar que dos expresiones regulares describen lenguajes distintos.
Dado un alfabeto X, las expresiones regulares sobre X se definen de forma recursiva por las siguientes reglas:
1. Las siguientes expresiones son expresiones regulares primitivas:
• 0
• Lamda
• a, siendo a € X.
2. Sean A y B expresiones regulares, entonces son expresiones regulares derivadas:
• A+B (unión)
• A.B (o simplemente AB) (concatenación)
• A* (cierre)
• (A)
3. No hay más expresiones regulares sobre X que las construidas mediante estas reglas.

Precedencia de los operadores:
1. ()
2. * cierre
3. . concatenación
4. + unión

Ejemplo:
Algunos ejemplos de expresión regular son:
(0 + 1)*01
(aa + ab + ba + bb)*
a*(a + b)
(aa)*(bb)*b
La semántica de una expresión regular define un lenguaje.

Dado una expresión regular $\alpha$ (sobre un alfabeto $\Sigma$). ¿Qué tiene que ver el lenguaje $L(\alpha)$ con un lenguaje $L(M)$ aceptado por un autómata finito $M$?

Veremos: para cada expresión regular $\alpha$ existe un autómata no-determinista con transiciones $\epsilon $ $M$, o sea un AFND-$\epsilon $, que acepta el mismo lenguaje (es decir, $L(\alpha)=L(M)$).

Ya sabemos: entonces también existe un autómata finito determinista, o sea un AFD, aceptando el mismo lenguaje.

De hecho, comprobaremos algo más: para cada $\alpha$ sobre $\Sigma$ existe un AFND-$\epsilon $ $M=(\Sigma,Q,\delta,q_0,F)$ con $L(\alpha)=L(M)$
Equivalencia entre autómatas finitos y expresiones regulares
Equivalencias y propiedades de las ER
Paula Andrea Rozo
Carlos Eduardo Carvajal
Jorge Andres Corzo

Transformacion de una expresion regular a un automata finito
EJEMPLO
CONSTRUCCION DEL AFD
Calcular las funciones Anulable, PrimeraPos, UltimaPos y SiguientePos
haciendo recorridos en profundidad del árbol.
3. Construir EstadosD (la letra D por Determinístico), el conjunto de
estados del AFD, por medio del procedimiento descripto en el punto
siguiente. Los estados dentro de EstadosD son conjuntos de posiciones;
al principio, cada estado está "no marcado", y un estado se convierte en "marcado" justo antes de considerar sus transiciones de salida. El estado
inicial del AFD es PrimeraPos(raíz), y los estados de aceptación son
todos los que contienen la posición asociada con el marcador #

Se realiza mediante siguiente procedimiento:
1. Construir el árbol sintáctico para la expresión regular aumentada
Exp Reg #, donde # es un marcador de final que se añade a Exp Reg y
que difiere de los caracteres que pueden aparecer en ExpReg (no debe
estar dentro del conjunto de terminales).
Para la expresión regular utilizada en los puntos precedentes tenemos
los siguientes pasos:
1. Inicialmente EstadosD = { {1, 2, 3} }.
El único estado del conjunto está sin marcar.

Sea E = { 1, 2, 3 } el estado actual, al que luego se le dará el número 0:
U'+' = { 3 } Transición[ {1, 2, 3}, '+' ] = { 3 }
U'-' = { 3 } Transición[ {1, 2, 3}, '-' ] = { 3 }
Ud
= { 3, 4 } Transición[ {1, 2, 3}, d ] = { 4, 3 }
EstadosD = { {1, 2, 3}0, {3}, {3, 4} }
QUE SON LOS ESTADOS
Los estados (conjunto de posiciones siguientes) fueron numerados de 0
a n-1, donde n es el cardinal del conjunto EstadosD.
Hay un solo estado final y es el {3, 4} (al que se le dio el número 2),
puesto que es el que contiene la posición que corresponde al #, que fue
numerada con 4. El conjunto de estados finales queda así:
Estados Finales = { {3, 4} }
La tabla de transiciones de estados para el autómata finito determinístico
que reconoce cadena de caracteres con la estructura " ( '+' | '-' ) ? d +" es la
siguiente:
Estado '+' '-' d
0 1 1 2
1 no definido no definido 2
2 no definido no definido 2
La gráfica del autómata finito determinístico para el ejemplo dado es:
Full transcript