Gramáticas Livres de Contexto

Uma gramática livre de contexto (GLC) é o quádruplo G = (V, Σ, R, S): variáveis, terminais, produções A → α com uma variável só à esquerda, e o inicial S. L(G) é o conjunto das cadeias só de terminais com S ⇒* w.

Árvores, análise, simplificação e formas normais deste tópico — e autômatos com pilha e a hierarquia de Chomsky nos seguintes — partem desse quádruplo.

As páginas se agrupam em quatro blocos. O primeiro monta G e calcula L(G): linear à direita ou à esquerda coincide com autômato finito; S → aSb gera {aⁿbⁿ}.

O segundo registra a hierarquia numa árvore e decide se w tem árvore e se ela é única. A fronteira é a forma sentencial; mais à esquerda e mais à direita são duas ordens da mesma árvore.

O terceiro troca G por outra com a mesma linguagem, na ordem produtivo, alcançável, ε e unitária.

O quarto restringe o formato: A → BC ou A → a para o CYK; A → aα para a mais à esquerda ler um terminal por passo.

Linear à direita (variável no fim) e a derivação S ⇒* w estão em Introdução. A árvore, e a derivação mais à direita ou mais à esquerda, estão em Árvores de Derivação.

Duas ordens da mesma árvore estão em Árvores de Derivação. Duas árvores para o mesmo w — G ambígua, ou L inerentemente ambígua — estão em Análise Sintática e Ambiguidade.

Cortar inúteis, ε e unitárias, sem mudar L(G), está em Simplificação de GLC. Converter para FNC (CYK) ou FNG (um terminal por passo) está em Formas Normais.