Aula 7 expressão regular

1. Curso: Ciência da Computação
Turma: 7ª Série
Linguagens Formais e Autômatos
Aula 7
Aspectos Teóricos da Computação

2. Aspectos Teóricos da Computação
2/26
Notas de Aula
Avaliação 15 de Abril.

3. Aspectos Teóricos da Computação
3/26
Linguagens Regulares
●O estudo das linguagens regulares é abordado
usando os seguintes formalismos:
➔Autômato Finito. Trata-se de um formalismo
operacional ou reconhecedor, sendo basicamente,
um sistema de estados finitos;
➔Expressão Regular. Trata-se de um formalismo
denotacional, também considerado gerador, o qual
é definido a partir de conjuntos (linguagens)
básicos e das operações de concatenação e de
união;
➔Gramática Regular. Trata-se de um formalismo
axiomático ou gerador o que, como o nome indica,
é uma gramática, mas com restrições de forma das
regras de produção.

4. Aspectos Teóricos da Computação
4/26
Expressão Regular
●Toda linguagem regular pode ser descrita por uma
expressão denominada Expressão Regular.
●Uma expressão regular é definida a partir de
conjuntos básicos (linguagens) e operações de
concatenação e de união.
●As expressões regulares são consideradas
adequadas para a comunicação humano x humano e,
principalmente, para a comunicação humano x
máquina.
●A expressão regular é a maneira mais compacta e
mais simples de descrever conjuntos regulares, e é
usada com essa finalidade em construção de
compiladores, editores, sistemas operacionais,
protocolos, etc.

5. Aspectos Teóricos da Computação
5/26
Expressão Regular, Linguagem Gerada
Uma Expressão Regular (frequentemente abreviada por ER) sobre um alfabeto ∑ é indutivamente
definida como segue:
a) Base de Indução.
a.1) A expressão :
Ø é expressão regular e denota a linguagem vazia.
a.2) A expressão:
e é uma expressão regular e denota a linguagem que contém
exclusivamente a palavra vazia: {e}
a.3) Para qualquer símbolo x Є ∑, a expressão:
X é uma expressão regular e denota a linguagem que contém
exclusivamente a palavra constituída pelo símbolo x: {x}
b) Passo de Indução. Se r e s são expressões regulares e denotam a linguagem R e S,
respectivamente, então:
b.1) União. A expressão (r+s) é expressão regular e denota a linguagem R U S
b.2) Concatenação. A expressão (rs) é expressão regular e denota a linguagem: R S = {uv | u Є
R e v Є S}
b.3) Concatenação sucessiva. A expressão (r
*
) é expressão regular e denota a linguagem R
*

Se r é uma expressão regular, a correspondente linguagem denotada é dita a Linguagem Gerada
por r, sendo representada por:
L(r) ou GERA(R)

6. Aspectos Teóricos da Computação
6/26
Expressão Regular, Linguagem Gerada
A omissão de parênteses em uma ER é usual, respeitando
as seguintes convenções:
●A concatenação sucessiva tem precedência sobre a
concatenação e a união;
●A concatenação tem precedência sobre a união.

7. Aspectos Teóricos da Computação
7/26
Expressão Regular
Detalhando a linguagem gerada pela expressão (a+b)*(aa+bb),
vale que:
●a e b denotam {a} e {b}, respectivamente
●a + b denota {a} U {b} = {a,b} (Lembre-se que o elemento
vazio também está aqui.)
●(a+b)* denota {a,b}*
●aa e bb denotam {a}{a} = {aa} e {b}{b} = {bb},
respectivamente
●(aa + bb) denota {aa} U {bb} = {aa,bb}
●(a+b)*(aa+bb) denota {a,b}*{aa,bb}
Portanto, GERA((a+b)*(aa+bb)) correponde à seguinte linguagem:
{aa,bb,aaa,abb,baa,bbb,aaaa,aabb,abaa,abbb,baaa,babb,bbaa,bb
bb,...}

8. Aspectos Teóricos da Computação
8/26
Exemplo: Expressão Regular
Expressão Regular Linguagem Gerada
aa Somente a palavra aa
ba* Todas as palavras que iniciam por b, seguido por
zero ou mais a's
(a+b)* Todas as palavras sobre {a,b}
(a+b)*aa(a+b)* Todas as palavras contendo aa como subpalavra
a*ba*ba* Todas as palavras contendo exatamente dois b's
(a+b)*(aa+bb) Todas as palavras que terminam com aa ou bb.
(a+e)(b+ba)* Todas as palavras que não possuem dois a
consecutivos.

