AFD's Do Satanás

1. Faça os autômatos finitos determinísticos para as seguintes linguagens:
a. {a,aa,b,bb}
b. {a,aa,aaa}
c. {an | n é par}
d. {an | n é ímpar}
e. {an | n é múltiplo de 3}
f. {an | n é múltiplo de 5}
g. {anbbam | n,m ≥0}
h. {anbbam | n,m > 0}
i. {anbbam | n> 0 e m≥0}
j. {anb2m | n,m>0}
2. Considere o alfabeto ∑ = {0,1}. O conjunto de todas as palavras sobre o alfabeto é dado por ∑*. A seguir, faça a representação da linguagem sobre o alfabeto conforme a descrição dada.
a. L1 é a linguagem mais simples que existe; não contém palavras:
b. L2 é a linguagem que contém uma única palavra: a palavra vazia
c. L3 é a linguagem que contém uma única palavra: 0.
d. L4 é a linguagem que contém duas palavras: λ e 0
e. L6 é a linguagem constituída de toda palavra de tamanho par cuja primeira metade só contém
0’s e cuja segunda metade só contém 1’s. Esta linguagem também é conhecida como duplo-bal.
3. Apresente a Linguagem e a descrição completa incluindo a tabela de transição para os diagramas de estados dos AFDs abaixo:
a)

b)

c)

4. Dado o AFD abaixo:

a)
b)
c)
d)

Justifique se ele é determinista ou não determinista
Apresenta a tabela de transição e especificação do AF
Apresente a transição estendida para a palavra 0011100
Que linguagem este AF reconhece.

5. Dada as linguagens, apresente os AFDs. Caso não seja possível desenvolver AFD ou AFND justifique sua resposta: a) L = Σ* para Σ = {a,b}
b) L = a para Σ = {a,b}
c) L = aa para Σ = {a,b}
d) L = a* para Σ = {a,b}
e) L = { } para Σ = {a,b}
f) L = {anbn | n>=0 } para Σ = {a,b}
g) Conjunto de todas as palavras que não contém aa sobre o alfabeto Σ = {a,b,c}
h) Conjunto de todas as palavras sobre Σ = {a,b,c} onde cada b é seguido de pelo menos um c
i) Conjunto de strings sobre Σ = {a,b} onde o número de a é divisível por 3
j) Conjunto de strings sobre Σ = {0,1} e w tem tamanho ímpar
k) L = {anb2m | n>0 e m>=0}
l) L = {zw | w pertence a {z,n}*}