Gramáticas regulares versus gramáticas livres de contexto

96

Estou estudando para o meu teste de linguagens de computação e há uma ideia que estou tendo problemas para entender.

Eu entendi que as gramáticas regulares são mais simples e não podem conter ambigüidade, mas não podem fazer muitas tarefas que são exigidas para linguagens de programação. Eu também entendi que gramáticas livres de contexto permitem ambigüidade, mas permitem algumas coisas necessárias para linguagens de programação (como palíndromos).

O que estou tendo problemas é entender como posso derivar todos os itens acima, sabendo que os não-terminais da gramática regular podem ser mapeados para um terminal ou um não-terminal seguido por um terminal ou que um não-terminal livre de contexto mapeia para qualquer combinação de terminais e não-terminais .

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

Jason Baker
fonte

Respostas:

70

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

Portanto, para um palíndromo, por exemplo, é da forma,

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

Você pode ver claramente que os palíndromos não podem ser expressos na gramática regular, pois precisam ser lineares à direita ou à esquerda e, como tal, não podem ter um não terminal em ambos os lados.

Como as gramáticas regulares não são ambíguas, existe apenas uma regra de produção para um determinado não terminal, enquanto pode haver mais de uma no caso de uma gramática livre de contexto.

Sujoy
fonte
13
Primeiro: gramáticas regulares podem ser ambíguas (exemplo de Kai Kuchenbecker: S -> aA | aB, B -> a, A -> a). A única coisa é que existe apenas uma maneira de posicionar os nós na árvore sintática (por exemplo, a ambigüidade de associatividade não existe quando uma gramática regular é usada). Segundo: pode haver mais de um lado direito para um não terminal (A -> a, A -> aA; e a wikipedia inclui até o epsilon como uma terceira alternativa: en.wikipedia.org/wiki/Regular_grammar )
usuário764754
1
a ambiguidade surge quando uma frase pode ser derivada de sua gramática em mais de um caminho de derivação. simplesmente ter mais de uma regra de produção para um não terminal não torna a gramática ambígua
Sujoy
11
Este exemplo está realmente errado. Se imaginarmos que são as regras completas A-> a | ce B->bentão esta gramática permite não palíndromos. Por exemplo, eu poderia produzir: S->ABA->aBA->abA->abc. O problema é que não queremos produzir duas variáveis ​​na primeira regra, mas sim dois terminais. Uma possibilidade para uma gramática que permite palíndromos é:S -> aSa | bSb | a | b
gdiazc
Existem palíndromos que podem ser expressos em uma gramática regular: os palíndromos que consistem em um único caractere. Por exemplo, S -> aSa | ee a(aa)*aambos descrevem uma linguagem regular. Isso mostra que um CFG pode descrever uma linguagem regular, mesmo que viole a linearidade esquerda ou direita. É certo que este é um palíndromo não tão óbvio ..
Martijn
Venha para pensar sobre isso, essa resposta está realmente errada. Diz que a gramática "livre de contexto" é basicamente qualquer combinação de terminais e não terminais. "No entanto, tu ^ nvw ^ mxy ^ kz é uma combinação de terminais e não terminais, mas não livre de contexto.
Charlie Martin
58

Acho que você quer pensar nos vários lemas do bombeamento. Uma 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 (o que é equivalente a dizer que requer uma máquina de Turing completa).

Então, se pensarmos no lema do bombeamento para linguagens regulares , o que ele diz, essencialmente, é que qualquer linguagem regular pode ser dividida em três partes, x , y e z , onde todas as instâncias da linguagem estão em xy * z (onde * é a repetição de Kleene, ou seja, 0 ou mais cópias de y .) Você basicamente tem um "não terminal" que pode ser expandido.

Agora, e quanto às linguagens livres de contexto? Há um lema de bombeamento análogo para linguagens livres de contexto que divide as strings na linguagem 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 pode ser replicado ou bombeado, desde que você tenha o mesmo número .

Charlie Martin
fonte
10
Uma linguagem sensível ao contexto não requer uma máquina de Turing completa. Um autômato linear limitado é suficiente. Esta é uma máquina de Turing cuja fita é finita, o tamanho é limitado por alguma função linear na string de entrada.
Dave Clarke
16

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

