Gramáticas Libres Regulares vs Contexto

Creo que lo que quieres pensar son los varios lemmata 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 las lenguas regulares , lo que dice, esencialmente, es que cualquier lengua regular se puede dividir en tres partes, x , y, and z, where all instances of the language are in xy*z (where * is Kleene repetition, ie, 0 or more copies of y.) Básicamente tienes un "no terminal" que se puede expandir.

Ahora, ¿qué pasa con los lenguajes libres de contexto? Hay un análogo lema de bombeo para lenguajes libres de contexto que rompe las cadenas en el 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 pueden replicar, o bombear, siempre y cuando tengas 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 lenguaje definidos por una gramática formal

● abc

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

● sustituido por grupos de símbolos terminales de acuerdo con las normas de producción

● ABC

Gramática regular: derecha o izquierda gramática regular gramática regular correcta, todas las reglas obedecen a 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

Izquierda 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 es 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 único símbolo no terminal

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

Expresiones regulares

• Base del análisis léxico
• Representan idiomas regulares

Gramáticas libres de Contexto

• Base del 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 sola variable; el lado derecho no está restringido 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 una asignación V
la gramática regular es lineal a la derecha o a la 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 Context Free Languages set también contiene Regular Languages set

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 que 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 una gramática ambigua porque dos árboles de análisis.

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 DCFL son LL(1) Gramática y todos LL(1) es LR(1) por lo que nunca es ambiguo. así que DCFG nunca es 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 ambiguo.

Nota: RL nunca será inherentemente ambiguo.

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

Un grammer regular nunca es ambiguo porque es lineal a la izquierda o lineal a la derecha, por lo que no podemos hacer dos árboles de decisión para grammer regular, por lo que siempre es inequívoco.pero othert que gramática regular todos son puede o no puede ser regular