Automatos Finitos

Autômatos Finitos DETERMINÍSTICOS

1. Construa um AFD para as seguintes linguagens:

1. {w ∈{0,1}* | w tem tamanho 3}
2. {w ∈{0,1}* | w tem tamanho menor que 3}
3. {w ∈{0,1}* | w tem tamanho maior que 3}
4. {w ∈{0,1}* | w tem tamanho múltiplo de 3}
5. {w ∈{0,1}* | cada 0 de w é imediatamente seguido de, no mínimo dois 1´s}
6. {w ∈{0,1}* | os primeiros 4 símbolos de w contêm, no mínimo, dois 1´s}
7. {w ∈{0,1}* | w NÃO contém 000 nem 111}
8. {w ∈{0,1}* | os últimos três símbolos de w NÃO são 000}
9. {w ∈{0,1,2}* |  w tem número par de 0´s, par de 1´s e par de 2´s}
10. { uavbxcy | u,v,x,y ∈{a,b,c}*}
11. {w ∈{a,b}* | w começa com a e tem tamanho par}
12. {w ∈{a,b}* | w nunca tem mais de dois a´s consecutivos}
13. {w ∈{a,b}* | w tem um número ímpar de ab´s}
14. {w ∈{a,b}* | |w| ≥ 2 e os a´s (se houver) precedem os b´s (se houver)}
15. {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)}
16. { xban | x ∈{a,b}*, n ≥ 0 e x tem um número par de a´s}
17. { xamban | x ∈{a,b}*, m+n é par e x não termina em a}

1. 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}:

1. 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.
2. 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.
3. 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.
4. 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.
5. O conjunto de palavras de tamanho par com 1´s nas posições pares, acrescido das palavras de tamanho ímpar com 1´s nas posições ímpares.

1. Faça um AFD para {0}{0,1}* ∪ {0,1}*{1}. Minimize o AFD.

1. Minimize todos os AFD´s do exercício 2.

1. Monte um AFD para a união e outro AFD para a interseção das linguagens dos exercícios 1.d) e 1.e)

1. Construa AFDs para as linguagens:

1. L1 = {w ∈{0,1}* | o tamanho de w é divisível por 3}
2. L2 = {0w0 | w ∈{0,1}* }
3. L1 ∩ L2

Autômatos Finitos NÃO-DETERMINÍSTICOS

1. Construa AFN´s para as seguintes linguagens sobre {a,b,c}:

1. O conjunto de palavras com, no mínimo, 3 ocorrências de abc.
2. O conjunto de palavras com, no mínimo, 3 ocorrências de a´s ou 3 ocorrências de b´s ou 3 ocorrências de c´s.
3. O conjunto de palavras com sufixo abc e bca.
4. O conjunto de palavras em que existem duas ocorrências de abc com um número ímpar de símbolos entre elas.
5. {w ∈{0,1}* | |w| ≥ 4  e o segundo e o penúltimo símbolos são ambos 1}
6. {w ∈{0,1}* | 00 não aparece nos últimos 4 símbolos de w}
7. {w ∈{0,1}* | entre dois 1´s de w há sempre um número par de 0´s, exceto nos últimos 4 símbolos}
8. {w ∈{0,1}* | w tem uma subpalavra constituída de dois 1´s separados por um número par de símbolos}

1. Sejam as linguagens da forma Ln = {xyx | x,y ∈ {a,b}* e |x| = n}. Determine o menos número de estados para um AFN e para um AFD que reconheçam Ln, nos seguintes casos:

1. n = 1
2. n = 2
3. n é arbitrário

1. Mostre que para todo AFN existe um AFN equivalente com um único estado inicial (mostre como construir um AFN só com um estado inicial a partir de um AFN qualquer).

1. Mostre que sim ou não: para todo AFN existe um AFN equivalente com um único estado final

1. Seja o AFNλ M = ({0,1,2},{a,b,c},δ,0,{2}), sendo δ dado por:

δ	A	b	C	λ
0	{0}			{1}
1		{1}		{2}
2			{2}

1. Determine fλ(e) para e = 0,1,2.
2. Determine um AFN M´ equivalente a M, retirando as transições λ.
3. Determine um AFD M´´ equivalente a M´, retirando o não-determinismo.

1. Construa AFNE´s para as linguagens do exercício 1, com um mínimo de transições possível.

1. Mostre que para todo AFNλ existe um outro AFNλ equivalente com um único estado inicial e um único estado final.

...