ftc lista ADF

Prévia do material em texto

BCC244-Teoria da Computação DECOM
Prof. Lucília Figueiredo ICEB - UFOP
Lista de Exercícios 01
1 Linguagens
1. Liste os strings de cada uma das seguintes linguagens:
a) ∅∗ R: ∅∗ = {λ} b) ∅+ R: ∅+ = ∅
c) {λ}∗ R: {λ}∗ = {λ} d) {λ}+ R: {λ}+ = {λ}
e) {0}∗ R: {0}∗ = {λ, 0, 00, 000, . . .} f) {0}+ R: {0}+ = {0, 00, 000, . . .}
2. Em que casos L∗ e L+ são finitas?
R: Somente se L = ∅ ou se L = {λ}
3. Seja Σ um alfabeto. Explique que palavras pertencem a cada uma das seguintes linguagens:
• Σn, para um determinado n ≥ 0
R: Σn = {w ∈ Σ∗ | |w| = n}
• (Σ ∪ {λ})n, para um determinado n ≥ 0
R: Σn = {w ∈ Σ∗ | |w| ≤ n}
4. Sejam Σ = {a, b}, A = {a}Σ+ e B = Σ∗ {b}. Descreva cada uma das linguagens a seguir,
especificando a propriedade que deve ser satisfeita pelos strings da linguagem. (O primeiro
item é resolvido como exemplo).
• AA R: AA = {awau |w, u ∈ Σ+}
Todos os strings com comprimento ≥ 4, contendo pelo menos dois as.
• AB R: AB = {awb |w ∈ Σ+}
Todos os strings com comprimento ≥ 3, que começam com a e terminam com b.
• BB R: AB = {wbub |w ∈ Σ∗}
Todos os strings com comprimento ≥ 2, contendo pelo menos dois bs.
• A ∩B R: AB = {awb |w ∈ Σ∗}
Todos os strings com comprimento ≥ 2, começando com a e terminando com b.
• A−B R: AB = {awa |w ∈ Σ∗}
Todos os strings com comprimento ≥ 2, que começam e terminam com a.
• B − A R: AB = {bw |w ∈ Σ∗}
Todos os strings com comprimento ≥ 1, que começam e terminam com b.
2 Autômatos Finitos e Expressões Regulares
1. Para cada uma das linguagens a seguir, sobre o alfabeto {0, 1}, desenhe um Autômato Finito
Determinista que reconheça a linguagem e escreva uma expressão regular que a representa.
(a) O conjunto dos strings com prefixo 01.
R: 01(0 + 1)∗
0
1
1
0
0,1
0,1
(b) O conjunto dos strings que não contêm 01 como sufixo.
R: λ+ (0 + 1)∗ (0 + 11)
0
1
1
0
0
1
(c) O conjunto dos strings que não contêm 01 como substring.
R: 1∗ 0∗
0
1
1
0
0,1
(d) O subconjunto dos strings de {0} ∗ {1}∗ com número par de 0s.
R: (00)∗ 1∗
0
1 0
0
0
1 0,1
(e) O conjunto dos strings com no máximo 3 símbolos.
R: (0 + 1 + λ)(0 + 1 + λ)(0 + 1 + λ)
0,1 0,1 0,1 0,1
0,1
(f) O conjunto dos strings que contêm pelo menos um 0 e um 1.
R: (0+1 + 1+0)(0 + 1)∗)
0
1
1
0
0
1
0,1
(g) O conjunto dos strings em que todo 0 é seguido de pelo menos dois símbolos.
R: (1∗0(0 + 1)(0 + 1))∗
0
1
0
1
0
1
0
1
1
0
(h) O conjunto dos strings que contêm pelo menos um 00, mas nenhum 11.
R: (0 + 10)(10)∗0(0∗10)∗
0
1
0
1
0
1
0
1
0
1
0,1
2. Para cada uma das linguagens a seguir, sobre o alfabeto {0, 1}, desenhe um Autômato Finito
Não Determinista que reconheça a linguagem.
(a) {w ∈ {0, 1}∗ | o primeiro e o penúltimo símbolos de w são 1}.
R:
1 1
0,1
0,1
(b) {w ∈ {0, 1}∗ | o último símbolo de w é diferente do primeiro}.
R:
0
1
1
0,1
0
0,1
(c) {w ∈ {0, 1}∗ | os três últimos símbolos de w não são 000}
R:
1
0
0,1
1 0,1
1
0
0,1
1
(d) {x10n |n ≥ 0, x ∈ {0, 1}e x tem número par de 0s}.
R:
1
0
1
1
0
0
3. Desenhe Autômatos Finitos Deterministas que reconheçam as linguagens A = 0(0 + 1)∗ e
B = (0 + 1)∗1.
R:
MA :
q0
q1
q2
0
1
0,1
0,1
MB :
q3 q4
0
1
1
0
Desenhe também Autômatos Finitos Deterministas que reconheçam as linguagens a seguir.
(a) A ∪B
R:
(q0, q3)
(q1, q3) (q1, q4)
(q2, q4) (q2, q3)
0
1
0
1
1
0
1
0
0
1
(b) A ∩B
R: O autômato é o mesmo da resposta anterior, exceto que o apenas o estado (q1, q4) é um
estado final.
(c) A−B
R: O autômato é o mesmo da resposta anterior, exceto que o apenas o estado (q1, q3) é um
estado final.
4. Quais das seguintes afirmativas são verdadeiras:
(a) Toda linguagem regular pode ser definida a partir de linguagens finitas, usando-se apenas
as operações de união, concatenação e estrela de Kleene.
(b) Toda linguagem regular é finita.
(c) A sintaxe de HTML pode ser expressa por meio de expressões regulares.
(d) Não existe algoritmo capaz de decidir, dada uma expressão regular, se a linguagem deno-
tada por esta expressão é vazia ou não.
(e) Existe um algoritmo para decidir, dada uma expressão regular, se a linguagem denotada
por esta expressão é finita ou é infinita.
R: São corretas as afirmativas (a) e (e)
5. Converta o seguinte autômato finito não determinista em um determinista equivalente.
0 1
2 3
b
a
λ
a
a
a
b
b
a
{0, 2} {1, 2}
{3} {2}
b
a
a
b
a
b
a
a
3 Gramáticas Lineares à Direita e à Esquerda
1. Considere a seguinte gramática Linear à Direita G:
S → aS || bA |λ
A → bbA | aS
(a) Desenhe um Autômato Finito Não Determinista) que reconheça a linguagem L(G).
R:
S A
a
b
a
b
b
(b) Escreva uma expressão regular que represente a linguagem L(G)
R: a∗ (b (bb)∗ a)∗
4 Lema do Bombeamento
1. Considere um autômato finito M com n estados. Explique porque se M reconhece um string
w, tal que |w| ≥ n, então a linguagem aceita por M – L(M) – é infinita.
R: Se M tem n estados, então o maior string que pode ser reconhecido por M , em uma com-
putação em que nenhum estado é repetido, tem comprimento n− 1. Portanto, se M reconhece
um string w, tal que |w| ≥ n, então o caminho da computação de M sobre w envolve um loop.
Então, este loop poderia ser repetido qualquer número de vezes, o que significa que a linguagem
reconhecida por M é infinita.
2. Prove que cada uma das linguagens a seguir não é regular, usando o Lema do Bombeamento.
(a) L = {w1n |w ∈ {0, 1}∗ e |w| = n}
R: Suponha, por contradição, que L seja regular. Então L deve satisfazer o Lema do
Bombeamento. Vamos provar que isso não acontece e que, portanto, L não é regular.
Seja p o número de bombeamento de L e considere o string u = 0p1p. Temos que u ∈ L
e |u| = 2p ≥ p. De acordo com o Lema do Bombeamento, devemos ter que u pode ser
dividido em 3 partes – u = xyz – satisfazendo as seguintes condições:
i) |y| > 0
ii) |xy| < p
iii) xyiz ∈ L, para todo i ∈ N
Entretanto, para qualquer divisão u = xyz satisfazendo i) e ii), temos que y contém
apenas 0s (já que |xy| < p). Portanto, xy2z contém maior número de zeros do que de 1s,
e, portanto, não é da forma w1n, onde |w| = n, isto é, xy2z 6∈ L.
(b) L = {10n1n |n ≥ 1}
R: Suponha, por contradição, que L seja regular. Então L deve satisfazer o Lema do
Bombeamento. Vamos provar que isso não acontece e que, portanto, L não é regular. Seja
p o número de bombeamento de L e considere o string u = 10p1p. Temos que u ∈ L e
|u| = 2p+ 1 ≥ p. De acordo com o Lema do Bombeamento, devemos ter que u pode ser
dividido em 3 partes – u = xyz – satisfazendo as seguintes condições:
i) |y| > 0
ii) |xy| < p
iii) xyiz ∈ L, para todo i ∈ N
Entretanto, para qualquer divisão u = xyz satisfazendo i) e ii), temos que y não contém
nenhum 1 da parte final de u (já que |xy| < p). Portanto, xy2z tem a forma 10k1p, onde
k > p, ou seja xy2z 6∈ L.
3. Prove que cada uma das linguagens a seguir não é regular, usando propriedades de fecho.
(a) L = {0m1n |n,m ≥ 0, n 6= m}
R: Suponha, por contradição, que L seja regular. Então temos que o seu complemento
L é regular. Entretanto, L = {0n1n |n ≥ 0}, que já provamos anteriormente que não é
regular. Portanto, L não é regular.
(b) L = {w ∈ {0, 1}∗ | o número de 0s em w é par e o número de 1s é primo}
R: Suponha, por contradição, que L seja regular. Temos que L1 = 1∗ é regular. Então
L ∩ L1 é uma linguagem regular, já que a classe das linguagens regulares é fechada em
relação à operação de interseção. Entretanto, L∩L1 = {1n |n é primo}, que já provamos
anteriormente que não é regular. Portanto, L não é regular.