Problemas a desarrollar
Enviado por lidavanesa2015 • 13 de Julio de 2015 • Exámen • 469 Palabras (2 Páginas) • 232 Visitas
Problemas a desarrollar:
Parte 1: calcular al autómata mínimo correspondiente al siguiente autómata infinito.
1. Enuncie el autómata en notación matemática
M = (K, ∑, qo, σ, F)
2. Identifique la tabla de transición correspondiente
Q / E1 o 1
qo q1 q2
q1 qo q3
q2 q3 qo
q3 q5 q4
q4 qo q6
q5 q6 qo
q6 q5 q4
o 1
C2 C2
C1 C2
C2 C1
C2 C2
C1 C2
C2 C1
C2 C2
3. Identifique el lenguaje que reconoce y enuncie cinco posibles cadenas válidas que terminen en un estado “halt”
El lenguaje que reconoce será el de todas las posibles cadenas ω que empiecen por O ó por 1 y terminen en O ó 1, bajo ciertas condiciones (propiedad) que resulta compleja, (ER) por eso es que se minimiza o reduce el autómata.
4. Encuentre la expresión regular válida.
((11+1010+1001+ (1011+1000) (11+00)*(10+01))*0(0+110+101+ (111+100) (11+00)*(10+01)))*(11+1010+1001+ (1011+1000) (11+00)*(10+01))*0
El propósito de las ER (que no son más que simples formulas) es representar cada una de ellas un lenguaje.
5. Encuentre su gramática que sea válida para la función de transición (describa sus componentes y como se escriben matemáticamente).
Definimos y caracterizamos una gramática regular como: un cuádruplo (V, ∑, R, S) en donde:
V = Variables
∑ = Constantes
R = Conjunto de reglas, subconjunto finito de V x (∑V U ∑)
S = Símbolo inicial y es un elemento de V.
...