Linguagens Regulares

1
Linguagens Regulares e Expressões Regulares
• Toda linguagem regular pode ser descrita por uma expressão regular.
• As Expressões Regulares são consideradas um formalismo gerador, pois especificam as
LR.
• É definida a partir de conjuntos básicos e operações de concatenação e união.
• São consideradas bastante adequadas para comunicação homem-máquina.
• Toda Linguagem Regular é reconhecida por um AFD / AFND / AF-ε.
Alfabetos e Palavras
• Sabemos que um alfabeto é um conjunto finito de símbolos distintos.
Σ = {a,b,c}; Σ = {0,1}; ...
• Uma palavra sobre um alfabeto Σ é uma sequência de comprimento finito formada com
símbolos desse alfabeto.
• Algumas palavras sobre o alfabeto Σ = {a,b,c} :
abc , bcaabbac , b
• Algumas palavras sobre o alfabeto Σ = {0,1} :
01011101, 1010, 0, 1
• A palavra de comprimento zero é representada por λ ; ou seja, | λ |= 0.
• λ é, em alguns livros, denotado por ε.
• Nunca confundir λ ou ε com o espaço em branco, que é um caractere não imprimível.

3
Linguagens
• Seja Σ um alfabeto qualquer. O conjunto de todas as palavras sobre Σ é denotado por Σ* .
• Por exemplo, se Σ = {a,b,c} , então
Σ* = {λ, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, ...}
• Uma linguagem sobre um alfabeto Σ é qualquer subconjunto de Σ* .
• Definição típica de uma linguagem L :
• L(M)= {w|w inicia por “a”}, com Σ = {a,b,c}
• Lê-se: A linguagem L, reconhecida pela máquina M, é definida pelo conjunto de
palavras w sobre , iniciadas pelo símbolo “a”.
• São exemplos de palavras de L:
• {a, ab, bbc}
• {aa, ab, ac, ba, bb, bc, ca, cb, cc}

4
Linguagens
• Outras linguagens sobre Σ = {a,b,c} :

• L(M)= {w|w inicia por “a”}, com |w| par}

• {λ, a, b, c}
• {λ}
• {}
• Σ*
• A concatenação de 2 palavras será representada por sua justaposição.
• Por exemplo, seja x e y palavras, onde x = abc e y = bb; a concatenação de x com y é
representada por:
xy = abcbb.

5
Reverso da Cadeia
• A reversa de uma cadeia é obtida escrevendo-se os símbolos em ordem reversa. Se w é a
cadeia acima, então a reversa de w, denotado por wR, é a cadeia an · · · a1.
• Uma definição recursiva da reversa de uma cadeia é a seguinte:
λR = λ e (aw) R = wRa
EXEMPLO:
Sejam w = bbab e v = aaab. Então:
wv = bbabaaab; vw = aaabbbab;
wR = babb e vR = baaa.
Sufixo e Prefixo
Se w = vu, então v é chamado de prefixo e u de sufixo de w.
Formalmente:
• v é um prefixo de w se existe uma cadeia u tal que vu = w.
• u é um sufixo de w se existe uma cadeia v tal que vu = w.

EXEMPLO:
Seja w = abbab.
• O conjunto de todos os prefixos de w é {λ, a, ab, abb, abba, abbab}
• O conjunto de todos os sufixos é {λ, b, ab, bab, bbab, abbab}
O comprimento de uma cadeia
O comprimento de uma cadeia w, denotado por |w|, é o número de símbolos que figuram
na cadeia.
Exemplo: |abba |= 4.
Sejam u e v cadeias quaisquer sobre um alfabeto Σ, então:
|uv|=|u| + |v|. (1)
Para mostrar esta igualdade precisamos de uma definição mais precisa de comprimento de
cadeia. Daremos a seguinte definição recursiva:
|λ|= 0, e |wa|=|w|+1, para todo a ∈ Σ e qualquer cadeia w de Σ.
Usaremos a indução no comprimento da cadeia para mostrar a equação (1).
O comprimento de uma cadeia
Mostrando que |uv|=|u| + |v|. (1)
• Se |v|= 0, então v = λ; logo, por definição,
|uv|=|u|=|u|+0 =|u| + |v | .

• Suponha que |uv|=|u| + |v| e calculemos |uva|:

|uva| = |uv|+1 = |u|+|v|+1 = |u|+|va|.
Logo, por indução, a igualdade é válida para todo v.
Se w é uma cadeia, então wn é a cadeia obtida concatenando w com ela própria n vezes.
Portanto, wn+1 = wwn . No caso especial de n = 0, w 0 = λ.
Concatenação de Linguagens
Se X e Y são duas linguagens, a concatenação de X com Y, denotada por XY, forma a
seguinte linguagem:

XY = { palavras xy tais que x ∈ X e y ∈ Y }

Ou seja, são as palavras formadas pela concatenação de uma palavra qualquer de X com
uma palavra qualquer de Y (prefixo pertence a X, sufixo pertence a Y).

10
Concatenação de Linguagens
Por exemplo, sejam
X = {a,b,c} e Y = {abb,ba} .
Então
XY = {aabb,aba,babb,bba,cabb,cba}

A concatenação de X consigo mesma n vezes é Xn :

Xn = X X X ... X X (n vezes)

Por definição, X0 é o conjunto {λ}:

X0 = {λ}