9. Aspectos Teóricos da Computação
9/26
Expressão Regular → Linguagem Regular
Por definição, uma linguagem regular é regular
se, e somente se, é possível construir um
autômato finito (determinístico, não determinístico
ou de movimentos vazios) que reconheça essa
linguagem. Assim, dada uma expressão regular r
qualquer é possível construir um autômato finito.

10. Aspectos Teóricos da Computação
10/26
Expressão Regular Autômato Finito Correspondente
a
b
a*
aa
bb
aa+bb
a
b
a
e a e
e
e
a e a
b e b
a e a
b e b
e
e
e e
e
Є

11. Aspectos Teóricos da Computação
11/26
ER convertida para Autômato
a*(aa+bb)
a e a
b e b
e
e e
e
e a e
e
e

12. Aspectos Teóricos da Computação
12/26
Gramática Regular
Gramáticas Lineares
Seja G={V,T,P,S} uma gramática. Sejam A e B elementos de V e w uma palavra de T*.
Então G é uma Gramática Linear se todas as suas produções encontram-se em uma e
em somente uma das seguintes formas:
a) Gramática Linear à Direita (abreviada por GLD). Todas as regras de produção são da
forma:
A → wB ou A → w
b) Gramática Linear à Esquerda (abreviada por GLE). Todas as regras de produção são
da forma:
A → Bw ou A → w
c) Gramática Linear Unitária à Direita (abreviada por GLUD). Todas as regras de
produção são como na gramática linear à direita e, adicionalmente:
|w| <= 1
d) Gramática Linear Unitária à Esquerda (abreviada por GLUE). Todas as regras de
produção são como na gramática linear à esquerda e, adicionalmente:
|w| <=1

13. Aspectos Teóricos da Computação
13/26
Gramática Regular
Note-se que, nas gramáticas lineares, o lado direito de uma produção é constituído por,
no máximo, uma variável. Adicionalmente, esta variável, se existir, sempre antecede
(linear à esquerda) ou sucede (linear à direita) qualquer sub-palavra (eventualmente
vazia) de terminais.

14. Aspectos Teóricos da Computação
14/26
Equivalência das Gramáticas Regulares
Seja L uma linguagem. Então:
L é gerada por uma GLD se, e somente se,
L é gerada por uma GLE se, e somente se,
L é gerada por uma GLUD se, e somente se,
L é gerada por uma GLUE
●Ou seja, as diversas formas das gramáticas
lineares são formalismos equivalentes.

15. Aspectos Teóricos da Computação
15/26
Gramática Regular
Uma gramática G é dita uma Gramática Regular,
eventualmente abreviada GR, se G é uma
gramática linear.

16. Aspectos Teóricos da Computação
16/26
Linguagem Gerada
Seja G=(V, T, P, S) uma gramática. A Linguagem
Gerada pela gramática G, denotada por:
L(G) ou GERA(G)
É tal que:
L(G) = {w є T* | S →
+
w}

17. Aspectos Teóricos da Computação
17/26
Exemplo: Gramática Regular: a(ba)*
A linguagem a(ba)* é gerada pelas seguintes gramáticas regulares:
(a) Linear à Direita. G=({S,A}, {a,b}, P, S), e P possui as seguintes
regras de produção
S → aA
A → baA | ε
(b) Linear à Esquerda. G=({S}, {a,b}, P, S), e P possui as seguintes
regras de produção
S → Sba | a
(c)Linear Unitária à Direita. G=({S,A,B}, {a,b}, P, S), e P possui as
seguintes regras de produção
S → aA
A → bB | ε
B → aA
(d)Linear Unitária à Esquerda. G=({S,A}, {a,b}, P, S), e P possui as
seguintes regras de produção
S → Aa | a
A → Sb

18. Aspectos Teóricos da Computação
18/26
Gramática Regular: (a+b)*(aa+bb)
A linguagem (a+b)*(aa+bb) é gerada pelas
seguintes gramáticas regulares:
(a) Linear à Direita. G=({S,A}, {a,b}, P, S), e P
possui as seguintes regras de produção
S → aS | bS | A
A → aa | bb
(b) Linear à Esquerda. G=({S}, {a,b}, P, S), e P
possui as seguintes regras de produção
S → Aaa | Abb
A → Aa | Ab | ε

