Clasificacion De Gramaticas

13 Clasificación de las gramáticas
Prof. Edgardo Adrián Franco Martínez http://computacion.cs.cinvestav.mx/~efranco efranco.docencia@gmail.com
@efranco_escom

1

• Jerarquía de Chomsky
• • • • • • • • Gramáticas tipo 3 Gramáticas tipo 2 Gramáticas tipo 1 Gramáticas tipo 0 Gramáticas tipo 3 Gramáticas tipo 2 Gramáticas tipo 1 Gramáticas tipo 0

• Descripción de las gramáticas

•Ejercicios
2

Teoría computacional 13 Clasificación de las gramáticas Prof. Edgardo Adrián Franco Martínez

Contenido

En 1950 el lingüista norteamericano Avram Noam Chomsky introdujo la teoría de las gramáticas transformacionales o teoría de lenguajes formales, que convirtió la lingüística en una ciencia y proporcionó una herramienta que no sólo podía aplicarse a los lenguajes naturales, sinoque facilitaba el estudio y la formalización de los lenguajes para la programación de computadoras (1960).
Estudio tradicional de los lenguajes gramática
análisis de la estructura de las frases

morfología sintaxis fonética
Propiedades del lenguaje hablado

Diversas formas que toman las palabras según su valor en la frase Diversas formas en que se combinan las palabras para formar frasescorrectas aún no aplicable a los lenguajes de computación

semántica
estudio de su significado

Teoría computacional 13 Clasificación de las gramáticas Prof. Edgardo Adrián Franco Martínez

3

• En función de la forma de sus producciones, se puede caracterizar qué tan compleja es una gramática formal. • Noam Chomsky mostró que esta caracterización clasifica jerárquicamente a las gramáticasformales: Gramáticas en un nivel están incluidas en los siguientes niveles y la inclusión entre niveles es propia.

Teoría computacional 13 Clasificación de las gramáticas Prof. Edgardo Adrián Franco Martínez

4

5

Teoría computacional 13 Clasificación de las gramáticas Prof. Edgardo Adrián Franco Martínez

Gramáticas Tipo 3 (gramáticas regulares)
• Generan los lenguajes regulares.Las reglas (producciones) se restringen a un único no terminal en la parte izquierda y una parte derecha compuesta por un único terminal que puede estar seguido o antecedido, de un único no terminal. Es decir, normas del tipo: Aa A aB A Ba
• Estos lenguajes son los que pueden ser decididos por un autómata finito (regular). • Los lenguajes regulares se utilizan para definir estructura léxica delos lenguajes de programación. Definen la sintaxis de los identificadores, números, cadenas y otros elementos básicos del lenguaje.

Teoría computacional 13 Clasificación de las gramáticas Prof. Edgardo Adrián Franco Martínez

6

Gramáticas Tipo 2(independientes o libres de contexto)
• Generan los lenguajes libres de contexto. Están definidas por reglas de la forma: • Aγ • A es un noterminal • γ es una cadena de terminales y no terminales. • Se denominan independientes de contexto porque A puede sustituirse por γ independientemente de las cadenas por las que esté acompañada. • Estos lenguajes son todos los lenguajes que pueden ser reconocidos por los autómatas de pila.
• Los lenguajes independientes de contexto constituyen la base teórica para la sintaxis de la mayoría de loslenguajes de programación. Definen la sintaxis de las declaraciones, las proposiciones, las expresiones, etc.(i.e. la estructura de un programa).

Teoría computacional 13 Clasificación de las gramáticas Prof. Edgardo Adrián Franco Martínez

7

Gramáticas Tipo 1 (dependientes de contexto)
• Generan los lenguajes dependientes de contexto. Contienen reglas de producción de la forma:
α A β αγ β A es un no terminal α, β y γ son cadenas de terminales y no terminales. α y β pueden ser vacíos, pero γ ha de ser distinto del vacío.

Teoría computacional 13 Clasificación de las gramáticas Prof. Edgardo Adrián Franco Martínez

Jerarquía de Chomsky

8

Gramáticas Tipo 1 (Continuación)
• Se denominan gramáticas dependientes del contexto, porque, como se observa, A puede ser...