Linguagens regulares
Last updated
Last updated
As gramáticas regulares geram linguagens regulares.
A classe das linguagens regulares sobre um qualquer alfabeto A define-se indutivamente da seguinte forma:
O conjunto vazio, é uma linguagem regular (LR).
Qualquer que seja o símbolo a ∈ A, o conjunto {a} é uma LR.
Se L1 e L2 são linguagens regulares, então L1 U L2 (união) é uma LR.
Se L1 e L2 são linguagens regulares, então L1 . L2 (concatenação) é uma LR.
Se L1 é uma linguagem regular, então (L1)* (fecho de Kleene) é uma LR.
Nada mais é linguagem regular.
Note que o conjunto {e}, isto é, o conjunto composto pela palavra vazia, é também uma linguagem regular uma vez que: {e} = vazio*
Uma vez que operações sobre LR geram uma LR, diz-se que a LR é fechada sobre as suas operações.
Esta definição tem implicações interessantes.
Uma delas é que qualquer linguagem finita, isto é que descreva um número finito de sequências de símbolos do seu alfabeto, é uma linguagem regular.
Porquê?
Seja A = {a1;a2; ... ;an} o alfabeto da linguagem L;
Então as linguagens L1 = {a1}, L2 = {a2}, . . . , Ln = {an} são LR;
Igualmente a linguagem Lany = L1 U L2 U ... U Ln é também uma LR;
Qualquer que seja uma sequência finita de n símbolos do alfabeto A, podemos sempre descrevê-la como:
Logo, a sequência será uma LR sse a subsequência prefixn-1(seqn) também o for.
Aplicando indutivamente a demonstração, facilmente se chega à conclusão que se há-de de chegar à subsequência vazia, logo qualquer linguagem finita é uma linguagem regular.
Uma vez que uma linguagem regular é uma linguagem reconhecida por um autómato finito é fácil, também por aí, chegarmos à mesma conclusão.
Basta para tal considerar uma máquina de estados que implemente todas as transições das palavras da linguagem.
Como o número de transições é finito (porque o número de palavras da linguagem também o é), então é sempre possível criar esse autómato finito.
Mantendo esta perspectiva, podemos ir mais longe e afirmar que numa linguagem finita, os autómatos que a reconhecem não têm ciclos.
Da mesma forma, a existência de pelo menos um ciclo no autómato finito, implica necessariamente uma linguagem infinita.
Mostre que o conjunto dos números binários começados em 1 e terminados em 0 é uma LR sobre o alfabeto A = {0;1}.
O conjunto pretendido pode ser representado por L = {1} . A* . {0}.
{1} e {0} são regulares;
A = {0;1} = {0} U {1} é regular;
Se A é regular então A* também é;
Finalmente, {1} .A* . {0} é também regular.
Um autómato finito que reconhece esta linguagem pode ser:
(Nota: A simples existência deste autómato também mostra a regularidade desta linguagem).