lista1.2 ExpressoesRegulares[solucao]

Prévia do material em texto

Fundamentos de Teoria da Computac¸a˜o DCC/ICEx/UFMG
Prof. Ma´rio S. Alvim 2017/02
SOLUC¸A˜O DE LISTA DE EXERCI´CIOS
Lista 1 - Parte 2/3
(Linguagens Regulares: Expresso˜es Regulares)
Leitura necessa´ria:
• Introduc¸a˜o a` Teoria da Computac¸a˜o, 2a Edic¸a˜o (Michael Sipser):
– Cap´ıtulo 1.3: Expresso˜es Regulares
Revisa˜o.
1. Responda formalmente a`s seguintes perguntas:
(a) O que e´ uma expressa˜o regular? Deˆ sua sintaxe.
Soluc¸a˜o do professor: R e´ uma expressa˜o regular (ER) sobre um alfabeto Σ se R for:
1. a, para algum a no alfabeto Σ (representando a linguagem {a}),
2. � (representando a linguagem {�}),
3. ∅ (representando a linguagem vazia),
4. (R1 ∪R2), onde R1 e R2 sa˜o expresso˜es regulares,
5. (R1 ◦R2), onde R1 e R2 sa˜o expresso˜es regulares,
6. (R∗1), onde R1 e´ uma expressa˜o regular.
(b) Em que sentido dizemos que expresso˜es regulares sa˜o equivalentes a linguagens regulares?
Soluc¸a˜o do professor: Linguagens regulares e expresso˜es regulares sa˜o equivalentes no sentido
de que toda linguagem regular e´ exprimı´vel atrave´s de uma expressa˜o regular, e toda expressa˜o
regular denota uma linguagem regular.
Exerc´ıcios.
2. (Sipser 1.12)
Soluc¸a˜o do professor: Note que a linguagem
D = {w | w conte´m um nu´mero par de a’s e um nu´mero ı´mpar de b’s e na˜o conte´m a subcadeia ab}
pode ser reescrita como
D = {w |w conte´m um nu´mero par de a’s e um nu´mero ı´mpar de b’s,
e nenhum b ocorre depois de algum a}.
Isto quer dizer que a linguagem D esta´ contida na linguagem b∗a∗ em que nenhum b ocorre apo´s algum
a. Agora apenas precisamos restringir a linguagem b∗a∗ de forma a ter um nu´mero ı´mpar de b’s e
1
um nu´mero par de a’s. Isto pode ser feito concatenando b(bb)∗ (prefixos com um nu´mero ı´mpar de
b’s) com (aa)∗ (sufixos com um nu´mero par de a’s), o que resulta na seguinte expressa˜o regular para
a linguagem D:
b(bb)∗(aa)∗.
Um AFD de 5 estados para a linguagem esta´ representado na Figura a seguir.
Soluc¸a˜o do exerc´ıcio 1.12
3. (Sipser 1.18 - Todos os itens, menos o item (h))
Soluc¸a˜o do professor:
a) 1(0 ∪ 1)∗0
b) 0∗10∗10∗1(0 ∪ 1)∗ ou (0 ∪ 1)∗1(0 ∪ 1)∗1(0 ∪ 1)∗1(0 ∪ 1)∗
c) (0 ∪ 1)∗0101(0 ∪ 1)∗
d) (0 ∪ 1)∗(0 ∪ 1)∗0(0 ∪ 1)∗
e) 0((0 ∪ 1)(0 ∪ 1))∗ ∪ 1(0 ∪ 1)((0 ∪ 1)(0 ∪ 1))∗
f) (0 ∪ 10)∗(� ∪ 11+) (Dica: construa um AFD para a linguagem e o converta em uma ER.)
g) � ∪ (0 ∪ 1) ∪ (0 ∪ 1)2 ∪ (0 ∪ 1)3 ∪ (0 ∪ 1)4 ∪ (0 ∪ 1)5
i) ((0 ∪ 1)1)∗
j) (1 ∪ �)0+0+ ∪ 0+(1 ∪ �)0+ ∪ 0+0+(1 ∪ �)
k) � ∪ 0
l) 1∗(01∗01∗)∗ ∪ 0∗10∗10∗
m) ∅
n) (0 ∪ 1)+
4. (Sipser 1.19 - Item (a))
Soluc¸a˜o do professor: Vamos construir um AFN para a ER
(0 ∪ 1)∗000(0 ∪ 1)∗
usando o procedimento descrito no Lema 1.55.
5. (Sipser 1.20 - Itens (a), (e), (g))
2
Soluc¸a˜o do exerc´ıcio 1.19 - AFN para 0
Soluc¸a˜o do exerc´ıcio 1.19 - AFN para 1
Soluc¸a˜o do exerc´ıcio 1.19 - AFN para 0 ∪ 1
Soluc¸a˜o do exerc´ıcio 1.19 - AFN para (0 ∪ 1)∗
Soluc¸a˜o do exerc´ıcio 1.19 - AFN para 000
Soluc¸a˜o do exerc´ıcio 1.19 - AFN para (0 ∪ 1)∗000(0 ∪ 1)∗
Soluc¸a˜o do professor:
a) L = a∗b∗. � ∈ L, a ∈ L, ba /∈ L, aba /∈ L.
e) L = Σ∗aΣ∗bΣ∗aΣ∗. aba ∈ L, aaabaab ∈ L, � /∈ L, aab /∈ L.
g) L = (� ∪ a)b. b ∈ L, ab ∈ L, � /∈ L, a /∈ L.
6. (Sipser 1.21)
Soluc¸a˜o do professor:
3
a) Eliminando os estados na ordem 1, 2, obtenho a ER: (a∗b)(a ∪ ba∗b)∗
b) Eliminando os estados na ordem 1, 3, 2, obtenho a ER: �∪ (a∪ b)(a∪ b(b∪ a(a∪ b)))∗(b(�∪ a)),
que pode ser reescrita de forma mais simples como � ∪ (a ∪ b)(a ∪ bb ∪ baa ∪ bab)∗(b ∪ ba).
4