Das seis alternativas: (1) a, onde a ∈ Σ, (2) ε, (3) ∅, (4) R1 ∪R2, onde R1 e R2 são expressões regulares, (5) R1 ◦R2, onde R1 e R2 são expresso...

Das seis alternativas: (1) a, onde a ∈ Σ, (2) ε, (3) ∅, (4) R1 ∪R2, onde R1 e R2 são expressões regulares, (5) R1 ◦R2, onde R1 e R2 são expressões regulares, ou (6) R∗1, onde R1 é uma expressão regular. Essas expressões representam as linguagens {a}, {ε}, { }, L(R1) ∪ L(R2), L(R1) ◦ L(R2) e L(R1)∗, respectivamente, onde L(R) denota a liguagem descrita por R. As linguagens dos casos (1), (2) e (3) são regulares, pois são reconhecidas, respectivamente, pelos seguintes AFNs: a Para os casos (4), (5) e (6), usamos o fato de que a classe das linguagens regulares é fechada sobre as operações de união, concatenação e estrela. Portanto, se L(R1) e L(R2), em (4) e (5), ou somente L(R1), em (6), são regulares, então sua união, concatenação e operação estrela também são. 4. Seja A uma linguagem finita, e n o comprimento máximo das cadeias de A (i.e., |w| ≤ n para todo w ∈ A). Prove que todo AFD que reconheçe A tem pelo menos n + 1 estados. Dica: lembre de como foi escolhido o comprimento de bombeamento na prova do Lema do Bombeamento. Conforme visto na demostração do Lema do Bombeamento, se um AFD tem p estados, então p é um comprimento de bombeamento para a linguagem do autômato e as cadeias da linguagem que possuem comprimento maior ou igual a p podem ser bombeadas. Se bombeamos uma cadeia “para cima”, obtemos outras infinitas cadeias da linguagem, de comprimento maior que a cadeia original. Suponha, assim, que um AFD que reconhece A tem uma quantidade de estados p ≤ n. Então, existe pelos menos uma cadeia w ∈ A, de comprimento maior ou igual a p, que pode ser bombeada. Bombeando “para cima” essa cadeia obtemos infinitas outras cadeias de A de comprimento maior que n. No entanto, isso contradiz a afirmação inicial de que A é finita e de que n é o comprimento máximo de suas cadeias. Portanto, nenhum AFD que reconheça A pode ter uma quantidade de estados p ≤ n. 5. Prove que a linguagem L = {0n1m| 0 ≤ n ≤ m} não é regular. Resposta: Suponha que L é regular, e seja p o comprimento de bombeamento. Esco-lhemos a cadeia de teste s = 0p1p, que pertence a L e tem comprimento maior que p. Subdividimos a cadeia na forma s = xyz. Pela condição (3) do Lema do Bombeamento, xy deve conter unicamente 0s, e pela condição (2), y contém pelo menos um 0. Supo-nha, então, y = 0k, com 1 ≤ k ≤ p. Pelo Lema do Bombeamento, a cadeia xyyz deve pertencer a L. No entanto, xyyz = 0p+k1p e a quantidade de 0s é maior que a de 1s, o que contradiz o Lema. Assim, L não pode ser regular. 6. Considere o seguinte AFN, com alfabeto Σ = {0, 1}. q0 q1 q2 q3 1 0,1 0,1 0,1 (a) Descreva a linguagem reconhecida pelo AFN. Resposta: o AFN reconhece a linguagem composta por todas as cadeias que contêm um 1 na penúltima ou na antepenúltima posição. (b) Escreva uma expressão regular equivalente ao AFN. Resposta: R = (0 ∪ 1)∗1(0 ∪ 1)(ε ∪ 0 ∪ 1).
[object Object]
[object Object]
[object Object]
[object Object]
[object Object]
[object Object]
[object Object]
[object Object]
[object Object]
[object Object]
a) Somente as afirmativas 1, 2 e 3 são verdadeiras.
b) Somente as afirmativas 2, 3 e 5 são verdadeiras.
c) Somente as afirmativas 1, 2, 3 e 5 são verdadeiras.
d) Somente as afirmativas 1, 3 e 4 são verdadeiras.
e) Todas as afirmativas são verdadeiras.