Regular vs gramáticas libres de contexto

StackOverflow https://stackoverflow.com/questions/559763

Pregunta

Estoy estudiando para mi lenguajes informáticos prueba, y no hay una idea que estoy teniendo problemas de envolver mi cabeza alrededor.

entendí que gramáticas regulares son más simples y no puede contener la ambigüedad, pero no se puede hacer un montón de tareas que se requieren para lenguajes de programación. También entendí que gramáticas libres de contexto permiten la ambigüedad, pero permiten que algunas cosas necesarias para lenguajes de programación (como palíndromos).

Lo que estoy teniendo problemas con la comprensión de cómo se pueda derivar de todo lo anterior al saber que no terminales gramática regular puede asignar a un terminal o un no terminal seguido de un terminal o que un contexto- Los mapas no terminales gratis a cualquier combinación de terminales y no terminales.

Puede alguien ayudarme a poner todo esto junto?

¿Fue útil?

Solución

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

Así que para un palíndromo por ejemplo, es de la forma: 

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

Se puede ver claramente que los palíndromos no pueden expresarse en gramática regular, ya que tiene que ser derecha o izquierda lineal y como tal no puede tener un no terminal en ambos lados.

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

Otros consejos

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

Por lo tanto, si pensamos en los href="http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages" lema del bombeo para lenguajes regulares , lo que dice, en esencia , es que cualquier lenguaje regular se puede dividir en tres piezas, x , y y z , donde todas las instancias de la lengua están en xy * z (donde * es Kleene repetición, es decir, 0 o más copias de y .) es, básicamente, tienen un "no terminal" que se puede ampliar.

Ahora, ¿qué pasa con lenguajes independientes del contexto? Hay una bombeo lema para lenguajes libres de contexto que rompe las cadenas en el idioma en cinco partes, uvxyz , y donde todas las instancias de la lengua están en uv i xy i z , para i ≥ 0. Ahora, usted tiene dos "no terminales" que pueden ser replicados o bombeado, , siempre y cuando tenga el mismo número .

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

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

● abc

símbolos No Terminales (o variables sintácticas)

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

● ABC

gramática regular: derecha o izquierda gramática regular gramática regular correcta, 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 son en N y A está en Σ
  3. B → ε donde B es en N y ε indica 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 el 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ía)

Las expresiones regulares

  • Bases de análisis léxico
  • Representar lenguajes regulares

Contexto Gramáticas

  • Bases de análisis
  • Representar construcciones del lenguaje

introducir descripción de la imagen aquí

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

V->TV or VT
V->T

donde V = variable y T = el terminal

RG se pueden dejar gramática lineal o Derecha Liner gramática, pero no la gramática lineal Medio.

Como sabemos todos RG son lineales Gramática pero sólo Izquierda o Derecha Lineal Lineal Gramática se RG.

Una gramática regular puede ser ambigua. 

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

gramática ambigua: -. para una cadena x su existir más de un LMD o más de RMD o más de un árbol de análisis sintáctico o un LMD y un RMD pero ambos producen diferentes árbol de análisis 

                S                   S

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

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

CFG: - Una gramática dice que 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 se ser ambigua. por lo que se DCFG Nunca ser ambigua.

También sabemos todo RL son tan DCFL RL no sea ambigua. Tenga en cuenta que RG puede ser ambigua, pero no RL.

CFL:. CFL puede o no ambigua

Nota:. RL no ser inherentemente ambiguo

Una gramática es libre de contexto si todas las reglas de producción tienen la forma: A (es decir, el lado izquierdo de una regla sólo puede haber una sola variable; el lado derecho es sin restricciones y puede ser cualquier secuencia de terminales y variables) . Podemos definir una gramática como 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 uno de los cuales es un mapeo V
gramática regular es o bien lineal derecho o izquierdo, mientras contexto gramática libre 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 idiomas del juego también contiene Regular Idiomas establecidos

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

una gramática regular es no ambigua, ya que es bien lineal o lineal izquierda derecha de modo que no puede hacer dos árbol de decisión para la gramática regular, de manera que siempre es unambiguous.but othert de gramática regular todos son pueden ser o no ser regular

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top