Lista AFd

Autômatos Finitos DETERMINÍSTICOS

1) Construa um AFD para as seguintes linguagens:

a) {w {0,1}* | w tem tamanho 3}
b) {w {0,1}* | w tem tamanho menor que 3}
c) {w {0,1}* | w tem tamanho maior que 3}
d) {w {0,1}* | w tem tamanho múltiplo de 3}
e) {w {0,1}* | cada 0 de w é imediatamente seguido de, no mínimo dois 1´s}
f) {w {0,1}* | os primeiros 4 símbolos de w contêm, no mínimo, dois 1´s}
g) {w {0,1}* | w NÃO contém 000 nem 111}
h) {w {0,1}* | os últimos três símbolos de w NÃO são 000}
i) {w {0,1,2}* | w tem número par de 0´s, par de 1´s e par de 2´s}
j) { uavbxcy | u,v,x,y {a,b,c}*}
k) {w {a,b}* | w começa com a e tem tamanho par}
l) {w {a,b}* | w nunca tem mais de dois a´s consecutivos}
m) {w {a,b}* | w tem um número ímpar de ab´s}
n) {w {a,b}* | |w|  2 e os a´s (se houver) precedem os b´s (se houver)}
o) {w {a,b,c,d}* | os a´s (se houver) precedem os b´s (se houver) e os c´s (se houver) precedem os d´s (se houver)}
p) { xban | x {a,b}*, n  0 e x tem um número par de a´s}
q) { xamban | x {a,b}*, m+n é par e x não termina em a}

2) Seja o primeiro símbolo de uma palavra a posição 1, o segundo símbolo é a posição 2, e assim por diante. Seja i um número natural qualquer: a posição i indica uma posição qualquer na palavra, as posições 2i (ou 2i+2, ou 2i+4, etc.) indicam as posições pares dentro da palavra, as posições 2i-1 (ou 2i+1, 2i+3, etc.) indicam as posições ímpares. Construa AFD´s para as seguintes linguagens sobre o alfabeto {0,1}:

a) O conjunto de palavras em que o símbolo na posição 2i é diferente do símbolo na posição 2i+2, para i  1.
b) O conjunto de palavras em que o símbolo na posição 2i-1 é diferente do símbolo na posição 2i, para i  1.
c) O conjunto de palavras em que o símbolo na posição i é diferente do símbolo na posição i+2, para i  1.
d) O conjunto de palavras com número par de 0´s nas posições pares e número ímpar de 0´s nas posições ímpares.
e) O conjunto de palavras de tamanho par com 1´s