Jerarquia de chomsky

1. Jerarquía de Jerarquía de
ChomskyChomsky
Roberto Daniel Pantoja TovarRoberto Daniel Pantoja Tovar
David del Ángel RodríguezDavid del Ángel Rodríguez
Karen Ramírez RodriguezKaren Ramírez Rodriguez

2. IntroducciónIntroducción
En lingüística la En lingüística la
jerarquía de jerarquía de
Chomsky es una Chomsky es una
clasificación clasificación
jerárquica de jerárquica de
distintos tipos de distintos tipos de
gramáticas formales gramáticas formales
que generan que generan
lenguajes formales. lenguajes formales.
Esta jerarquía fue Esta jerarquía fue
descrita por Noam descrita por Noam
Chomsky en 1956.Chomsky en 1956.

3. Expresiones regularesExpresiones regulares
Una expresión regular, a menudo llamada también Una expresión regular, a menudo llamada también
patrón, es una expresión que describe un patrón, es una expresión que describe un
conjunto de cadenas sin enumerar sus elementosconjunto de cadenas sin enumerar sus elementos
Para poder realizar expresiones regulares Para poder realizar expresiones regulares
debemos tomar en cuenta esto:debemos tomar en cuenta esto:
Sea S y R símbolos cualquieraSea S y R símbolos cualquiera
1. entonces R y/o S son expresiones regulares1. entonces R y/o S son expresiones regulares
2. R*S=RS es una expresión regular2. R*S=RS es una expresión regular
3. (R) es una expresión regular3. (R) es una expresión regular
4. nulo (vacío) es una expresión regular4. nulo (vacío) es una expresión regular
5. R*=a que R puede repetirse 0 muchas veces5. R*=a que R puede repetirse 0 muchas veces
6. R+=R(R*) R se repite 1 o más veces6. R+=R(R*) R se repite 1 o más veces
7. R?=R o 7. R?=R o vacío quierevacío quiere decir que R puede decir que R puede venir venir 1 1
vez o no venir nuncavez o no venir nunca

4. EjemplosEjemplos::
Supongamos que se desea generar una expresión regulara Supongamos que se desea generar una expresión regulara
que reconozca un numero de cédula que reconozca un numero de cédula
La solución seriaLa solución seria
Formato de no. De cedula =A1-12354544Formato de no. De cedula =A1-12354544
Expresión regular que reconoce éste tipo de informaciónExpresión regular que reconoce éste tipo de información
LD-DD*LD-DD*
DondeDonde
L representa al conjunto de todas las letras del alfabetoL representa al conjunto de todas las letras del alfabeto
D representa el conjunto de todos los decimalesD representa el conjunto de todos los decimales
Ejemplo2Ejemplo2
Supongamos que se desea generar una expresión regular Supongamos que se desea generar una expresión regular
que reconozca números decimalesque reconozca números decimales
DD*.DD*DD*.DD*
Aquí decimos que puede venir un digito (D) seguido de otro Aquí decimos que puede venir un digito (D) seguido de otro
digito que puede venir 0 o muchas veces (D*) hágase notar digito que puede venir 0 o muchas veces (D*) hágase notar
que el (.) que se encuentra no es de concatenación sino que que el (.) que se encuentra no es de concatenación sino que
es el punto decimal, después de esto viene otro digito (D) es el punto decimal, después de esto viene otro digito (D)
obligatorio ya que no se acepta 3. ya que no seria un número obligatorio ya que no se acepta 3. ya que no seria un número
decimal.decimal.

5. Jerarquía de ChomskyJerarquía de Chomsky
Clasifico las gramáticas en 4 familias.Clasifico las gramáticas en 4 familias.
-Las no restringidas (Tipo Las no restringidas (Tipo
0)0)
-Sensibles al contexto (Tipo Sensibles al contexto (Tipo
1)1)
-Independientes del contexto (Tipo 2)Independientes del contexto (Tipo 2)
-Gramáticas Regulares (Tipo Gramáticas Regulares (Tipo
3)3)

6. Descripción de los tipos de Descripción de los tipos de
jerarquíasjerarquías

