Tipos de Gramática

[pic 1][pic 2][pic 3][pic 4]

Lenguajes

y

Autómatas II.

UNIDAD 2 TAREA 1.

Tema: Tipos de Gramática

Equipo 9

Alumnos:         Sergio Daniel Jimenez Zacarias

                        Carlos Donado Ramón Gómez

Luis Pablo Ramos Perez

Elizabeth Soveranez Alvarez

Maestro:                Dr. Alejandro Peña Casanova

Villahermosa, Tabasco, México.  3 de octubre del 2019

Resumen

El objetivo del presente es introducir algunos de los conceptos teóricos necesarios sobre la teoría de gramáticas, para poder integrarlos como una herramienta matemática que nos permitirá diseñar lenguajes de programación mediante la construcción de autómatas que ayuden al reconocimiento de cadenas válidas para esos lenguajes.

En décadas anteriores los sistemas se manejaban con el uso de trabajo humano, lo que propiciaba lentitud y gastos elevados en la industria, por ello llega la creación de sistemas automatizados, es decir, se busca tecnología que puedan seguir procesos industriales sin necesidad de la intervención humana, pero esto solo se lograría con una evolución en la informática.

Para lograr definir una gramática es necesario conocer que es la teoría de autómatas por lo cual Von Neumann(1948) citado por Serafín Moral (s.f.,p.16) introduce el termino de teoría de autómatas y dice sobre los trabajos de McCulloch-Pitts:” …el resultado más importante de McCulloch-Pitts, es que cualquier funcionamiento en este sentido, que pueda ser definido en todo, lógicamente y sin ambigüedad, en un número finito de palabras, puede ser realizado también por una tal red neuronal formal”.

Entonces podemos entender que para la creación de los autómatas es necesario que éste se defina totalmente de manera que logre especificarse toda la lógica necesaria evitando así toda clase de ambigüedad. Requiere de igual manera tener un conjunto de palabras finito, es decir, que estén establecidos todos los elementos y no puedan ser modificados.

(Chomsky ,1956) propone tres modelos para la descripción de lenguajes que son la base de su futura jerarquía de los tipos de lenguajes, que ayudó también en el desarrollo de los lenguajes de programación. Para ello intentó utilizar autómatas para extraer estructuras sintácticas y dirige sus estudios a las gramáticas, indicando que la diferencia esencial entre autómatas y gramáticas es que la lógica asociada a los autómatas es elegible, mientras que la asociada a las gramáticas no lo es.

Tomando en cuenta de que la lógica de la gramática no es elegible, podemos definir a la gramática como un conjunto de reglas para formar cadenas finitas juntando diversos símbolos del alfabeto (Peinado,2010, p.2). Para ello es necesario analizar a detalle las partes de una gramática la cuales son: elementos no terminales, elementos terminales, producciones y el símbolo de partida.

Todas las cadenas del lenguaje definido por la gramática están formadas del vocabulario terminal el cual se define por la enumeración de los símbolos terminales, mientras que el vocabulario no terminal es el conjunto de símbolos introducidos como elementos auxiliares para la definición de la gramática pero que no figuran en las sentencias del lenguaje.

El símbolo inicial es un símbolo no terminal a partir del cual se aplican las reglas de la gramática para obtener las distintas cadenas del lenguaje. Las producciones son las reglas que se aplican desde el símbolo inicial para obtener las cadenas del lenguaje.

De acuerdo a (Borrajo, Isasi & Martínez, 1997) una gramática formal consta de un conjunto finito de símbolos terminales, un conjunto finito de símbolos no terminales, un conjunto de reglas de producción, y un símbolo inicial. Las reglas se aplican sustituyendo sus lados; una derivación, por lo tanto, es una secuencia de aplicaciones de reglas. A este conjunto de cadenas posibles se le llama lenguaje formal.

Por ejemplo: Una gramática con no terminales escritas dentro de etiquetas < >, y terminales sin ellas, con s -> <articulo> <nombre><predicado>    y las siguientes reglas de producción:

• <enunciado>   🡪   <sujeto> <predicado>
• <sujeto>   🡪   <forma nominal>
• <forma nominal>   🡪   <articulo> <nombre>
• <articulo>   🡪   el
• <nombre>   🡪   hombre | libro | balón
• <predicado>   🡪   <verbo> <forma nominal >
• <verbo>   🡪  tomó | compró
• <enunciado>   🡪   <sujeto> <predicado>
• <sujeto> <predicado>   🡪   <forma nominal> <predicado>
• <forma nominal> <predicado>   🡪   <articulo> <nombre><predicado>

