Prévia do material em texto

FUNDAMENTOS TEÓRICOS DA COMPUTAÇÃO 
AUTÔMATOS FINITOS DETERMINÍSTICOS 
 
Exercício Individual 
Gere diagrama de estado de AFD completo (todos os estados têm que ter transições 
para todos os símbolos do alfabeto) para cada uma das linguagens descritas abaixo. Em 
todas as questões o alfabeto Σ = {0,1}. Use a ferramenta JFLAP. 
Sugestão: faça testes com diversas cadeias (opção Input – Multiple Run), incluindo 
cadeias aceitas e cadeias rejeitadas. 
Entregue somente os arquivos “jff”. 
Dê o nome dos arquivos exatamente iguais à questão. Por exemplo, “1.jff”, “2.jff”, etc. 
Comprima todos os arquivos no formato “zip” e submeta no Colabweb. O nome do 
arquivo zipado deve ser exatamente o nome do aluno. 
Se não seguir qualquer recomendação acima já perderá 1.0 (um) ponto. 
1) {𝜔 ∶ 	𝜔 inicia com 0 e termina com 1} 
2) {𝜔 ∶ 	𝜔 inicia com 0 e tem comprimento ímpar} 
3) {𝜔 ∶ 	𝜔 contém pelo menos quatro 1s} 
4) {𝜔 ∶ 	𝜔 contém a subcadeia 101} 
5) {𝜔 ∶ 	𝜔 contém um número par de 0s} 
6) {𝜔 ∶ 	𝜔 contém todas as cadeias possíveis, exceto a cadeia vazia} 
7) {𝜔 ∶ 	𝜔 contém todas as cadeias possíveis, exceto a subcadeia 000} 
8) {𝜔 ∶ 	𝜔 contém todas as cadeias possíveis, exceto as subcadeias11 e 00} 
9) {𝜔 ∶ 	𝜔 contém pelo menos dois 0s e no máximo dois 1’s} 
10) {𝜔 ∶ 	𝜔 contém o conjunto das palavras cujo penúltimo símbolo é 1} 
11) {𝜔 ∶ 	𝜔 contém o conjunto das palavras cujo antepenúltimo símbolo é 0} 
12) {𝜔 ∶ 	𝜔 tem comprimento igual a quatro} 
13) {𝜔 ∶ 	𝜔 tem comprimento menor que cinco} 
14) {𝜔 ∶ 	𝜔 tem comprimento par e um número ímpar de 0s} 
15) {𝜔 ∶ 	𝜔 tem comprimento ímpar e um número par de 0s} 
16) {𝜔 ∶ 	𝜔 ou é a cadeia vazia (𝜀) ou é um 0, e nada mais que isso} 
17) {𝜔 ∶ |𝜔| ≥ 1, inicia com 0 e tem comprimento ímpar} 
18) {𝜔 ∶ |𝜔| ≥ 2 e contém somente dois 1s} 
19) {𝜔 ∶ |𝜔| ≥ 3 e o terceiro símbolo em 𝜔 é um 0} 
20) {𝜔 ∶ |𝜔| ≥ 0 e toda posição ímpar de 𝜔 é 1} 
Todas as questões valem 0,5 pontos. 
Será considerado somente se o autômato resolve o problema, ou seja, não será 
considerado se o autômato é otimizado / minimizado.