CCT-UFCA/Ciência da Computação/Autômatos e Linguagens Formais/Gramáticas Livres-de-contextos

Gramáticas Livres-de-contexto (GLCs) são um método mais poderoso que as Linguagens Regulares, que são dispositivos geradores que se aproveitam de recursão. Elas geram as strings que pertencem a ela, definindo assim a sua linguagem. O conjunto de linguagens que podem ser representadas por GLCs são as Linguagens livres-de-contexto.

Uma GLC é constituída por finitas regras de substituição, regras de produção e produções. Cada produção consiste em um símbolo e uma cadeia separados por uma seta. O símbolo é sempre uma variável (letra maiúscula) e a cadeia pode ser composta por várias variáveis e símbolos chamados de terminais (ε, letras minúsculas, números e símbolos especiais). Convenciona-se chamar a variável da primeira produção de variável inicial.

Exemplo:

A → 0A1

A → B

B → #

Variáveis: A (inicial) e B; Terminais: 0, 1 e #.

Definição Formal

Uma Gramática livre-de-contexto é uma 4-upla (V, Σ,R, S), onde:

1. V é o conjunto finito de variáveis;
2. Σ é o conjunto finito, disjunto de V, de terminais;
3. R é uma relação binária V × (V ∪ Σ)*;
4. S ∈ V é a variável inicial.

A linguagem definida por uma GLC G, denotada por L(G), são todas as strings derivadas por G. O alfabeto da linguagem é o conjunto de terminais da gramática.

Árvore Sintática

Árvore enraizada que representa a estrutura de uma derivação. Uma derivação de uma cadeia é feita de seguinte forma:

1. Inicialmente, temos apenas a variável inicial na cadeia atual;
2. Em cada passo, substituímos uma variável da cadeia atual por uma cadeia de acordo com as produções;
3. O processo finda quando a cadeia atual contém apenas símbolos terminais;
4. A sequência de cadeias da variável inicial até a cadeia derivada s é chamada de uma derivação de s.

Uma derivação é dita derivação mais à esquerda se, em cada passo, a variável substituída é sempre a mais à esquerda da cadeia atual. As estruturas de duas derivações são diferentes se e somente se as suas árvores sintáticas são diferentes. Os nós internos da árvore serão as variáveis, a raiz será a variável inicial, as folhas serão os terminais e os filhos de um nó serão todos os símbolos derivados dele (a ordem dos filhos importa).

Uma cadeia é derivada ambiguamente se ela possui duas derivações mais à esquerda diferentes ou ela possui duas árvores sintáticas diferentes. Dizemos que uma Gramática é ambígua se ela gera alguma cadeia ambiguamente. Algumas linguagens possuem apenas GLCs ambíguas que as geram (ditas linguagens inerentemente ambíguas)

Forma Normal de Chomsky

Quando se trabalha com LLCs, é frequentemente conveniente tê-las em forma simplificada. Uma das formas mais simples e amis úteis é chamada forma normal de Chomsky. Ela é útil quando se quer dar algoritmos para trabalhar com gramáticas livres-de-contexto.

Definição: Uma gramática livre-de-contexto está na forma normal de Chomsky se toda regra é da forma:

A → BC

A → a

onde a é qualquer terminal e A, B e C são quaisquer variáveis, exceto que B e C não podem ser a variável inicial. Adicionalmente, permitimos a regra S → ε, onde S é a variável inicial.