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.

...