# 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:
    * Se todas as regras de produção são do tipo: A::= tN ou A::= t
    * Se todas as regras de produção são do tipo = A::= Nt ou A::= t
    * Se todas as regras de produção são como na linear à direita e, adicionalmente |t| < 1
    * 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:
* B → a - onde B é um símbolo não-terminal de V e a é um terminal em Σ;
* B → aC - onde B, C pertencem a V e a pertence a Σ;
* 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:
* A → a - onde A é um símbolo não-terminal de V e a é um terminal em Σ;
* A → Ba - onde A, B pertence a V e a pertence a Σ;
* 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:
* B → a - onde B é um símbolo não-terminal de V e a é um terminal em Σ;
* A → wB - onde A, B pertencem a V e w pertence a Σ*;
* 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:
* B → a - onde B é um símbolo não-terminal de V e a é um terminal em Σ;
* A → Bw - onde A, B pertencem a V e w está em Σ*;
* 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.