Gramática regular
Este artigo não cita fontes confiáveis. (Novembro de 2021) |
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
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]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},
S → aA
A → Sb
S →
gera , a linguagem linear não-regular padrão.