● símbolos elementares da linguagem definidos por uma gramática formal

● abc

Símbolos não terminais (ou variáveis ​​sintáticas)

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

● ABC

gramática regular: gramática regular direita ou esquerda gramática regular direita, todas as regras obedecem às formas

  1. B → a onde B é um não terminal em N e a é um terminal em Σ
  2. B → aC onde B e C estão em N e a está em Σ
  3. B → ε onde B está em N e ε denota a string vazia, ou seja, a string de comprimento 0

deixou a gramática regular, todas as regras obedecem às formas

  1. A → a onde A é um não terminal em N e a é um terminal em Σ
  2. A → Ba onde A e B estão em N e a está em Σ
  3. A → ε onde A está em N e ε é a string vazia

gramática livre de contexto (CFG)

○ gramática formal em que toda regra de produção é da forma V → w

○ V é um único símbolo não terminal

○ w é uma string de terminais e / ou não terminais (w pode estar vazio)

stringRay2014
fonte
5

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

V->TV or VT
V->T

onde V = variável e T = terminal

RG pode ser Gramática do Linear Esquerdo ou Gramática do Liner Direito, mas não Gramática do Linear Médio.

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

Uma gramática regular pode ser ambígua.

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

Gramática ambígua: - para uma string x existem mais de um LMD ou Mais de RMD ou Mais de uma árvore de Parse ou Um LMD e Um RMD, mas ambos produzem árvores de Parse diferentes.

                S                   S

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

esta gramática é gramática ambígua porque dois analisam a árvore.

CFG: - Uma gramática dita CFG se sua produção estiver na forma:

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

DCFL: - como sabemos, todos os DCFL são gramática LL (1) e todos os LL (1) são LR (1), então nunca seja ambíguo. portanto, DCFG nunca é ambíguo.

Também sabemos que todos os RL são DCFL, portanto, RL nunca seja ambíguo. Observe que RG pode ser ambíguo, mas RL não.

CFL: CFl Pode ou não ser ambíguo.

Nota: RL nunca seja inerentemente ambíguo.

Dean Meehan
fonte
4

Expressões regulares

  • Base de análise lexical
  • Representam linguagens regulares

Gramáticas livres de contexto

  • Base de análise
  • Representam construções de linguagem

insira a descrição da imagem aqui

Ahmed Salem
fonte
Não, essa é uma breve descrição, por favor leia novamente e verifique a imagem.
Ahmed Salem
3

Uma gramática é livre de contexto se todas as regras de produção tiverem a forma: A (ou seja, o lado esquerdo de uma regra só pode ser uma única variável; o lado direito é irrestrito e pode ser qualquer sequência de terminais e variáveis). Podemos definir uma gramática como uma 4 tupla, onde V é um conjunto finito (variáveis), _ é um conjunto finito (terminais), S é a variável inicial e R é um conjunto finito de regras, cada uma das quais é um mapeamento A
gramática regular V é linear à direita ou à esquerda, enquanto a gramática livre de contexto é 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 essas propriedades, podemos dizer que o conjunto de Linguagens Livres de Contexto também contém o conjunto de Linguagens Regulares

Wafiullah NAeemzi Afghan
fonte
-1

Basicamente, a gramática regular é um subconjunto da gramática livre de contexto, mas não podemos dizer que Cada gramática livre de contexto é uma gramática regular. Principalmente a gramática livre de contexto é ambígua e a gramática regular pode ser ambígua.

Babita Mehra
fonte
-4

uma gramática regular nunca é ambígua porque é linear à esquerda ou linear à direita, portanto, não podemos fazer duas árvores de decisão para a gramática regular, por isso ela é sempre inequívoca. mas, exceto a gramática regular, todos são podem ou não ser regulares

Dinesh
fonte
4
@dinesh Uma gramática regular pode ser ambígua. Lembre-se de que uma gramática é ambígua se existem duas árvores de sintaxe diferentes e que uma árvore de sintaxe é rotulada. Portanto, as árvores isomórficas são árvores diferentes. Ou seja, uma gramática simples como S -> aA | aB, B -> a, A -> a é ambíguo, pois existem duas árvores de sintaxe para a palavra 'aa' que são isomórficas, mas diferentes.
Kai Kuchenbecker