Trabalho de linguagens formais e autômatos

CENTRO UNIVERSITÁRIO DE FORMIGA – UNIFOR-MG
CIÊNCIA DA COMPUTAÇÃO - 6º PERÍODO

TRABALHO DE LINGUAGENS FORMAIS E AUTÔMATOS

FORMIGA-MG
2012
MÁRIO ARAÚJO RIBEIRO NETO
STEFANIA MACIENTE

LINGUAGENS FORMAIS E AUTÔMATOS

Trabalho elaborado para a disciplina de Linguagens Formais e Autômatos ao professor Alexandre Magno de Sousa da turma de Ciência da Computação, 6º período.

FORMIGA-MG
2012
Sumário I. Questões da página 62 do livro 3 1. Faça um diagrama de estados, similar àquele da Figura 2.1, página 58, para o problema dos missionários e canibais: 3 2. Faça um diagrama de estados, usando a ideia apresentada na Seção 2.1.2, para uma máquina que determine se uma sequência ternária (com dígitos 0,1 e 2) é divisível por 4. 4 II. Questões da página 81 do livro 5 1. Construa AFD’s para as seguintes linguagens sobre o alfabeto {0, 1}: 5 A. O conjunto das palavras de tamanho 3. 5 B. O conjunto das palavras de tamanho menor do que 3. 5 C. O conjunto das palavras de tamanho maior do que 3. 5 D. O conjunto das palavras de tamanho múltiplo de 3. 5 E. O conjunto das palavras com no máximo três 1’s. 5 F. O conjunto das palavras que contêm um ou dois 1’s, cujo tamanho é múltiplo de 3. 6 2. Construa AFD’s para as seguintes linguagens: 6 A. {λ, 0}2 6 B. {ω ϵ{0, 1}* | cada 0 de ω é imediatamente seguido de, no mínimo, dois 1’s}. 6 C. {ω ϵ{0, 1}* | os primeiros 4 símbolos de ω contêm, no mínimo, dois 1’s}. 6 D. {ω ϵ{0, 1}* | ω não contém 000 nem 111}. 7 E. { ω ϵ{0, 1}* | os últimos 3 símbolos de ω não são 000}. 7 F. {ω ϵ{0, 1, 2}* | ω tem número par de 0’s, par de 1’s e par de 2’s}. 8 BIBLIOGRAFIA 9

I. Questões da página 62 do livro

1. Faça um diagrama de estados, similar àquele da Figura 2.1, página 58, para o problema dos missionários e canibais:

Três missionários e três canibais devem atravessar um rio. Para isto dispõem de uma canoa que pode transportar no máximo 2 pessoas de cada vez. Durante a