Problemas a desarrollar

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.

Estas gramáticas regulares son de la forma:

Lineales por la derecha. – cuando todas las producciones tienen la forma

A aB o bien A a

6. Genere la gramática tanto por la izquierda como por la derecha y verifique cual es válida sustentando el por qué.

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

8. Identifique si ese árbol o gramática es ambigua o no y plasme las razones de su afirmación

La gramática no es ambigua porque hay un solo árbol de derivación.

...