Atps Linguagens Formais E Automatos

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 travessia, se o número de canibais ficar maior do que o de missionários em qualquer uma das margens, os canibais comem os missionários. Determinar um plano para travessia em que nenhum missionário seja devorado.