7. Tipo3: lenguajes Tipo3: lenguajes
regularesregulares
Estos tipos de lenguajes se resuelven Estos tipos de lenguajes se resuelven
mediante autómatas finitos.mediante autómatas finitos.
CaracterísticasCaracterísticas
Del lado derecho de cada producción debe Del lado derecho de cada producción debe
empezar con un símbolo terminalempezar con un símbolo terminal
Ejemplo:Ejemplo:
Con éste tipo de lenguaje se hacen los scannersCon éste tipo de lenguaje se hacen los scanners

8. Tipo2: Libres o Tipo2: Libres o
Independientes de contextoIndependientes de contexto
Estos tipos de lenguajes se resuelven mediante Estos tipos de lenguajes se resuelven mediante
autómatas descendentesautómatas descendentes
CaracterísticasCaracterísticas
Del lado derecho de cada producción puede Del lado derecho de cada producción puede
empezar con un símbolo terminal o con un no empezar con un símbolo terminal o con un no
terminalterminal
Los lenguajes regulares también se pueden Los lenguajes regulares también se pueden
resolver mediante autómatas descendentesresolver mediante autómatas descendentes
Ejemplo:Ejemplo:
Con éste tipo de lenguaje se programa los parser en un compiladorCon éste tipo de lenguaje se programa los parser en un compilador

9. Tipo1: Sensibles o Tipo1: Sensibles o
Dependientes de contextoDependientes de contexto
Estos tipos de lenguajes se resuelven mediante Estos tipos de lenguajes se resuelven mediante
autómatas lineales limitadosautómatas lineales limitados
CaracterísticasCaracterísticas
Del lado derecho de cada producción puede Del lado derecho de cada producción puede
empezar con un símbolo terminal o con un no empezar con un símbolo terminal o con un no
terminal y del lado izquierdo puede empezar con terminal y del lado izquierdo puede empezar con
más de un símbolo no terminal.más de un símbolo no terminal.
RestricciónRestricción
El número de no terminales del lado izquierdo de El número de no terminales del lado izquierdo de
la producción debe ser menor o igual al número de la producción debe ser menor o igual al número de
símbolos del lado derechosímbolos del lado derecho
NotaNota
Los lenguajes regulares y los libres de contexto Los lenguajes regulares y los libres de contexto
también se pueden resolver mediante autómatas también se pueden resolver mediante autómatas
lineales limitados.lineales limitados.

10. Ejemplo:Ejemplo:
Con éste tipo de lenguajes se hacen los parser de un compilador.Con éste tipo de lenguajes se hacen los parser de un compilador.
Un analizador sintáctico (en inglés Un analizador sintáctico (en inglés parserparser) es una de las partes ) es una de las partes
de de
un compilador que transforma su entrada en un árbol de un compilador que transforma su entrada en un árbol de
derivación.derivación.
El análisis sintáctico convierte el texto de entrada en otras El análisis sintáctico convierte el texto de entrada en otras
estructuras (comúnmente árboles), que son más útiles para el estructuras (comúnmente árboles), que son más útiles para el
posterior análisis y capturan la jerarquía implícita de la entrada.posterior análisis y capturan la jerarquía implícita de la entrada.

11. Tipo0: Recursivamente Tipo0: Recursivamente
enumerableenumerable
Estos tipos de lenguajes se resuelven mediante Estos tipos de lenguajes se resuelven mediante
maquinas de Turínmaquinas de Turín
CaracterísticasCaracterísticas
Del lado derecho de cada producción puede Del lado derecho de cada producción puede
empezar con un símbolo terminal o con un no empezar con un símbolo terminal o con un no
terminal y del lado izquierdo puede empezar con terminal y del lado izquierdo puede empezar con
más de un símbolo no terminal.más de un símbolo no terminal.
Restricción Restricción
No tiene ninguna restricción solamente que del No tiene ninguna restricción solamente que del
lado izquierdo debe haber por lo menos un lado izquierdo debe haber por lo menos un
símbolo no terminalsímbolo no terminal
NotaNota
Todos los demás tipos de lenguajes también se Todos los demás tipos de lenguajes también se
pueden resolver mediante maquinas de Turínpueden resolver mediante maquinas de Turín

12. Ejemplo:Ejemplo:
Con éste tipo de lenguajes se hacen los parser de un compiladorCon éste tipo de lenguajes se hacen los parser de un compilador