Propriedades de idiomas comuns

Definição: Seja Σ um alfabeto finito. Uma linguagem L ⊆ Σ é regular se L for finita, ou L pode ser obtida indutivamente usando uma das seguintes operações:

L é L1 ∪ L2, a união de L1 e L2, onde L1 e L2 são regulares;

ou L é L1 • L2, a concatenação de L1 e L2, onde L1 e L2 são

regulares; ou L é L a iteração de L1, onde L1 é regular.

Note que o conjunto vazio ∅ e o conjunto {λ} são ambos

regulares, sendo finitos. As linguagens

{ab}∗. {a} {a, b}∗ são também regulares. Por que?

Proposição: Todo conjunto regular é uma linguagem linear a direita.

Definição: Seja Σ um alfabeto finito. Define-se expressões regulares R e suas denotações de conjuntos regulares S(R) indutivamente como:

• ∅ é uma expressão regular com S(∅) = ∅, o conjunto vazio.

• λ é uma expressão regular com S(λ) = {λ}.

• Se a ∈ Σ, então a é uma expressão regular com S(a) ={a}.

• Se R1 e R2 são expressões então (R1 + R2) ou (R1|R2) é

uma expressão regular com S((R1 + R2)) = S((R1|R2)) = S(R1) ∪ S(R2).

• 5 Se R1 e R2 são expressões então (R1 • R2) é uma

expressão regular com S((R1 • R2)) = S(R1) • S(R2).

• 6 Se R é regular então (R)∗ é regular com S((R)∗)=(S(R))∗

.

Propriedades das Linguagens Regulares

Introdução

• Os formalismos que representam linguagens regulares são de pouca complexidade, grande eficiência e fácil implementação.

• Entretanto a classe das linguagens regulares é muito restrita e limitada, sendo fácil definir linguagens que não são regulares.

• Algumas questões sobre linguagens regulares são as seguintes:

 Como determinar se uma linguagem é regular?

 Como verificar se uma LR é finita, infinita ou mesmo vazia?

 É possível examinar duas LR e decidir se são equivalentes ou não?

 A classe das LR é fechada para as operações de união concatenação e intersecção?