Regular vs Contexto gramáticas livres

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

Pergunta

Estou estudando para o meu linguagens de computação teste, e há uma idéia que eu estou tendo problemas envolvendo minha cabeça em torno.

Eu entendi que gramática regular são mais simples e não pode conter a ambiguidade, mas não pode fazer um monte de tarefas que são necessárias para linguagens de programação. Eu também entendi que gramáticas livres de contexto permitir ambigüidade, mas permitem algumas coisas necessárias para linguagens de programação (como palíndromos).

O que eu estou tendo problemas com é entender como eu pode derivar todos os acima por saber que nonterminals gramática regular pode mapear a um terminal ou um não-terminal seguido por um terminal ou que uma ao contexto mapas gratuitos não terminais para qualquer combinação de terminais e não terminais.

Alguém pode me ajudar a colocar tudo isso junto?

Foi útil?

Solução

gramática regular é tanto linear direita ou esquerda, enquanto contexto livre gramática é basicamente qualquer combinação de terminais e não-terminais. Assim você pode ver que a gramática regular é um subconjunto de gramática livre de contexto.

Assim, para um palíndromo por exemplo, é do formulário, 

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

Você pode ver claramente que palíndromos não pode ser expresso em gramática regular, uma vez que precisa de ser direita ou linear esquerda e, como tal, não pode ter um não-terminal de ambos os lados.

Uma vez que gramáticas regulares são não-ambígua, há apenas uma regra de produção para um dado não-terminal, ao passo que não pode haver mais do que um no caso de uma gramática livre de contexto.

Outras dicas

Eu acho que o que você quer pensar são os vários lemas de bombeamento. A linguagem regular pode ser reconhecida por um autômato finito. Uma linguagem livre de contexto requer uma pilha, e uma linguagem sensível ao contexto requer duas pilhas (que é equivalente a dizer que requer uma máquina de Turing completo.)

Assim, se pensarmos sobre o lema bombeamento para linguagens regulares , o que diz, essencialmente, , é que qualquer linguagem regular pode ser dividido em três partes, x , y e z , onde todas as instâncias da linguagem estão em xy * z (em que * é Kleene repetição, isto é, 0 ou mais cópias de y .) é basicamente tem uma "não-terminal", que pode ser expandida.

Agora, o que acontece com linguagens livres de contexto? Há um bombeamento lema análoga para linguagens livres de contexto que quebra o cordas na língua em cinco partes, uvxyz , e onde todas as instâncias da linguagem estão em uv i xy i z , para i = 0. Agora, você tem dois "não terminais" que podem ser replicadas, ou bombeado, , desde que você tem o mesmo número .

A diferença entre regular e gramática livre de contexto: (N, S, P, S): terminais, não terminais, produções, estado inicial símbolos terminais

? símbolos elementares da linguagem definidas por uma gramática formal

? abc

símbolos não-terminal (ou variáveis ??sintáticas)

? substituídos por grupos de símbolos terminais de acordo com as regras de produção

? ABC

gramática regular: direita ou esquerda gramática regular gramática regular direita, todas as regras obedecer as formas

  1. B ? um em que B é um não-terminal em N e um é um terminal em S
  2. B ? CA onde B e C são em N e um está em S
  3. B ? e em que B é N e em e indica a cadeia vazia, isto é, a cadeia de caracteres de comprimento 0

esquerdo gramática regular, todas as regras obedecer as formas

  1. A ? um em que A é um não-terminal em N e um é um terminal em S
  2. A ? Ba em que A e B são em N e um está em S
  3. A ? e em que A é N e em e é a cadeia vazia

contexto livre gramática (CFG)

? gramática formal em que cada regra de produção é da forma V ? w

? V é um símbolo não-terminal

? W é uma cadeia de terminais e / ou não-terminais (w pode estar vazia)

Expressões Regulares

  • Bases de análise léxica
  • Representar linguagens regulares

Contexto gramáticas livres

  • Bases de análise
  • representam construções de linguagem

enter descrição da imagem aqui

gramática regular: - gramática contendo produção da seguinte forma é RG: 

V->TV or VT
V->T

onde V = variável e T = terminal de

RG pode ser deixado Linear gramática ou Direita Liner gramática, mas não Oriente linear gramática.

Como sabemos todos RG são Linear Grammar mas apenas Linear Esquerda ou Direita Gramática Linear são RG.

A gramática regular pode ser ambíguo. 

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

ambíguo Gramática: -. para uma string x seu existir mais de dois árvore de análise diferente produzir mais do que uma árvore de análise um LMD ou mais de RMD ou ou Uma LMD e One RMD mas 

                S                   S

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

Essa gramática é ambígua Grammar porque dois árvore de análise.

CFG: - Uma gramática dito ser CFG se sua produção está em forma: 

   V->@   where @ belongs to (V+T)*

DCFL: - como sabemos todos DCFL são LL (1) Gramática e todos LL (1) é LR (1), por isso é nunca ser ambíguo. assim DCFG é nunca ser ambíguo.

Também sabemos tudo RL são DCFL tão RL não ser ambíguo. Note-se que RG pode ser ambígua, mas RL não.

CFL:. CFL pode ou não ambígua

Nota:. RL não ser inerentemente ambígua

A gramática é livre de contexto se todas as regras de produção têm a forma: A (isto é, o lado esquerdo de uma regra só pode ser uma única variável, o lado direito é irrestrito e pode ser qualquer seqüência de terminais e variáveis) . Podemos definir uma gramática de um 4-tuplo em que V é um conjunto finito (variáveis), _ é um conjunto finito (terminais), S é a variável de início, e R é um conjunto finito de regras, cada uma das quais é um mapeamento V
gramática regular ou é linear direita ou esquerda, enquanto contexto livre gramática é basicamente qualquer combinação de terminais e não-terminais. portanto, podemos dizer que a gramática regular é um subconjunto da gramática livre de contexto. Após estas propriedades, podemos dizer que Contexto Grátis Idiomas definir também contém conjunto de linguagens regulares

Basicamente gramática regular é um subconjunto de contexto livre gramática, mas nós não podemos dizer qualquer contexto livre gramática é uma gramática regular. Principalmente contexto gramática livre é gramática ambígua e regular pode ser ambígua.

a gramática regular, nunca é ambígua porque ele é ou deixou linear ou linear direita, de modo que nós não podemos fazer dois árvore de decisão para a gramática regular, por isso é sempre othert unambiguous.but de gramática regular todos são podem ou não ser regular

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top