Colaborativo No. 2

INTRODUCCIÓN

Mediante el presente trabajo se pretende dar a conocer la temática correspondiente a la Unidad N°2 –LENGUAJES INDEPENDIENTES DE CONTEXTO los cuales que también se conocen con el nombre de gramáticas de contexto libre son un método recursivo sencillo de especificación de reglas gramaticales con las que se pueden generar cadenas de un lenguaje.

Es factible producir de esta manera todos los lenguajes regulares, además de que existen ejemplos sencillos de gramáticas de contexto libre que generan lenguajes no regulares. Las reglas gramaticales de este tipo permiten que la sintaxis tenga variedad y refinamientos mayores que los realizados con lenguajes regulares, en gran medida sirven para especificar la sintaxis de lenguajes de alto nivel y otros lenguajes formales.

Son diversos ejercicios a desarrollar los cuales se pueden hacer con su interpretación matemática o con el simulador.

OBJETIVOS

OBJETIVO GENERAL:

Conocer los modelos de computación que corresponden a los lenguajes independientes del contexto y su aplicación.

OBJETIVOS ESPECÍFICOS:

 Generalizar los conceptos de autómatas finitos y gramáticos regulares.

 Reconocer el potencial de procesamiento del lenguaje del autómata con los Autómatas de pila.

 Lograr un buen entendimiento del desarrollo de cada ejercicio

 Adquirir nuevos conocimientos acerca de la temática trabajada

 Interactuar con el equipo de trabajo en pro de consolidar mejor las ideas

 Reconocer el proceso que se hace mediante la interpretación matemática o a través del simulador.

DESARROLLO DE LAS ACTIVIDADES

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

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

Se puede representar el autómata de la siguiente forma:

M = (Q, V, δ, q0, F), donde

Q = {q0, q1, q2, q3, q4, q5, q6, q7}  conjunto finito de estados

V = {0,1}  alfabeto de entrada

q0 = {q0}  estado inicial

F = {q2}  conjunto de estados finales

δ = {q0, q1, q2, q3, q4, q5, q6, q7} x {0,1} → q0, q1, q2, q3, q4, q5, q6, q7}

 función de transición

2. Identifique la tabla de transición

δ 1 0

 q0 {q4} {q1}

q1 {q2} {q5}

# q2 {q2} {q0}

q3 {q4} {q6}

q4 {q5} {q2}

q5 {q3} {q5}

q6 {q2} {q5}

q7 {q5} {q2}

3. Identifique el lenguaje que reconoce y las posibles cadenas

L = {0,1} El lenguaje formado por todas las cadenas formadas de 0's y 1's.

4. Encuentre la expresión regular válida. (Compruebe una cadena válida de esa expresión regular en el simulador). Identifique sus componentes

ER = (0 | 1) 1,0 *  expresión regular válida

La expresión es aceptada ya que termina en {0} e inicia en {1} y/o {0}.

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). Justifíquela si la convierte a la Izquierda o a la derecha. Plásmela en el simulador y recréela. (Debe quedar documentado en el texto el paso a paso que realizan en el simulador)

 gramática válida para la función

Se define completamente la operación de concatenación por la derecha con las letras del alfabeto de la función.

Paso 1  Tener plasmado en el simulador el diagrama de Moore del Autómata propuesto.

Paso 2  Verificar las cadenas válidas reconocidas por el autómata.

Paso 3  Generar la gramática en el simulador desde el Menú Convert  Convert to Grammar.

Paso 4  Clic en el botón “Show” de la ficha “Convert to Grammar” para visualizar la gramática generada en el simulador.

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

La distinción entre derivación por la izquierda y por la derecha es importante porque en la mayoría de analizadores, la transformación de la entrada es definida dando una parte de código para cada producción que es ejecutada cuando la regla es aplicada. De modo que es importante saber qué derivación aplica el analizador, porque determina el orden en el que el código será ejecutado.

Una derivación también puede ser expresada mediante una estructura jerárquica sobre la cadena que está siendo

...