UNIVERSIDADE FEDERAL DE UBERLÂNDIA
Faculdade de Computação
Disciplina : Teoria da Computação
Professora : Sandra de Amo
Lista de Exercı́cios no 2
Revisão de Autômatos
1. Fazer os seguintes exercı́cios do Livro texto Introduction to Theory of Computation - Michael Sipser - 2a Edição - Capitulo 1. Alguns destes exercicios têm sua solução apresentada
no livro texto. Tente primeiro fazer os exercicios propostos depois confira no livro se estão
na lista dos exercicios com soluções.
(a) 1.4
(b) 1.5
(c) 1.6
(d) 1.8
(e) 1.9
(f) 1.10
(g) 1.16: Neste exercicio, primeiro transforme o autômato em um autômato sem movimento e depois transforme este último autômato em um autômato determinista.
2. Reveja o slide de construção do slide “Star” e responda: Por que instroduzir um novo
estado inicial ? Por que não considerar o antigo estado como inicial e torná-lo também
um estado final para que a linguagem L(M∗ ) aceite a palavra vazia ?
3. Prove que as seguintes linguagens são regulares exibindo um autômato que as reconheça:
(a) Conjunto de todos as palavras com três zeros consecutivos.
(b) Conjunto de todas as palavras tais que cada bloco de 5 simbolos consecutivos contém
pelo menos 2 zeros.
(c) Conjunto de todas as palavras com no máximo um par de zeros consecutivos e no
máximo um par de 1’s consecutivos.
(d) Conjunto de todas as palavras que n ao contém 101 como subpalavra.
4. Seja L uma linguagem regular sobre o alfabeto Σ e sejam Rev(L), Prefix(L) e Sufix(L) as
linguagens definidas a seguir:
1
(a) Rev(L) = { w = a1 ...an ∈ Σ∗ | an ...a1 ∈ L }
(b) Prefix(L) { w ∈ Σ∗ | existe y ∈ Σ∗ tal que wy ∈ L }, isto é, Prefix(L) é constituida
dos prefixos de L.
(c) Sufix(L) { w ∈ Σ∗ | existe y ∈ Σ∗ tal que yw ∈ L }, isto é, Sufix(L) é constituida dos
sufixos de L.
Mostre que estas 3 linguagens são regulares (supondo que L é uma linguagem regular, é
claro).
5. Sejam M1 e M2 dois autômatos, e seja M o autômato construı́do (informalmente) da
seguinte maneira a partir dos autômatos M1 e M2 :
• Para cada flecha chegando num estado final q de M1 e partindo de um estado q 0
de M1 , acrescente uma flecha saindo de q 0 e chegando no estado inicial de M2
(mantendo o mesmo label).
• Se é reconhecida pelo autômato M2 então os estados finais de M são os estados de
F1 ∪ F2 .
• Se não é reconhecida pelo autômato M2 então os estados finais de M são os estados
de F2 .
Pede-se:
(a) Dar uma descrição formal do autômato M descrito acima.
(b) Qual a linguagem reconhecida por M ? Justifique sua resposta.
6. UM CIRCUITO LÓGICO :
Especificar um autômato finito correspondendo ao circuito lógico ilustrado na figura 1.
As portas marcadas com “.” são portas AND, as marcadas com “+” são portas OR e as
marcadas com “ ˜ ” são portas NOT. As saidas destas portas respeitam a tabela verdade
dos conectivos lógicos.
Supõe-se que o estado inicial deste circuito corresponde a y1 = 0 e y2 = 0, isto é, os
impulsos nas saı́das das portas D e E são nulos. Uma sequência de impulsos (0 ou 1) que
entra no circuito é aceita se o último impulso que sai pela porta F é 1.
2
A
y1
+
D
Input x
Output
B
F
y2
+
E
C
7. UMA REDE NEURONAL :
Especificar um autômato finito correspondendo à rede neuronal ilustrada na figura 2.
Historicamente, os autômatos finitos foram primeiramente utilizados para modelar redes
neuronais. Na figura 2, os elementos representados por triângulos são neurônios. Cada
neurônio tem uma sinapse excitatórias (bolas brancas) e sinapses inibitórias (bolas pretas).
Um neurônio produz um output 1 se o número de sinapses excitatórias com inputs 1 excede
o número de sinapses inibitórias com inputs 1 de no mı́nimo o valor marcado no interior do
neurônio. Assuma que exista tempo suficiente entre as mudanças nos valores dos inputs
para que os sinais se propaguem e para que a rede neuronal atinja uma configuração estável.
Assuma que os valores iniciais das saı́das y1 , y2 e y3 é zero.
Estados finais do autômato correspondem a saı́das 1 no Output da rede neuronal.
3
Input
◦
◦ 2
◦
y1
◦
• 1
◦
y2
◦
◦ 1
•
◦
◦ 2
Output
y3
8. UM BRINQUEDO :
Especificar um autômato finito correspondendo ao brinquedo ilustrado na Figura 1 no final
desta lista. Os movimentos das alavancas x,y,z bem como as direções que as bolas tomam
após a passagem pelas alavancas estão descritos na Figura 1. As bolas pretas (0-bolas)
entram pela entrada A e as bolas brancas (1-bolas) entram pela entrada B. Uma sequência
de bolas é vencedora se a última bola sai pela saı́da D.
9. Para cada uma das expressões regulares seguintes, dê duas palavras que pertençam à
linguagem aceita pela expressão, duas que não pertencem e dê o autômato finito equivalente
(pode ser não determinista).
(a) 0∗ (11)∗ 0∗
(b) [(1 + 0)(1 + 0)]∗
10. Para cada um dos autômatos finitos deterministas descritos na Figura 2 do final desta lista
encontre a expressão regular correspondente.
11. Prove as seguintes identidades para expressões regulares r, s, t. Aqui r = s significa que
L(r) = L(s) (onde L(r) = linguagem associada a r).
(a) r + s = s + r
(b) (r + s) + t = r + (s + t)
(c) (rs)t = r(st)
(d) r(s + t) = rs + rt
(e) (r + s)t = rt + st
(f) ∅∗ = (g) (r∗ )∗ = r∗
(h) ( + r)∗ = r∗
(i) (r∗ s∗ )∗ = (r + s)∗
12. No que segue, r, s, t são expressões regulares. Diga se é verdadeiro ou falso e prove sua
afirmação :
4
(a) (rs + r)∗ r = r(sr + r)∗
(b) s(rs + s)∗ r = rr∗ s(rr∗ s)∗
(c) (r + s)∗ = r∗ + s∗
13. Mostrar que as seguintes linguagens não são regulares, utilizando para isto o lema do
bombeamento para linguagens regulares:
(a) {0m 1n 0m+n | m ≥ 1, n ≥ 1}
(b) {w | w = wR }, onde wR é a palavra reversa de w.
14. Mostrar que as seguintes linguagens não são regulares.
(a) L = conjunto das palavras do tipo w0wR onde w é uma palavra de zeros e uns
qualquer e wR é a palavra reversa de w.
(b) L = {ai | i é primo}
(c) L = {ai | i é um quadrado perfeito }
5
Figura 1: Um brinquedo
6
Figura 2: Autômatos
7