Jerarquía de Chomsky Flashcards
¿Qué es la Jerarquía de Chomsky?
Establece una clasificación de 4 tipos de gramática formales, que a su vez, generan 4 tipos diferentes de LF.
¿Cuáles son los tipos que hay?
TIPO 3,2,1,0
¿Qué tipo de GF y LF genera el Tipo 3?
El tipo 3 genera la Gramática Regular (GR) y a su vez el Lenguaje Regular (LR).
¿Qué tipo de GF y LF genera el Tipo 2?
El tipo 2 genera la Gramática Independiente del Contexto (GIC) y a su vez el Lenguaje Independiente del Contexto (LIC).
¿Qué tipo de GF y LF genera el tipo 1?
El tipo 1 genera la Gramática Dependiente del Contexto (GDC) y el Lenguaje Dependiente del Contexto (LDC).
¿Qué tipo de GF y LF genera el Tipo 0?
El tipo 0 genera la gramática irrestricta (GI) y el Lenguaje Irrestricto (LI).
¿Cuáles son las restricciones de una Gramática Regular (GR)?
- El lado izquierdo debe tener un solo no terminal
- El lado derecho debe estar formado por :
- Un solo terminal
- Un terminal seguido por un no terminal (o viceversa)
- Épsilon
Ejemplo : G = ({S,T}, {a,b}, {S → aT, T → a, T → b},S)
¿Qué es una producción recursiva? (Parte de GR)
Es aquella producción en las que el no terminal que figura en el lado izquierdo también figura en el lado derecho. Pueden generar LR infinitos.
“Es como si se llamara a sí misma”.
Ejemplo : L = {aⁿb / n ≥ 1}
S → aS | aT
T → b
¿Qué es una Gramática Quasi-Regular (GQR)?
Es similar a una GR, pero el conjunto de terminales es reemplazado por un no terminal en una o varias producciones.
Ejemplo: Sea la GQR con las siguientes producciones:
S → N | NS
N → a | b | c
GR: S → a | b | c | aS | bS | cS
¿La GQR puede ser reescrita como una GR?
Sí, ya que la GQR abrevia la escritura de una GR.
¿Cuándo se dice que las gramáticas formales son equivalentes?
Se dice que son equivalentes cuando generan el MISMO LF.
¿Cuáles son las restricciones de una GIC?
- El lado izquierdo debe estar formado por un no terminal.
- El lado derecho no tiene restricciones.
Ejemplo : S → ba (es una GIC válida, pero no una GR ya que su lado derecho está formado por 2 terminales consecutivos).
¿Puede aplicarse la recursividad a las GIC?
Sí, las GIC también generan LICs infinitos.
Ejemplo : S → aSb | a
¿Cuáles son las restricciones de una GI?
No tienen restricciones de ningún tipo en sus lados. (v+t)*
A → B (alfa produce a beta).
Pero Alfa debe ser SI o SI distinto de ÉPSILON.
¿Cuáles son las restricciones de una GDC?
Es una gramática irrestricta.
Su única restricción está en las longitudes: | α | ≤ | β |.
