Automatas Y Lenguajes Formales - Momento2

Problemas a desarrollar

Parte 1:

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

Primer punto.

Enuncie el autómata en notación matemática

Autómata M Finito:

Dónde:

Donde la función de transición está dada por:

× → → →

Punto 2.

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

El autómata finito descrito es una quíntupla donde

( ) Es el conjunto de estados, estos estados conservan la información de cierto elemento hasta que al ser motivado por un símbolo puede cambiar su comportamiento

( ), Es un conjunto finito A y sus elementos se nombraran comosímbolos o letras que al ser combinados bajo ciertas reglas permiten determinar palabras o cadenas validas que pueden llegar a generar un lenguaje

S ∈ K

es el estado inicial, para nuestro caso es q0, este se indica por un triángulo o una flecha ( )

Es el conjunto de estados finales o de aceptación, se indican mediante doble círculo. Los estados finales indican que cuando se llega a ellos, en nuestro ejemplo los estados finales son

: K x ∑ → K

Es la función de transición, que a partir de un estado y un símbolo del alfabeto obtiene un nuevo estado.

3. Identifique la tabla de transición correspondiente

δ 0 1 2 λ

→ # q0 q2 q2 ϕ q1

# q1 q3 q2 ϕ ϕ

q2 ϕ q2 q5 ϕ

q3 ϕ ϕ q4 q2

# q4 ϕ q2 q5 ϕ

# q5 ϕ q3 q5 ϕ

Se evidencia las transiciones lambda solo en los estados q0 a q1; y de q3 a q2.

4. 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 0 ó por 1 y que terminen en 0 ó 1, bajo ciertas condiciones que resultan complejas, (ER) por eso es que se minimiza o reduce el autómata.

5. Encuentre la expresión regular válida.

Siendo (q4) final es:

(02+((1+0+1)1*2+01*2)(2+11*2)*12)((2+11*2)(2+11*2)*12)*

Siendo (q5) final es:

((1+0+1)1*2+01*2+02(2+11*2))(2+11*2+12(2+11*2))*

ER:

(02+((1+0+1)1*2+01*2)(2+11*2)*12)((2+11*2)(2+11*2)*12)* + ((1+0+1)1*2+01*2+02(2+11*2))(2+11*2+12(2+11*2))*

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 (eso significa que debe hacerla por ambos lados y verificar cual es válida sustentando el por qué). Plásmela en el simulador y recréela. (Debe quedar documentado en el texto el paso a paso que realizan en el simulador).

Se caracteriza y define la gramática regular de la siguiente manera:

Un cuádruplo (V, Σ, R, S) en donde:

V = Es el alfabeto de variables

Σ = Es el alfabeto

...