Pregunta Gramáticas regulares versus gramáticas gratuitas


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

lo entendí 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í eso gramáticas libres de contexto permite la ambigüedad, pero permite 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 sabiendo que regular gramática no terminales puede mapear a un terminal o un no terminal seguido de un terminal o que un mapa sin terminal sin contexto se asigna a cualquier combinación de terminales y no terminales.

¿Alguien puede ayudarme a armar todo esto?


75
2018-02-18 03:46


origen


Respuestas:


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.


58
2018-02-18 05:35



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 bombeo lema para idiomas regulares, lo que dice, esencialmente, es que cualquier lenguaje regular se puede dividir en tres partes, X, yy z, donde están todas las instancias del lenguaje 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 análogo bombeo lema para idiomas sin contexto que rompe las cuerdas en el lenguaje en cinco partes, uvxyz, y donde están todas las instancias del lenguaje uvyoxyyoz, para i ≥ 0. Ahora, tienes dos "no terminales" que pueden ser replicados, o bombeados, siempre y cuando tengas el mismo número.


50
2018-02-18 05:36



La diferencia entre regular y gramática libre de 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

  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 a los formularios

  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 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)


8
2018-05-13 19:29



Expresiones regulares

  • Bases del análisis léxico
  • Representar idiomas regulares

Gramáticas libres de contexto

  • Bases de análisis
  • Representar construcciones de lenguaje

enter image description here


4
2018-01-16 05:07



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


3
2018-06-30 15:28



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 Parse o un LMD y un RMD, pero ambos producen un árbol de Parse 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.


3
2017-07-26 20:07



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.


-1
2018-03-03 14:51



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.


-4
2018-04-21 09:46