Automatas y lenguajes perfectos
Enviado por Estudiantes unipanamericana • 25 de Octubre de 2016 • Trabajos • 337 Palabras (2 Páginas) • 171 Visitas
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA
UNAD
[pic 2]
CURSO
AUTOMATAS Y LENGUAJES FORMALES
TRABAJO COLABORATIVO
TUTOR
ANGELA MARIA GONZALEZ
PRESENTADO POR:
ROBERTH ROJAS MOSQUERA
COD. 1.144.131.603
JUNIO 2015
2. PARA LA EXPRESION REGULAR 4: 1*0 + 1*0(λ +0+1)*(λ +0+1)
RESUELVA:
- Describa la forma matemática del autómata
R / El siguiente autómata determina como “Autómata Finito Determinista”; se expresa la notación matemática; como el Autómata Finito Determinista, equivale de la notación 5-tupla y se determina de la siguiente manera, M =( K ,∑,,σ, F )[pic 3]
- Plasme la tabla de transición. Identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta. (No se trata de dar el concepto de determinismo)
R /
[pic 4]
q0, λ = q1
q0, 0 = q2
q0, 1 = q2
q1, 1 = q2
q1, 0 = q3
q2, 1 = q2
q2, 2 = q5
q3, λ = q2
q3, 2 = q4
q4, 1 = q2
q4, 2 = q5
q5, 1 = q3
q5, 2 = q5
- Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto). Debe explicar y describir cada elemento y la función y significado en el autómata. Conceptos y definiciones adicionales.
R / 5-Tupla M Finito: M = =( K ,∑, q0 ,σ, F )
Q = Es un conjunto finito de estados
∑ = Es un alfabeto finito
q0 ε Q = Es el estado inicial
σ = Es una función de transición
F = Es un conjunto de estados finales o de aceptación
K = (q0, q1, q2, q3, q4, q5)
∑ = (0, 1, 2)
q0= q0 Estado inicial
f = (q0, q1, q4, q5)
Se expresa en la transición de la siguiente manera:
σ = (q0, q1, q2, q3, q4, q5) x (0, 1, 2) (q0, q1, q2, q3, q4, q5) q0 (q0, q1, q4, q5)[pic 5][pic 6][pic 7]
- Identifique el lenguaje que genera
R / El lenguaje que genera, el autómata finito determinista, según las transacciones.
Ṧ = (q0, q1, q4, q5) Estado final
W = 1122
Ṧ = (q0, W) = q0, q1, q4, q5
...