Gramáticas regulares vs libres de contexto

Estoy estudiando para mi examen de lenguajes de computación , y hay una idea que tengo problemas para entender.

Entendí que las gramáticas regulares son más simples y no pueden contener ambigüedad, pero no pueden realizar 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 tengo problemas es entender cómo puedo derivar todo lo anterior sabiendo que los no terminales gramaticales regulares se pueden asignar a un terminal o un no terminal seguido de un terminal o que un no terminal sin contexto se asigna a cualquier combinación de terminales y no terminales .

¿Alguien puede ayudarme a poner todo esto junto?

La gramática regular es lineal hacia la derecha o hacia la izquierda, 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, tiene la forma,

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

Puede ver claramente que los palíndromos no se pueden expresar en la gramática regular, ya que deben ser lineales a la derecha o a la izquierda y, como tal, no pueden tener un no terminal en ambos lados.

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

Creo que lo que quieres pensar son los distintos lemas de bombeo. Un lenguaje regular puede ser reconocido por un autómata finito. Un lenguaje libre de 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 regulares , lo que dice, esencialmente, es que cualquier idioma regular se puede dividir en tres partes, x , y y z , donde todas las instancias del idioma 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 puede expandirse.

Ahora, ¿qué pasa con los lenguajes libres de contexto? Existe un lema de bombeo análogo para los lenguajes sin contexto que divide las cadenas 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 .

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

● símbolos elementales del idioma definidos por una gramática formal

● abc

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

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

● ABC

gramática regular: gramática regular derecha o izquierda gramática regular derecha, todas las reglas obedecen las formas

1. B → a donde B es un no terminal en N y a es un terminal en Σ
2. B → aC donde B y C están en N y a está en Σ
3. 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 las formas

1. A → a donde A es un no terminal en N y a es un terminal en Σ
2. A → Ba donde A y B están en N y a está en Σ
3. 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 tiene la forma V → w

○ V es un símbolo no terminal único

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

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 lineal derecha, pero no gramática lineal media.

Como sabemos, todos los RG son gramática lineal, pero solo la gramática lineal izquierda o 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 Parse o Un LMD y Un RMD pero ambos producen un árbol Parse diferente.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

esta gramática es gramática ambigua porque dos árboles de análisis.

CFG: - Una gramática que se dice 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 todo LL (1) es LR (1), por lo que nunca sea ambiguo. entonces DCFG es Nunca sea ambiguo.

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

CFL: CFl Puede o no ambiguo.

Nota: RL nunca sea intrínsecamente ambiguo.

Expresiones regulares

• Base del análisis léxico
• Representar lenguajes regulares

Gramáticas libres de contexto

• Base de análisis
• Representar construcciones del lenguaje

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 única variable; el lado derecho no tiene restricciones y puede ser cualquier secuencia de terminales y variables). Podemos definir una gramática como una tupla de 4 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 La
gramática regular V es lineal hacia la derecha o hacia la izquierda, mientras que la gramática libre de contexto es básicamente cualquier combinación de terminales y no terminales. por 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 sin contexto también contiene el conjunto de idiomas regulares

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

una gramática regular nunca es ambigua porque es lineal a la izquierda o lineal a la derecha, por lo que no podemos hacer dos árboles de decisión para la gramática regular, por lo que siempre es inequívoco. pero aparte de la gramática regular, todas pueden o no ser regulares.