Linguagens regulares

As gramáticas regulares geram linguagens regulares.

A classe das linguagens regulares sobre um qualquer alfabeto A define-se indutivamente da seguinte forma:

1. O conjunto vazio, é uma linguagem regular (LR).

2. Qualquer que seja o símbolo a ∈ A, o conjunto {a} é uma LR.

3. Se L1 e L2 são linguagens regulares, então L1 U L2 (união) é uma LR.

4. Se L1 e L2 são linguagens regulares, então L1 . L2 (concatenação) é uma LR.

5. Se L1 é uma linguagem regular, então (L1)* (fecho de Kleene) é uma LR.

6. 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.

Linguagens regulares: exemplo 1

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ê?

1. Seja A = {a1;a2; ... ;an} o alfabeto da linguagem L;

2. Então as linguagens L1 = {a1}, L2 = {a2}, . . . , Ln = {an} são LR;

3. Igualmente a linguagem Lany = L1 U L2 U ... U Ln é também uma LR;

4. Qualquer que seja uma sequência finita de n símbolos do alfabeto A, podemos sempre descrevê-la como:

   

5. Logo, a sequência será uma LR sse a subsequência prefixn-1(seqn) também o for.

6. 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.

Linguagens regulares: exemplo 1

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.

Linguagens regulares: exemplo 2

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. {1} e {0} são regulares;

2. A = {0;1} = {0} U {1} é regular;

3. Se A é regular então A* também é;

4. 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).