Puede derivar distintas cadenas, por ejemplo:

<articulo> <nombre><predicado>   🡪   el <nombre><predicado> 🡪  el hombre <predicado> 🡪   el hombre <verbo> <forma nominal> 🡪   el hombre tomó <forma nominal> 🡪 el hombre tomó <articulo> <nombre> 🡪   el hombre tomó el <nombre> 🡪   el hombre tomó el libro

 De acuerdo a los tipos de gramáticas formales y los lenguajes formales que a su vez generan, se pueden clasificar dentro de la llamada jerarquía de Chomsky. Esta jerarquía fue descrita por el lingüista estadounidense (Chomsky, 1956) y consta de 4 niveles, donde cada una forma parte de las anteriores.[pic 5]

Las gramáticas tipo 0, también llamadas sin restricciones o recursivas, son el tipo más general de gramática ya que incluyen a toda gramática formal. Estas generan todos los lenguajes que pueden ser reconocidos por una máquina de Turing.

Las gramáticas del tipo 1 son llamadas gramáticas dependientes del contexto y generan a su vez lenguajes dependientes de contexto. (Hopcroft, Motwani & Ullman, 2010) describen sus reglas de producción con la forma alfa A Beta🡪 Alfa Gamma Beta donde A es un no terminal; alfa, beta y gamma son cadenas de terminales y no terminales; y gamma ha de ser distinto del vacío. Como se observa, A puede ser sustituido por gamma si está acompañada de alfa por la izquierda y de beta por la derecha, es por ello que se les llama dependientes del contexto. Estos lenguajes pueden ser reconocidos por una máquina de Turing no determinista.

Las gramáticas del tipo 2 son llamadas independientes de contexto y generan lenguajes libres de contexto. Están definidas por reglas de la forma A 🡪 Gamma donde A es un no terminal y gamma es una cadena de terminales y no terminales. Se denominan independientes de contexto porque A puede sustituirse por gamma independientemente de las cadenas por las que esté acompañada. Estos lenguajes pueden ser reconocidos por los autómatas de pila.

Las gramáticas tipo 3 o gramáticas regulares se estructuran de la forma: A🡪aB,
A 🡪 a. De acuerdo a la Universidad Tecnológica Nacional (UTN, s.f.) los lenguajes regulares formados por esta gramática, al igual que las libres de contexto del tipo 2, forman la estructura léxica básica de los lenguajes de programación, por ejemplo, la sintaxis de los identificadores, números, cadenas y otros símbolos básicos del lenguaje. Estos lenguajes pueden ser reconocidos por un autómata finito.

Ejemplos

(Gaudioso, 2010, pp. 45-56) describe gramáticas 0 a 3 en los siguientes ejemplos:

Tipo 0

La gramática G1 = ({A}, {a, b, c}, P1, S1), siendo P1:

• S1 🡪 A
• A 🡪 aAa
• A 🡪 bAb
• A 🡪 c

La gramática G2 = ({A, B, C}, {0, 1, 2, 3}, P2, S2), y P2 contiene las producciones

• S2 🡪 ABC
• S2 🡪 AC
• S2 🡪 BC
• S2 🡪 C
• A 🡪0A1
• A 🡪 01
• B 🡪 1B2
• B 🡪 12
• C 🡪 3C
• C 🡪 3

Tipo 1

Dado la gramática G4 = < {A, B, C}, {a, b, c}, S4, P4> donde P4 contiene las siguientes producciones:

• S4 🡪 A
• A 🡪 aABC
• A 🡪 abC
• CB 🡪 BC
• bB 🡪 bb
• bC 🡪 bc
• cC 🡪 cc

Por ejemplo, derivando la cadena aaabbbccc

• S4 🡪 A 🡪 aABC 🡪 aaABCBC 🡪 aaabCBCBC 🡪 aaabBCCBC 🡪 aaabBCBCC 🡪 aaabBBCCC 🡪 aaabbBCCC 🡪 aaabbbCCC 🡪 aaabbbcCC 🡪 aaabbbccC 🡪 aaabbbccc

Dado la gramática G5= < {A, B, C}, {a, b, c}, S5, P5> donde P5 contiene las siguientes producciones:

...