Regular vs Contexto Gramáticas gratis

Estoy estudiando para mi prueba de lenguajes de computación, y hay una idea que estoy teniendo problemas para resolver.Regular vs Contexto Gramáticas gratis

Entiendo que 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 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 con la comprensión de cómo se pueda derivar de todo lo anterior al saber que no terminales gramática regular pueden asignar a un terminal o un no terminal seguido de un terminal o que un contexto libre de mapas no terminales a cualquier combinación de terminales y no terminales.

¿Alguien me puede ayudar a armar todo esto?

Fuente

2009-02-18 Jason Baker

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, 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 a la derecha oa la izquierda lineal y, como tal, no puede tener un no terminal en ambos lados.

Dado que las gramáticas regulares no son ambiguas, solo existe 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.

Fuente

2009-02-18 05:35:47 Sujoy

Primero: las gramáticas regulares pueden ser ambiguas (ejemplo de Kai Kuchenbecker: S -> aA | aB, B -> a, A -> a). Lo único es que solo hay una forma de posicionar los nodos en el árbol de sintaxis (por ejemplo, la ambigüedad de asociatividad no existe cuando se usa una gramática común). Segundo: Puede haber más de un lado derecho en un terminal no terminal (A -> a, A -> aA; y wikipedia incluso incluye épsilon como tercera alternativa: http://en.wikipedia.org/wiki/ Regular_grammar) – user764754

ambigüedad viene cuando una oración se puede derivar de su gramática en más de una ruta de derivación.el simple hecho de tener más de una regla de producción para un terminal no hace que la gramática sea ambigua. – Sujoy

Este ejemplo es realmente incorrecto. Si imaginamos que las reglas completas son 'A-> a | c' y 'B-> b' entonces esta gramática permite no palíndromos. Por ejemplo, podría producir: 'S-> ABA-> aBA-> abA-> abc'. El problema es que no queremos producir dos variables en la primera regla, sino dos terminales. Una posibilidad para una gramática que permite palíndromos es: 'S -> aSa | bSb | a | b' – gdiazc

Creo que lo que quiere 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 pumping lemma for regular languages, lo que dice, esencialmente, es que cualquier lenguaje regular se puede dividir en tres piezas, x, y, y z, en 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). Básicamente tiene un "no terminal" que se puede expandir.

Ahora, ¿qué pasa con los idiomas libres de contexto? Hay un análogo pumping lemma for context-free languages que rompe las cadenas en el lenguaje en cinco partes, uvxyz, y donde todas las instancias de la lengua están en UV ⁱ xy ⁱ z, para i ≥ 0. Ahora, usted tiene dos "no terminales" que se pueden replicar, o bombear, , siempre que tenga el mismo número.

Fuente

2009-02-18 05:36:43

Un lenguaje sensible al contexto no requiere una máquina Turing completa. Un autómata lineal limitado es suficiente. Esta es una máquina de Turing cuya cinta es finita, el tamaño está limitado por alguna función lineal en la cadena de entrada. –

-4

una gramática común nunca es ambigua porque se deja lineal o lineal derecha, por lo que no podemos hacer dos árboles de decisión para la gramática normal, por lo que siempre es inequívoca.pero, aparte de la gramática regular, todos pueden ser o no ser regulares

Fuente

2011-04-21 09:46:46 dinesh

-1 Una gramática regular * puede * ser ambigua. – NullUserException

@dinesh Una gramática regular puede ser ambigua. Recuerde que una gramática es ambigua si existen dos árboles de sintaxis diferentes y si un árbol de sintaxis está etiquetado. Por lo tanto, los árboles isomorfos son árboles diferentes. Es decir. una gramática simple como S -> aA | aB, B -> a, A -> a es ambiguo ya que existen dos árboles de sintaxis para la palabra 'aa' que son isomorfos pero diferentes. –

Una gramática no tiene 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 mapeo V
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 Context Free idiomas del juego también contiene Regular Idiomas establecen

Fuente

2011-06-30 15:28:41

expresiones regulares

Bases de análisis léxico
Representar lenguajes regulares

de contexto libre de gramáticas

Bases de análisis
representar el lenguaje construye

enter image description here

Fuente

2013-01-16 05:07:36

Esto no explica nada. – Zimano

-1

Básicamente 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, la gramática libre de contexto es ambigua y la gramática regular puede ser ambigua.

Fuente

2013-03-03 14:51:22

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

V->TV or VT 
V->T

donde V = variable y T = terminal de

RG se pueden dejar Gramática lineal o Derecha Liner gramática, pero no Gramática lineal media.

Como sabemos, todos los RG son gramática lineal, pero solo la gramática lineal izquierda o derecha son 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 sintáctico.

   S     S 

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

este Grammar es ambiguo Grammar because two parse tree.

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 es 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.

Fuente

2013-07-26 20:07:38

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

● símbolos elementales de la lengua definidas por un oficial gramática

● abc

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

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

● ABC

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

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 el límite vacío g, es decir, la cadena de longitud 0

gramática regular izquierda, todas las reglas obedecen las formas

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

contexto gramática libre (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ío)

Fuente

2015-05-13 19:29:42 stringRay2014

Regular vs Contexto Gramáticas gratis

Respuesta

Cuestiones relacionadas