Gramáticas livres de contexto

CFG e derivações

Uma gramática livre de contexto é $G=(V,\Sigma,P,S)$ : $V$ são as variáveis, $\Sigma$ os terminais disjuntos de $V$ , $P$ as produções e $S\in V$ o símbolo inicial. Cada produção tem a forma $A\to\alpha$ , com uma única variável à esquerda.

Um passo escreve-se $xAy\Rightarrow x\alpha y$ e $\Rightarrow^*$ indica zero ou mais passos. A linguagem contém só palavras terminais deriváveis de $S$ : $L(G)=\{w\in\Sigma^*\mid S\Rightarrow^*w\}$ .
Para provar $L(G)=L$ , mostra que as regras não geram palavras fora de $L$ e que geram todas as palavras pretendidas.

Construções

Linguagem, com $n,m\ge0$	Gramática
$a^nb^n$	$S\to aSb\mid\varepsilon$
$a^nb^{2n}$	$S\to aSbb\mid\varepsilon$
$a^nb^m$ com $n>m$	$S\to aSb\mid A$ ; $A\to aA\mid a$
Palíndromos binários	$S\to0S0\mid1S1\mid0\mid1\mid\varepsilon$

Para palavras com o mesmo número de $a$ e de $b$ em qualquer ordem, a lição usa $S\to SS\mid aSb\mid bSa\mid ab\mid ba\mid\varepsilon$ . A regra $SS$ junta dois blocos equilibrados, $aSb$ e $bSa$ envolvem um bloco equilibrado e as bases $ab$ , $ba$ e $\varepsilon$ garantem palavras terminais. Sem essas bases, só com $SS$ , $aSb$ e $bSa$ , nenhuma palavra terminal seria gerada. A prova completa por indução na árvore e no comprimento está na lição.

Ambiguidade e precedência

Uma gramática é ambígua quando alguma palavra tem duas árvores sintáticas distintas, ou seja, duas derivações mais à esquerda distintas. As ordens esquerda e direita da mesma árvore não contam como ambiguidade.
$E\to E+E\mid E*E\mid a$ : $a+a*a$ como $a+(a*a)$ ou $(a+a)*a$ .
Precedência de $*$ e associatividade à esquerda:

E\to E+T\mid T,\quad T\to T*F\mid F,\quad F\to a\mid(E).

Aceitar as mesmas palavras não implica dar as mesmas árvores.

Palavra

Palavra aceite.

Testes

Uma palavra e o resultado esperado por linha

Passar estes casos não prova que a gramática gera toda e só a linguagem pedida.

Solução do exercício

Sintaxe

Uma produção por linha, com -> ou →. Separa alternativas com | e usa ε para a palavra vazia. A primeira variável é a inicial.

As variáveis começam por maiúscula e precisam de uma produção. Os outros caracteres são terminais; usa aspas, como "A", para um terminal maiúsculo. Os espaços entre símbolos são ignorados.

A palavra em branco representa ε. O editor aceita recursão à esquerda e mostra uma árvore possível, sem decidir se a gramática é ambígua.

Hierarquia

Tipo	Restrição nas produções $u\to v$ , com pelo menos uma variável em $u$
3, regular	Todas lineares à direita ou todas à esquerda
2, livre de contexto	Uma única variável à esquerda
1, sensível ao contexto	$\lvert u\rvert\le\lvert v\rvert$ , isto é, as regras não diminuem o comprimento
0, sem restrições	Qualquer $u\to v$ com variável em $u$

Se a linguagem contém $\varepsilon$ , o tipo 1 admite a exceção $S\to\varepsilon$ , desde que o símbolo inicial $S$ não apareça em nenhum lado direito. Esta é a convenção usada na lição para regras que não diminuem o comprimento.

Classifica as regras dadas, não a menor classe da linguagem: a gramática $S\to SS\mid a$ é de tipo 2, mas gera $aa^*$ , que é regular. De um DFA, cria uma variável $A_q$ por estado, uma produção $A_q\to aA_r$ por transição $\delta(q,a)=r$ e $A_f\to\varepsilon$ por cada estado final $f$ , com inicial $A_{q_0}$ .

Construções com desigualdades e provas.

Perguntar sobre esta página

CFG e derivações

Construções

Ambiguidade e precedência

Hierarquia

Gramáticas livres de contexto · TLDR

CFG e derivações

Construções

Ambiguidade e precedência

Hierarquia

À tua maneira

Aparência

Leitura

Código

Navegação

CSS personalizado

Pesquisar

Copiar fórmula

Pesquisar nesta página

Atalhos de teclado