Gramática regular

Na ciência da computação teórica e na teoria da linguagem formal, uma gramática regular é uma gramática que é regular à direita ou regular à esquerda. Embora sua definição exata varie de livro para livro, todos eles exigem que

• todas as regras de produção têm no máximo um símbolo não-terminal;
• esse símbolo é sempre no final ou sempre no início do lado direito da regra.

Toda gramática regular descreve uma linguagem regular.

Gramáticas estritamente regulares

Uma gramática regular à direita (também chamada de gramática linear à direita) é uma gramática formal (N, Σ, P, S) em que todas as regras de produção em P são de uma das seguintes formas:

1. A → um
2. A → AB
3. A →

onde A, B, S ∈ N são símbolos não terminais, a ∈ Σ é um símbolo terminal e ε denota a string vazia, ou seja, a string de comprimento 0. S é chamado de símbolo inicial.

Em uma gramática regular à esquerda, (também chamada de gramática linear à esquerda), todas as regras obedecem às formas

1. A → um
2. A → Bando
3. A →

A linguagem descrita por uma determinada gramática é o conjunto de todas as strings que contêm apenas símbolos terminais e podem ser derivadas do símbolo inicial pela aplicação repetida de regras de produção. Duas gramáticas são chamadas de fracamente equivalentes se descrevem a mesma linguagem.

As regras de ambos os tipos não devem ser misturadas; por exemplo, a gramática com conjunto de regras { S→T, T→Sb, S→ε } não é regular, e descreve a linguagem (umEu...b)Eu...:Eu...∈ ∈ N?{displaystyle {a^{i}b^{i}:iin mathbb {N} }}, que também não é regular.

Alguns livros e artigos não permitem regras de produção vazias e assumem que a string vazia não está presente nos idiomas.

Gramática regular estendida

Uma gramática regular à direita estendida é aquela em que todas as regras obedecem a uma das

1. A → O quê?, onde A é um não-terminal em N e O quê? está em uma cadeia (possivelmente vazia) de terminais Σ^*
2. A → WB, onde A e B em N e O quê? está em Σ^*.

Alguns autores chamam esse tipo de gramática de gramática regular à direita (ou gramática linear à direita) e o tipo acima de gramática estritamente regular à direita (ou gramática estritamente linear à direita).

Uma gramática regular à esquerda estendida é aquela em que todas as regras obedecem a uma das

1. A → O quê?, onde A é um não-terminal em N e O quê? está em Σ^*
2. A → Bw., onde A e B em N e O quê? está em Σ^*.

Exemplos

Um exemplo de gramática regular à direita G com N = {S, A}, Σ = {a, b, c}, P consiste nas seguintes regras

S → aS

S → bA

A →

A → cA

e S é o símbolo inicial. Esta gramática descreve a mesma linguagem que a expressão regular a*bc*, viz. o conjunto de todas as strings consistindo em muitos "a"s, seguidos por um único "b", seguido por arbitrariamente muitos "c"s.

Uma gramática regular à direita estendida um pouco mais longa, mas mais explícita G para a mesma expressão regular é dada por N = {S, A, B, C}, Σ = {a, b, c}, onde P consiste nas seguintes regras:

S → A

A → aA

A → B

B → BC

C → ε

C → cC

...onde cada letra maiúscula corresponde a frases que começam na próxima posição na expressão regular.

Como um exemplo da área de linguagens de programação, o conjunto de todas as strings que denotam um número de ponto flutuante pode ser descrito por uma gramática regular direita estendida G com N = {S,A,B,C,D,E,F}, Σ = {0,1,2,3,4,5,6,7,8,9,+,−,.,e}, onde S é o símbolo inicial e P consiste nas seguintes regras:

S → +A	A → 0A	B → 0C	C → 0C	D → + E	E → 0F	F → 0F
S → A −	A → 1A	B → 1C	C → 1C	D → -E	E → 1F	F → 1F
S → A	A → 2A	B → 2C	C → 2C	D → E	E → 2F	F → 2F
	A → 3A	B → 3C	C → 3C		E → 3F	F → 3F
	A → 4A	B → 4C	C → 4C		E → 4F	F → 4F
	A → 5A	B → 5C	C → 5C		E → 5F	F → 5F
	A → 6A	B → 6C	C → 6C		E → 6F	F → 6F
	A → 7A	B → 7C	C → 7C		E → 7F	F → 7F
	A → 8A	B → 8C	C → 8C		E → 8F	F → 8F
	A → 9A	B → 9C	C → 9C		E → 9F	F → 9F
	A →.B		C → ED			F →
	A → B		C → ε

Poder expressivo

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

Toda gramática regular à direita estrita é regular à direita estendida, enquanto toda gramática regular à direita estendida pode ser tornada estrita inserindo novos não-terminais, de modo que o resultado gere a mesma linguagem; portanto, gramáticas regulares à direita estendidas também geram as linguagens regulares. Analogamente, o mesmo acontece com as gramáticas regulares à esquerda estendidas.

Se produções vazias não forem permitidas, apenas todas as linguagens regulares que não incluam a string vazia podem ser geradas.

Enquanto gramáticas regulares só podem descrever linguagens regulares, o inverso não é verdadeiro: linguagens regulares também podem ser descritas por gramáticas não regulares.

Misturando regras regulares à esquerda e regulares à direita

Se a mistura de regras regulares à esquerda e regulares à direita for permitida, ainda teremos uma gramática linear, mas não necessariamente regular. Além disso, tal gramática não precisa gerar uma linguagem regular: todas as gramáticas lineares podem ser facilmente trazidas para esta 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 start símbolo S e regras

S → aA

A → Sb

S →

gera (umEu...b)Eu...:Eu...≥ ≥ 0?{displaystyle {a^{i}b^{i}:igeq 0}}, a linguagem linear paradigmática não regular.