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)

...