AUTOMATAS

Cadena 111000110

Encuentre la expresión regular válida.

[00 + 11 + (01 + 10) (1(11)*0 + 0(00)*1)]*

Encuentre su gramática que sea válida para la función de transición (describa sus componentes y como se escriben matemáticamente).

Rta: Es una gramática de tipo 3 es decir regular y libre de contexto, donde Sus producciones son de la forma:

Lineal por la derecha: Cuando todas las producciones tienen la siguiente forma:

A―›aB o A―›a, donde A,B N , a T, Donde Se permiten producciones de la forma B

Finalmente la gramática está definida por: G= ({A,B,C,D,E,F,G},{a,b},P,S) siendo P el siguiente conjunto.

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

GRAMATICA POR LA IZQUIERDA:

La gramatica valida es por la derecha porque todas sus producciones tienen la forma

Y al generar la gramática por la izquierda el simulador no muestra interacción del gráfico.

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

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

Definición

Se dice que una gramática es ambigua si alguna palabra del lenguaje que genera tiene más de un árbol de derivación.

Palabra: 100011

Gramática:

ACTIVIDADES PARA EL EJERCICIO A MINIMIZAR Y YA MINIMIZADO:

Identifique los estados No distinguibles y los Distinguibles. Justifique o caracterice la diferencia entre ellos.

Un par de estados es distinguible cuando un estado de la pareja es final y el otro no. En este caso las parejas de estado distinguibles serian (q2,q0) (q2,q1) (q2,q3) (q2,q4) (q2,q5) (q2,q6) (q2,q7).

Identifique los estados equivalentes. Para ello realice el proceso de validación de equivalencias identificando los estados a ser eliminados

Los estados indistinguibles o equivalentes para el caso de nuestro autómata inicial son (q3, Q5) (q7, Q1); en el caso de (q3, Q5), de q3 sale un 1 para q6 y un 0 para q2 y esto ocurre exactamente igual con q5. En el caso de (q7, Q1), de q7 sale un 1 para q2 y un 0 para q6 lo cual ocurre igual con q1.

Después de eliminar los estados q5 y q7 también se convierten en equivalentes la pareja de estados (q1, Q0), ya que de estas salen un 0 para q1 y un 1 para q3.

Realice el proceso de eliminación de estados (que estados se suprimen y porque). Realice la eliminación de transiciones y de estados

Como dijimos en el punto anterior los estados equivalentes son (q3, q5) y (q7, q1), por lo tanto procedemos a eliminar de cada pareja uno de ellos. En este caso vamos a eliminar q5 y q7 quedando el autómata como se muestra en la siguiente imagen:

Autómata después de eliminar q5 y q7 manualmente

Se puede realizar de nuevo el mismo análisis notando que la pareja de estados q4 y q0 son también equivalentes ya que presentan las mismas transiciones de 0 hacia q1 y 1 hacia q3 respectivamente. Se procede entonces con la eliminación de q4 ya que q0 es el estado inicial por lo tanto continuamos con él.

Realice la tabla de estados distinguibles.

q1 *

q2 x x

q3 * * x

q4 (q7,q1) * x *

q5 * * x (q3,q5) *

q6 * * x * * *

q7 * * x * * * *

q0 q1 q2 q3 q4 q5 q6

x distinguibles

*

Son equivalentes (q3, q5) (q7, q1) y (q4,

...