Lista Exercícios DFA

Prévia do material em texto

Exercícios – Lista 2 
 
1. Desenvolva AFD que reconheçam as seguintes linguagens sobre o alfabeto ∑ = {a,b} 
a) {w | o sufixo de w é aa} 
b) {w | w possui aaa como subpalavra} 
c) {w | w possui número ímpar de a e número ímpar de b} 
d) {w | w possui número par de a e ímpar de b ou w possui número par de b e ímpar de 
a} 
e) {w | o quinto símbolo da direita para a esquerda de w é a} Dica: o autômato resultante 
possui um número relativamente grande de estados. 
 
2. Desenvolva autômatos finitos não determinísticos que reconheçam as seguintes 
linguagens sobre o alfabeto ∑ = {a, b}. 
a) Qualquer ocorrência de a é imediatamente sucedida por b. 
b) Qualquer ocorrência de a é imediatamente antecedida e imediatamente sucedida por 
b. 
 
3. Quais das seguintes palavras são aceitas pelos autômatos finitos não determinísticos 
sobre o alfabeto ∑ = {a,b}. 
 
a) e, aa, bb, aba, bbaaba, abababababa. 
 
 
 
 
 
b) e, bb, bab, bbbaaa, bbbbbbababababa 
 
 
3. Desenvolva autômatos finitos não determinísticos, com ou sem movimentos vazios, que 
reconheçam as seguintes linguagens sobre o alfabeto ∑ = {a,b} 
 
a) {w1w2w1 | w2 é qualquer e |w1| = 3 } 
b) {w | o decimo símbolo da direita para a esquerda de w é a} 
c) {w | w possui número de símbolos a e b e (qualquer prefixo de w possui, no máximo, 
dois a a mais que b ou qualquer prefixo de w possui, no máximo, dois b a mais que a) } 
 
4. Desenvolva, sobre o alfabeto ∑ = {a,b,c}: 
 
a) Autômato finito não determinístico que reconheça a seguinte linguagem: 
 {w | a ou bb ou ccc é sufixo de w} 
 
b) Autômato finito não determinístico com movimentos vazios que reconheça a seguinte 
linguagem: 
 {w | aa ou bb é subpalavra e cccc é sufixo de w}