context free grammar - resueltos - Gramáticas regulares versus gramáticas gratuitas

lenguajes y automatas (8)

Estoy estudiando para mi examen de idiomas de computación , y hay una idea de la que estoy teniendo problemas.

Comprendí que las gramáticas regulares son más simples y no pueden contener ambigüedades, pero no pueden hacer muchas tareas que son necesarias para los lenguajes de programación. También entendí que las gramáticas libres de contexto permiten la ambigüedad, pero permiten algunas cosas necesarias para los lenguajes de programación (como los palíndromos).

Lo que estoy teniendo problemas es entender cómo puedo derivar todo lo anterior al saber que los elementos no terminales regulares de la gramática pueden asignarse a un terminal o un terminal no terminal seguido de un terminal o que un mapa no terminal sin contexto se asigna a cualquier combinación de terminales y no terminales .

¿Alguien puede ayudarme a armar todo esto?

Básicamente, la gramática regular es un subconjunto de la gramática libre de contexto, pero no podemos decir que la gramática gratuita Every Context sea una gramática regular. Principalmente, la gramática libre de contexto es ambigua y la gramática regular puede ser ambigua.

Creo que lo que quieres pensar son los diversos lemma de bombeo. Un lenguaje regular puede ser reconocido por un autómata finito. Un lenguaje sin contexto requiere una pila, y un lenguaje sensible al contexto requiere dos pilas (lo que equivale a decir que requiere una máquina de Turing completa).

Entonces, si pensamos en el lema de bombeo para los lenguajes comunes , lo que dice, esencialmente, es que cualquier lenguaje regular se puede dividir en tres partes, x , y y z , donde todas las instancias del lenguaje están en xy * z (donde * es la repetición de Kleene, es decir, 0 o más copias de y ). Básicamente tiene un "no terminal" que se puede expandir.

Ahora, ¿qué pasa con los idiomas libres de contexto? Hay un lema de bombeo análogo para lenguajes sin contexto que divide las cuerdas del lenguaje en cinco partes, uvxyz , y donde todas las instancias del lenguaje están en uv ⁱ xy ⁱ z , para i ≥ 0. Ahora, tienes dos "no terminales" "que se puede replicar o bombear, siempre que tenga el mismo número .

Expresiones regulares

Bases del análisis léxico
Representar idiomas regulares

Gramáticas libres de contexto

Bases de análisis
Representar construcciones de lenguaje

La gramática regular es lineal o derecha, mientras que la gramática libre de contexto es básicamente cualquier combinación de terminales y no terminales. Por lo tanto, puede ver que la gramática regular es un subconjunto de la gramática libre de contexto.

Entonces, para un palíndromo, por ejemplo, es de la forma,

S->ABA A->something B->something

Puede ver claramente que los palíndromos no se pueden expresar en la gramática normal, ya que debe ser lineal o bien lineal o izquierdo y, como tal, no puede tener un terminal no terminal en ambos lados.

Como las gramáticas regulares no son ambiguas, solo hay una regla de producción para un terminal no terminal determinado, mientras que puede haber más de una en el caso de una gramática libre de contexto.

Una gramática está libre de contexto si todas las reglas de producción tienen la forma: A (es decir, el lado izquierdo de una regla solo puede ser una variable única, el lado derecho no tiene restricciones y puede ser cualquier secuencia de terminales y variables). Podemos definir una gramática como una 4-tupla donde V es un conjunto finito (variables), _ es un conjunto finito (terminales), S es la variable de inicio, y R es un conjunto finito de reglas, cada una de las cuales es un mapeo V
la gramática regular es lineal derecha o izquierda, mientras que la gramática libre de contexto es básicamente cualquier combinación de terminales y no terminales. por lo tanto, podemos decir que la gramática regular es un subconjunto de la gramática libre de contexto. Después de estas propiedades, podemos decir que el conjunto de idiomas libres de contexto también contiene el conjunto de idiomas regulares

una gramática regular nunca es ambigua porque se deja lineal o lineal derecha, por lo que no podemos hacer dos árboles de decisión para las gramáticas regulares, por lo que siempre es inequívoco. Pero a excepción de la gramática común, todos pueden ser regulares o no.

Gramática regular: la gramática que contiene la producción de la siguiente manera es RG:

V->TV or VT V->T

donde V = variable y T = terminal

RG puede ser Gramática lineal izquierda o Gramática derecha del trazador, pero no Gramática lineal intermedia.

Como sabemos, todos los RG son Gramática lineal, pero solo Gramática lineal izquierda o Gramática lineal derecha son RG.

Una gramática regular puede ser ambigua.

S->aA|aB A->a B->a

Gramática ambigua: para una cadena x existen más de un LMD o más de RMD o más de un árbol de análisis o un LMD y un RMD, pero ambos producen un árbol de análisis diferente.

S S / / / / a A a B / / a a

esta Gramática es Gramática ambigua porque dos árbol de análisis sintáctico.

CFG: una gramática que se dice que es CFG si su producción está en forma:

V->@ where @ belongs to (V+T)*

DCFL: - como sabemos, todos los DCFL son LL (1) Gramática y todos LL (1) son LR (1) por lo que nunca será ambiguo. entonces DCFG es Nunca ser ambiguo.

También sabemos que todos los RL son DCFL, por lo que RL nunca será ambiguo. Tenga en cuenta que RG puede ser ambiguo pero RL no.

CFL: CFl Puede o no ser ambiguo.

Nota: RL nunca será intrínsecamente ambiguo.

La diferencia entre gramática regular y sin contexto: (N, Σ, P, S): terminales, no terminales, producciones, estado inicial Símbolos terminales

● símbolos elementales del lenguaje definido por una gramática formal

● abc

Símbolos no terminales (o variables sintácticas)

● reemplazado por grupos de símbolos de terminal de acuerdo con las reglas de producción

● ABC

gramática regular: gramática regular derecha o izquierda gramática regular correcta, todas las reglas obedecen a los formularios

B → a donde B es un no terminal en N y a es un terminal en Σ
B → aC donde B y C están en N y a está en Σ
B → ε donde B está en N y ε denota la cadena vacía, es decir, la cadena de longitud 0

dejó la gramática regular, todas las reglas obedecen a los formularios

A → a donde A es un no terminal en N y a es un terminal en Σ
A → Ba donde A y B están en N y a está en Σ
A → ε donde A está en N y ε es la cadena vacía

gramática libre de contexto (CFG)

○ gramática formal en la que cada regla de producción es de la forma V → w

○ V es un símbolo único no terminal

○ w es una cadena de terminales y / o no terminales (w puede estar vacío)