Gramática regular

Em Teoria da computação as Gramáticas regulares também conhecida como Tipo 3 da Hierarquia de Chomsky, é uma restrição sobre a forma das produções, pode-se criar uma nova classe de gramáticas de grande importância no estudo dos compiladores por possuírem propriedades adequadas para a obtenção de reconhecedores simples. Que também podem ser denominadas de Expressão regular.

A linguagem do tipo 3 é qualquer gramática linear. E uma gramática linear pode ser classificada em:

• Gramática linear à direita

* Se todas as regras de produção são do tipo: A::= tN ou A::= t

• Gramática linear à esquerda

* Se todas as regras de produção são do tipo = A::= Nt ou A::= t

• Gramática linear unitária à direita

* Se todas as regras de produção são como na linear à direita e, adicionalmente |t| < 1

• Gramática linear unitária à esquerda

* Se todas as regras de produção são como na linear à esquerda e, adicionalmente |t| < 1

Gramáticas regulares estritas

Uma gramática regular à direita é uma 4-upla (V, T, R, S) onde:

• V é um conjunto finito de variáveis;
• T é um conjunto finito, disjunto de V, denominado terminais;
• R é um conjunto finito de regras, onde cada regra é uma variável e uma cadeia de variáveis terminais;
• S é a variável inicial

As regras de produção de R são da forma:

1. B → a - onde B é um símbolo não-terminal de V e a é um terminal em Σ;
2. B → aC - onde B, C pertencem a V e a pertence a Σ;
3. B → ε - onde B pertence a V e ε é cadeia vazia.

Um exemplo de gramática regular à direita G com V = {S,A}, T = {a,b,c}, R consiste

nas seguintes regras:

S → aS

S → bA

A → ε

A → cA

S é o símbolo inicial. Esta gramática descreve a mesma linguagem que a expressão regular a*bc*, um conjunto de cadeias constituído de um número arbitrário de “a”s, seguido de um único “b”, seguido de um número arbitrário de “c”s.

Uma gramática regular à esquerda possui regras de produção da forma:

1. A → a - onde A é um símbolo não-terminal de V e a é um terminal em Σ;
2. A → Ba - onde A, B pertence a V e a pertence a Σ;
3. A → ε - onde A pertence a V e ε é cadeia vazia.

Gramáticas regulares estendidas

Uma gramática regular estendida à direita possui regras produções da forma:

1. B → a - onde B é um símbolo não-terminal de V e a é um terminal em Σ;
2. A → wB - onde A, B pertencem a V e w pertence a Σ*;
3. A → ε - onde A pertence a V e ε é cadeia vazia.

Alguns autores chamam este tipo de gramática como gramática regular à direita (ou gramática linear à direita) e o tipo acima como gramática regular estritamente à direita (ou gramática linear estritamente à direita). Uma gramática regular estendida à esquerda possui regras produções da forma:

1. B → a - onde B é um símbolo não-terminal de V e a é um terminal em Σ;
2. A → Bw - onde A, B pertencem a V e w está em Σ*;
3. A → ε - onde A pertence a V e ε é uma cadeia vazia.

Poder expressivo

Há uma correspondência direta de um-para-um entre as regras de uma gramática regular (estrita) à esquerda e as de um autômato finito não-determinístico, de tal forma que a gramática gera exatamente a linguagem que o autômato aceita. Assim, as gramáticas regulares à esquerda geram exatamente todas as linguagens regulares. As gramáticas regulares à direita descrevem o inverso de todas essas linguagens, ou seja, também geram exatamente todas as linguagens regulares.

Toda gramática regular estrita à direita é regular estendida à direita, enquanto cada gramática regular estendida à direita pode ser feita pela inserção estrita de novos símbolos não-terminais, de forma que o resultado gera a mesma linguagem; ou seja, gramáticas regulares estritas à direita também geram linguagens regulares. Analogamente, o mesmo acontece com as gramáticas regulares estendidas à esquerda.

Se produções vazias não são permitidas, apenas as linguagens regulares que não incluem a cadeia vazia podem ser geradas.

O lema do bombeamento para linguagens regulares descreve uma propriedade essencial para todas as linguagens regulares. Informalmente, o lema diz que todas as palavras suficientemente longas em uma linguagem regular podem ser bombeadas — ou seja, no meio da palavra há uma seção que se repete um número arbitrário de vezes — para produzir uma nova palavra que também se encontra dentro da mesma linguagem. Referindo-se ao exemplo de sintaxe de ponto flutuante acima, na derivação de um número de ponto flutuante que contém mais de 7 caracteres, um símbolo não-terminal deve ocorrer duas vezes, daí uma das regras "A → 0A", "C → 0C", ..., "F → 9F" deve ter sido aplicada; repetindo essa regra diversas vezes, no lugar de apenas uma vez, sempre resulta em um número de ponto flutuante.

Misturando regras regulares à esquerda e à direita

Sendo permitido misturar as regras regulares à esquerda ou regulares à direita, nós ainda temos uma gramática linear, mas não necessariamente uma gramática regular. Além disso, tal gramática não precisa gerar uma linguagem regular: todas as gramáticas lineares podem ser facilmente trazidas para essa forma e, portanto, tais gramáticas podem gerar exatamente todas as linguagens lineares, incluindo as não regulares.

Por exemplo, a gramática G com N = {S, A}, Σ = {a, b}, P com símbolo inicial S e regras

S → aA

A → Sb

S → ε

gera $\{a^{i}b^{i}:i\geq 0\}$ , a linguagem linear não-regular padrão.