19. Aspectos Teóricos da Computação
19/26
Gramática Linear à Esquerda e Linear à Direita
Suponha |w| >= 1. Se uma gramática tiver
simultaneamente produções do tipo A → wB
(linear à direita) e do tipo A → Bw (linear a
esquerda), então a correspondente linguagem
gerada poderá não ser regular, ou seja, esta não
é uma gramática regular.
Por exemplo, a linguagem a seguir não é regular:
{ a
n
b
n
| n є N }
Entretanto, é possível desenvolver uma
gramática, com produções lineares à direita e à
esquerda, que gera esta linguagem.

20. Aspectos Teóricos da Computação
20/26
Gramática Regular → Linguagem Regular
Se L é uma linguagem gerada por uma gramática regular, então L é uma linguagem
regular.
Prova: Por indução
Para mostrar que uma linguagem é regular, é suficiente construir um autômato finito que
a reconheça.
Suponha G=(V,T,P,S) uma gramática linear unitária à direita.
Então o AFNε : M=( ∑, Q,δ,q
0
, F)
Tal que: (suponha q
f
não pertence a V):
∑ = T
Q = V U {q
f
}
F = {q
f
}
q
0
= S
δ é construída como ilustrado na tabela (Suponha A e B variáveis e a terminal) simula as
derivações de G, ou seja:
ACEITA(M) = GERA(G)
A demonstração que, de fato, ACEITA(M) = GERA(G) é por indução no número de
derivações. (Vamos omitir essa demonstração mas ela pode ser vista na página 77 do
livro texto.)
Tipo da
Produção
Transição
Gerada
A → ε δ(A,ε) = q
f
A → a δ(A,a) = q
f
A → B δ(A,ε) = B
A → aB δ(A,a) = B

21. Aspectos Teóricos da Computação
21/26
Exemplo: Construção de um AFNε a partir de uma
gramática regular
Considere a seguinte gramática linear unitária à direita,

G=({S,A,B},{a,b},P,S) onde P é tal que:
S → aA
A → bB | ε
B → aA
O AFNε que reconhece a linguagem gerada pela gramática G é:
5 minutos para fazer.

22. Aspectos Teóricos da Computação
22/26
Exemplo: Construção de um AFNε a partir de uma
gramática regular
Considere a seguinte gramática linear unitária à direita,

G=({S,A,B},{a,b},P,S) onde P é tal que:
S → aA
A → bB | ε
B → aA
O AFNε que reconhece a linguagem gerada pela gramática G é:
M = ({a,b}, {S,A,B,q
f
},δ,S,{q
f
})
ProduçãoTransição
S → aA δ(S,a) = A
A → bB δ(A,b) = B
A → ε δ(A,ε) = q
f

B → aA δ(B,a) = A
S q
faA
B
ba
εA

23. Aspectos Teóricos da Computação
23/26
Construção de uma Gramática Regular a partir de um
AFD
Considere o autômato finito determinístico:
M = ({a,b,c}, {q
0
,q
1
,q
2
},δ,q
0
,{q
0
,q
1
,q
2
})
A gramática correspondente regular construída é?
5 minutos.
q
0
q
2b cq
1
a b c

24. Aspectos Teóricos da Computação
24/26
Considere o autômato finito
determinístico:
M = ({a,b,c}, {q
0
,q
1
,q
2
},δ,q
0
,
{q
0
,q
1
,q
2
})
A gramática correspondente
regular construída é?
G = ({q
0
,q
1
,q
2
,S}, {a,b,c}, P,S)
onde P é dado pela tabela:
Construção de uma Gramática Regular a partir de um
AFD
q
0
q
2b cq
1
a b c
Transição Produção
- S → q
0
- q
0
→ ε
- q
1
→ ε
- q
2
→ ε
δ(q
0
,a)=q
0
q
0
→ aq
0
δ(q
0
,b)=q
1
q
0
→ bq
1
δ(q
1
,b)=q
1
q
1
→ bq
1
δ(q
1
,c)=q
2
q
1
→ cq
2
δ(q
2
,c)=q
2
q
2
→ cq
2

25. Aspectos Teóricos da Computação
25/26
Ler
●Seçao 3.6 do livro.

26. Aspectos Teóricos da Computação
26/26
Exercícios
1. (Exercício 3.7 do livro) Desenvolva expressões regulares que gerem as seguintes linguagens sobre
∑ = {a,b}:
(a) {w | w tem no máximo um par de a como subpalavra e no máximo um par de b como subpalavra.
(b){w | qualquer para de a antecede qualquer par de b}
(c){w | w não possui aba como subpalavra}
2. Descreva em palavras as linguagens geradas pelas seguintes expressões regulares:
(a) (aa+b)*(a+bb)
(b) (b+ab)*(e +a)
(c) (aa +bb + (aa+bb) (ab+ba)(aa+bb))*