TRABAJO FINAL TAREA 2

Ejercicio a trabajar

Caracterización del autómata

Autómata finito no determinista. Es el autómata finito que tiene transiciones vacías o que por cada símbolo desde un estado de origen se llega a más de un estado destino. Los AFND son definiciones no tan deseables dentro de los lenguajes regulares porque dificultan su implementación tanto mecánica como informática; aunque en la mayoría de las transformaciones a lo interno de los LR (expresiones regulares a AF, gramáticas regulares a AF) conducen a AFND. Los AFND, por tanto, son imprescindibles en el análisis lexicográfico y el diseño de los lenguajes de programación.

Q={q 0 , q 1 , q 2 } ∑ ¿{a , b } q 0 ∈ Q={q 0 } F ⊆Q={q 2 } δ ( q 0 , a )=q 2 δ ( q 0 , b )=q 1 δ ( q 2 ,a )=q 2 δ ( q 2 ,b )=q 1 δ ( q 2 ,b )=q 0 Tabla de transición: Estado Actual q0 q1 q2

Estado Siguiente a q2 q2

b  q1   q1, q0

Para identificar la estructura de este automata observamos que sus rutas no tienen definido su sentido, por esta razón este automata es Finito NO DETERMINISTA.

Procedimiento de

PASO 1 no se puede dejar ninguna transición repetida o que vaya hacia ella

conversión de Autómata Finito a Expresión Regular paso a paso

misma por ende hay que desdoblarlos.

PASO 2 Eliminamos a q2

PASO 3 Eliminamos a q0

Autómata final convertido

Lenguaje regular

ER= ab*b+11

EJERCICIOS 2: Conversión de Autómatas Finitos Deterministas a Autómatas Finitos No deterministas (AFD a AFND) y viceversa Ejercicio a trabajar

Caracterización del autómata

Autómata finito no determinista. Es el autómata finito que tiene transiciones vacías o que por cada símbolo desde un estado de origen se llega a más de un estado destino. Los AFND son definiciones no tan deseables dentro de los lenguajes regulares porque dificultan su implementación tanto mecánica como informática; aunque en la mayoría de las transformaciones a lo interno de los LR (expresiones regulares a AF, gramáticas regulares a AF) conducen a AFND. Los AFND, por tanto, son imprescindibles en el análisis lexicográfico y el diseño de los lenguajes de programación.

Q={q 0 , q 1 , q 2 } ∑ ¿{a , b , c , λ } q 0 ∈ Q={q 0 } F ⊆Q={q 2 } F ⊆Q={q 2 } δ ( q 0 , a )=q 0 δ ( q 0 , a )=q 1 δ ( q 0 , b )=q 2 δ ( q 1, c )=q 1 δ ( q 1, c )=q 2 δ ( q 2 , λ )=q 0 Tabla de transición: Estado Actual

a

Estado Siguiente c b

λ

q0 q0, q1 q2 q1 q1, q2 q2 q0 Para identificar la estructura de este automata observamos que sus rutas no tienen definido su sentido, por esta razón este automata es Finito NO DETERMINISTA. También Transitan entre un conjunto finito de estados posibles. Estando en un estado y recibiendo una entrada del exterior el autómata tendrá la posibilidad de transitar a más de un estado del conjunto de estados posibles.

Procedimiento de conversión paso a paso

Paso 1 no se puede dejar ninguna transición repetida o que vaya hacia ella misma por ende hay que desdoblarlos.

Paso 2 Eliminamos el dobles de q0.

Paso 3 Eliminamos el dobles de q1.

Paso 4 Eliminamos q1.

Paso 4 Eliminamos q0.

Autómata final convertido

Practicar y verificar lo aprendido

Para este inciso utilizaremos el software JFLAP para observar las cadenas aceptadas y rechazadas del sistema. PARA EL AUTOMATA ORIGINAL

PARA EL AUTOMATA FINAL

Ejercicio Grupal: Construir autómata Construir un autómata que realice lo siguiente: ER = (ab*c(cc)*b)

Ejercicio a trabajar

Caracterización del autómata

M= {q0, q1, q2, q3, q4, q5, q6}, {a, b, c} S=q0, F=q6 Q= {q0, q1, q2, q3, q4, q5, q6} Estados Σ = {a, b, c} Alfabeto q0∈Q = q0 F= {q0, q6} Función δ: {q0, q1, q2, q3, q4, q5, q6} X {a, b, c} {q0, q1, q2, q3, q4, q5, q6} (q0, a) = q1 (q1, c) = q2 (q1, b) = q3 (q3, b) = q3 (q3, c) = q2 (q2, c) = q4 (q2, b) = q6 (q4, c) = q5 (q5, b) = q4 (q5, c) = q6 -Tabla de transición: Estado Actual →q0 q1 q2 q3 q4 q5

a q1 -

Estado Siguiente b   q3  q6 q3 q6

c q2 q4 q2 q5 q4

PARTE TEORICA

AUTOMATA FINITO es un autómata finito en donde δ (delta) es una función de transición, es decir, que para cada par (estado actual y símbolo de entrada) le corresponde un único estado siguiente. Si para todo estado del autómata existe como máximo una transición definida para cada símbolo del alfabeto, se dice que el autómata es determinístico (AFD). Si a partir de algún estado y para el mismo símbolo de entrada, se definen dos o más transiciones se dice que el autómata es no determinístico (AFND). Formalmente un autómata finito se define como una 5-upla M = donde E: conjunto finito de estados A: alfabeto o conjunto finito de símbolos de entrada δ: función de transición de estados, que se define como - δ: E x A → E si el autómata es determinístico - δ: E x A → P(E) si el autómata es no determinístico (P(E) es el conjunto potencia de E, es decir el conjunto de todos los subconjuntos de E) e0: estado inicial; e0 ∈ E F: conjunto de estados finales o estados de aceptación; F ⊆ E

Autómata final convertido

VALIDACION DE CADENAS

ER= ab*c(cc)*b

REALIZAREMOS UN TEST POR UNA DE LAS RUTAS ACEPTADAS DE AUTOMATA PRACTICAR Y VERIFICAR LO APRENDIDO

El simulador se ubica en el estado q0 en donde se iniciara el recorrido de la ruta

Como podemos observar la cadena comienza con el símbolo ‘a’ en donde hace transición al estado q1 desde q0

El siguiente símbolo es “b” al leer este símbolo el autómata pasa del estado q1 donde se encuentra al q3, aquí hacemos una aclaración ya que cuando se pasa al estado q3 este se repite ya que una de sus transiciones vuelve a su estado original por eso en la cadena se repita la letra ‘b’.

La transición se traslada al estado q2 con el símbolo c proveniente de q3

Finalmente, q2 se lee el ultimo símbolo de la cadena el cual es “b”, el cual esta conectado o hace transición en q6 que es el estado final de la cadena.