CCT-UFCA/Ciência da Computação/Autômatos e Linguagens Formais/Operações Regulares e Expressões Regulares

Nessa seção, veremos os tipos de operações regulares e o que são expressões regulares.

Operações Regulares

Vamos mostrar que as linguagens regulares tem fecho sob as operações regulares; união, concatenação e estrela.

União:

Para provarmos que a classe das linguagens regulares é fechada sob a operação de união, utilizaremos AFNs para facilitar o entendimento. Temos as linguagens regulares A1 e A2 e desejamos provar que A1 ∪ A2 é regular. A ideia é tomar os dois AFNs, N1 e N2 para A1 e A2, e combiná-los em um novo AFN, N. Para construir esse autômato N, podemos criar um novo estado inicial que liga para os estados iniciais de N1 e N2 com uma transição vazia. Dessa forma, a máquina N não-deterministicamente adivinha qual das duas máquinas aceita a entrada. Se uma delas aceita a entrada, N também a aceitará.

Concatenação:

Temos as linguagens regulares A1 e A2 e desejamos provar que A1 ◦ A2 é regular. A ideia é tomar dois AFNs, N1 e N2 para A1 e A2, e combiná-los em um novo AFN N como fizemos para o caso da união, mas com um detalhe diferente. Para isso, criamos novas transições vazias saindo de cada estado final de N1 e entrando no estado inicial de N2. Dessa forma, o autômato N só vai aceitar entradas que são aceitas tanto em N1 como em N2. Podemos pensar em N como não-deterministicamente adivinhando onde fazer a divisão da entrada.

Estrela:

Temos uma linguagem regular A₁ e desejamos provar que A₁* também é regular. Tomamos um AFN N₁ para A₁ e modificamo-lo para reconhecer A₁*. O AFN resultante N aceitará sua entrada sempre que ela puder ser quebrada em várias partes e N₁ aceite cada uma das partes.

Exemplos: Seja A = {0, 01, 011} e B = {1, 01, 11},

A ∪ B = B ∪ A = {0, 1, 01, 11, 011};

A ○ B = {01, 001, 011, 0101, 0111, 01101, 01111};

B^* = {ε, 1, 01, 11, 101, 111, 011, 0101, 0111, 1101, 1111,⋯}.

Expressões Regulares

Uma expressão aritmética utiliza as operações +,−,× e / para representar números, como por exemplo (5+3)×4. Similarmente, podemos usar as operações regulares para montar expressões descrevendo linguagens, que são chamadas expressões regulares. Um exemplo seria: (0 ∪ 1)0*.

Definição formal:

Digamos que R é uma expressão regular se R for

1. a para algum a no alfabeto sigma;
2. ε;
3. ∅;
4. (R₁ ∪ R₂), onde R₁ e R₂ são expressões regulares;
5. (R₁ ○ R₂), onde R₁ e R₂ são expressões regulares; ou
6. (R₁*), onde R₁ e R₂ são expressões regulares.

Nota: Por conveniência, tomamos R⁺ como abreviação para RR*, significando que a linguagem R⁺ tem todas as cadeias que resultam de 1 ou mais concatenações de cadeias de R. Logo, R* ∪ ε = R⁺.

Exemplos

1. Todas as cadeias que que contém um único 1: R = 0*10*;
2. Todas as cadeias que contém pelo menos um símbolo 1: R = Σ*1Σ*;
3. Todas as cadeias de comprimento par: R = (ΣΣ)*;
4. Todas as cadeias de comprimento múltiplo de 3: R = (ΣΣΣ)*;
5. Todas as cadeias que começam e terminam com o mesmo símbolo: R = 0Σ* 0 ∪ 1Σ* 1 ∪ 0 ∪ 1.

Equivalência entre Autômatos Finitos e Expressões Regulares

Expressões regulares e autômatos finitos são equivalentes no seu poder descritivo. Esse fato é um tanto notável, porque autômatos finitos e expressões regulares aparentam superficialmente ser um tanto diferentes. Entretanto, qualquer expressão regular pode ser convertida em um autômato finito que reconhece a linguagem que ela descreve, e vice-versa. Lembre-se que uma linguagem regular é aquela que é reconhecida por algum autômato finito.

Para você provar a veracidade disso, basta você pegar uma expressão regular qualquer R descrevendo uma certa linguagem A e converter R em um AFN equivalente que reconhece A.