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.
Imagem: Vitor Oliveira from Torres Vedras, PORTUGAL · BY-SA · Openverse
Uma gramática regular à direita é uma 4-upla (V, T, R, S) onde: As regras de produção de R são da forma: Um exemplo de gramática regular à direita G com V = {S,A}, T = {a,b,c}, R consiste 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:
Imagem: Eugenio Hansen, OFS · BY-SA · Openverse
Uma gramática regular estendida à direita possui regras produções da forma: 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:
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.
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 gera { a i b i : i ≥ 0 } {\displaystyle \{a^{i}b^{i}:i\geq 0\}} , a linguagem linear não-regular padrão.
