# 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:

   <img src="https://2105802016-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FP0B5wWrJT1pz8LDXyP2I%2Fuploads%2FSwoDwyE10QqwdYXDz0Kw%2Fa.png?alt=media&#x26;token=1f91105e-42d5-41ab-a182-158554b07590" alt=" " data-size="original">
5. Logo, a sequência será uma LR *sse* a subsequência prefix*n-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:

![](https://2105802016-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FP0B5wWrJT1pz8LDXyP2I%2Fuploads%2FPm6icekx8cPwKxGtRk7w%2Fa.png?alt=media\&token=aaaf28a8-60cd-451e-852a-858e483c0e78)

(Nota: A simples existência deste autómato também mostra a regularidade desta linguagem).
