Please enable JavaScript.
Coggle requires JavaScript to display documents.
la gramática libre de contexto - Coggle Diagram
la gramática libre de contexto
Definición
En lingüística e informática, una gramática libre de contexto (o de contexto libre) es una gramática formal en la que cada regla de producción es de la forma:
V → w
Donde V es un símbolo no terminal y w es una cadena de terminales y/o no terminales.
Definición formal
Así como cualquier gramática formal, una gramática libre de contexto puede ser definida mediante la 4-tupla:
G=(Vt,Vn,P,S)} donde:
Vt es un conjunto finito de terminales
Vn es un conjunto finito de no terminales
P es un conjunto finito de producciones
S € Vn el denominado Símbolo Inicial
los elementos de P son de la forma
Vn →(Vt ∪ Vn)*
Derivaciones
Una regla de producción puede considerarse como equivalente a una regla de rescritura, donde el no terminal de la izquierda es sustituido por la pseudocadena del lado derecho de la producción. Podemos considerar que una pseudocadena es cualquier secuencia de terminales y/o no terminales
Derivación por la izquierda:
es aquella en la que la reescritura se realiza sobre el no terminal más a la izquierda de la pseudocadena de partida.
Derivación por la derecha:
es aquella en la que la reescritura se realiza sobre el no terminal más a la derecha de la pseudocadena de partida.
Formas Formales
Una gramática que no genera la cadena vacía puede ser transformada en una equivalente (que genera el mismo lenguaje)
forma normal de Chomsky
forma normal de Greibach.
Cerradura de ⇒
• Definimos ∗⇒ como la cerradura reflexiva y transitiva de ⇒. Lo que quiere decir es que usamos uno a mas pasos de derivación.
Ideas:
• Base:
Sea α ∈ (V ∪ T)∗, entonces α∗ ⇒ α(ósea que cada cadena se deriva a sı misma).
•Induccion :
Si α ∗⇒ β, y β ⇒ γ, entonces α ∗⇒ γ
Ejemplo :
