EJERCICIOS_1_5

AUTOMATAS Y LENGUAJES FORMALES

Momento 2

Presentado por:

Francisco Javier contreras

Código: 88254578

Correo: [email protected]

Zona: centro oriente

Caed: Cúcuta

Grupo 301405_63

Tutor

Jaime jose valdes

Escuela de Ciencias Básicas Tecnología e

Programa de Ingeniería sistemas

Momento dos:

UN DOCUMENTO EN PDF: que contiene: Formato de presentación del Documento: El documento debe contener los siguientes puntos

PORTADA: Datos de los Estudiantes (nombre, número de matrícula, e-mail, Zona, Cead, Grupo que presenta la actividad). Datos del tutor. Descripción general del trabajo. Desarrollo de cada uno de los puntos enunciados a continuación. No se está solicitando introducción, objetivos, bibliografía. Lo importante de esta actividad es estar concentrados en el desarrollo del ejercicio como estrategia de Problemas. Estos no son considerados como aportes ni deben ir plasmados en el trabajo.

LOS ARCHIVOS GENERADOS POR EL SIMULADOR EN UNA CARPETA: Si es JFLAP (los de extensión jff) y si es con archivos de VAS (los de extensión .fa)

Problemas a desarrollar:

PARTE 1: Calcular el autómata mínimo correspondiente al siguiente autómata finito.

1. Enuncie el autómata en notación matemática e identifique que tipo de autómata es.

M=(∑ , K ,S , q0 , F )

K= {q0 , q1 , q2, q3 , q4 , q5 , q6 , q7 }∑ ¿ {0,1 }, F={q0 , q3 , q5 } , S= {q0 } y

q0=es el estado inicial

Es un Autómata Finito Determinista (AFD), ya que para todos los estados el autómata puede responder solamente por una transición para dicho estado; por ejemplo, estando en el estado q0 se puede ir al estado q1 a través de 1, y a q2 a través de 0.

2. Identifique los componentes del autómata (que tipo de tupla es)

Las Tuplas se describen a continuación:

S :¿

Estando en el estado q0 se llega al estado q2 a través de 0, y al estado q1 a través de 1








L(M )

→0→1

3. Identifique la tabla de transición correspondiente

La tabla de transición será:

0 1

4. Identifique el lenguaje que reconoce (no en notación de ER) y enuncie cinco posibles cadenas válidas que terminen en el estado “halt” y cinco cadenas no válidas

El lenguaje que reconoce el autómata vendrá dado por:

L (A )={W / δ̂ (q0 ,W )∈F }

Cinco cadenas válidas que terminen en el estado Halt serán:

W 1=00 δ̂ (q0 ,W 1 )=q3

W 2=11 δ̂ (q0 ,W 2 )=q5

W 3=0101 δ̂ (q0 ,W 3 )=q5

W 4=0110 δ̂ (q0 ,W 4 )=q3

W 5=1010 δ̂ (q0 ,W 5 )=q3

Cinco cadenas no válidas serán:

W 6=0100

W 7=1011

W 8=0111

W 9=01110

W 10=10110

5. Encuentre la expresión regular válida. (se genera de forma manual, asociando cada operador y sentencia al diagrama de moore de forma explicativa). No se genera con el JFLAP

q0=0q2+1q1

q1=0q4+1q5

q2=0q3+1q4

q3=0q2+1q7+λ

q4=0q7+1q6

q5=0q6+1q1+λ

q6=0q3+1q4

q7=0q4+1q5

6. Encuentre su gramática que sea válida para la función de transición (describa sus componentes y como se escriben matemáticamente). Justifíquela si la convierte a la Izquierda o a la derecha. Plásmela en el simulador y recréela. (Debe quedar documentado en el texto el paso a paso que realizan en el simulador)

6. Encuentre su gramática que sea válida para la función de transición (describa sus componentes y como se escriben matemáticamente). Justifíquela si la convierte a la Izquierda o a la derecha. Plásmela en el simulador y recréela. (Debe quedar documentado en el texto el paso a paso que realizan en el simulador)

Gramática

Letra EstadoS q0A q1B q2C q3D q4E q5F q6G q7

S 0B

S 1A

A 0D

A 1E

B 0C

B 1D

C 0B

C 1G

C λ

D 0G

D 1F

E 0F

E 1A

E λ

F 0C

F 1D

G 0D

G 1E

7. Realice el árbol de Derivación de esa gramática.

Documents

EJERCICIOS_1_5