11
Concatenação de Linguagens
Outros exemplo:
Seja X = {a,b,c} e Y = {abb,ba} :

X0 = {λ}
X1 = X = {a,b,c}
X2 = XX = {aa,ab,ac,ba,bb,bc,ca,cb,cc}
X3 = X2X = {aaa,aab,aac,aba,abb,abc,aca,acb,acc,
baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc,
caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc}
Y2 = YY = {abbabb,abbba,baabb,baba}

12
Fecho de Kleene
A operação X*, denominada Fecho de Kleene de X; ela é definida como a união de cada Xi ,
com 0 ≤i≤∞.
X* = X0 ∪ X1 ∪ X2 ∪ X3 ∪ ...
Ou seja, X* consiste de todas as palavras que se pode construir a partir dos elementos
de X .
Por exemplo, se X = {a,b,c} e Y = {abb,ba} :
X* = {λ,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,...}
Y* = {λ,abb,ba,abbabb,abbba,baabb,baba,abbabbabb,...}

13
Fecho de Kleene
•O conjunto Σ∗ sempre contém λ.
•O fecho estrela de Σ sem a cadeia vazia é denominado fecho positivo do alfabeto Σ, e é
denotado por Σ+. Assim, Σ+ = Σ *− {λ}.
•Enquanto um alfabeto Σ é um conjunto finito, Σ * e Σ + são sempre infinitos, pois Σ é não
vazio e não existe limite no comprimento das cadeias nesses dois conjuntos.
Expressões Regulares

15
Expressões Regulares (ER)
Se r e s são ER e denotam as linguagens R e S, então:
. (r+s) é ER e denota a linguagem R∪S; qualquer alternância na ocorrência das
linguagens r e s.
. (rs) é ER e denota a linguagem RS={uv| u ∈ R e v ∈S} – a linguagem r, seguida
(concatenada) à linguagem s.
. (r*) é ER e denota a linguagem R* (fecho)
. (r+) é ER e denota a linguagem R+ (fecho positivo)
Expressões Regulares - Definição
Para definir expressões regulares, vamos usar as seguintes abreviações:
• o conjunto {a} será representado simplesmente por a ;
• {a,b,c,...} será representado por a ∪ b ∪ c ∪...
O conjunto de expressões regulares (ER) sobre um alfabeto Σ qualquer é definido indutivamente da
seguinte maneira:
• os conjuntos { } e λ são expressões regulares;
• para todo símbolo a de Σ, a é uma expressão regular;
• se x e y são expressões regulares sobre Σ, então também são expressões regulares: x ∪ y , xy
e x* .
• ∅ É uma ER e denota a linguagem vazia.
• λ é uma ER e denota a linguagem contendo unicamente, a palavra vazia {λ} ou {ε}.
• ∑ é o alfabeto; qualquer x ∈ Σ é uma ER e denota a linguagem contando a palavra unitária {x}
17
Expressões Regulares - Definição
a∪b
linguagem formada apenas pelas palavras a e b
abb ∪ aa ∪ ac
linguagem formada exatamente pelas palavras abb, aa e ac, ou seja, {abb,aa,ac}

a*
linguagem (infinita) de todas as palavras formadas apenas com o símbolo a

18
Expressões Regulares - Exemplos
(a ∪ b) (ab ∪ bb) denota a linguagem {aab,abb,bab,bbb}
(a ∪ b)* a linguagem {λ,a,b,aa,ab,ba,bb,aaa,...} :
(aa)* palavras só com a, e com comprimento par (inclui a palavra nula)

Outras abreviações:
• x+ é usado para abreviar xx* ;
• x2 é usado para abreviar xx ;
• x3 para abreviar x2x etc.
• (a2)+ define palavras só com a, e com comprimento par maior que zero (não inclui a
palavra nula)
• a (a ∪ b ∪ c)* define a Linguagem sobre {a,b,c} das palavras que começam com o
símbolo a

19
Expressões Regulares - Exemplos
• a (a ∪ b ∪ c)* b - Linguagem sobre {a,b,c} das palavras que começam com o símbolo
a e terminam com “b”
• (b ∪ c) (a ∪ b ∪ c)* ∪ λ - Linguagem das palavras sobre {a,b,c} que não começam
com o símbolo “a”.
• (a ∪ b)* b (a ∪ b)* - Linguagem das palavras sobre {a,b,c} que possuem pelo menos
um símbolo “b”.
• (b* a b* a b*) * - Linguagem das palavras sobre {a,b,c} que possuem exatamente dois
símbolos “a”.
• (a ∪ b ∪ c) (a ∪ b ∪ c) (a ∪ b ∪ c) - Linguagem das palavras sobre {a,b,c} que
possuem exatamente três símbolos.

20
Expressões Regulares - Restrições
As linguagens que podem ser especificadas por expressões regulares são chamadas de
linguagens regulares.
Mas expressões regulares não podem ser usadas para especificar qualquer linguagem
desejada.
Muitas linguagens não conseguem ser especificadas com expressões regulares,
necessitando de formalismos mais poderosos. Por exemplo:
• Linguagem cujas palavras têm o formato anbn, para qualquer n. Ou seja:
{ λ, ab, aabb, aaabbb, ... }
• Linguagem sobre alfabeto { a, b, (, ) } com aninhamento correto de parêntesis
abrindo e fechando.
{((a)), b, ((((b))), ((((((((a((b))))))))))}

21