Nada d+

Universidade Federal de Uberlândia
1a Lista de Exercícios de Linguagens Formais e Autômatos
2o Semestre de 2014 - Profa. Gina Maira B. de Oliveira
Data de entrega: 18/11/2014

1) Sejam as gramáticas G1 e G2 conforme definidas abaixo:
(Entregar 1 dos 2 exercícios abaixo à escolha do aluno)

G1 = ({S,A,B,C,E,F}, {0,1,2},{S012|0BAC, B0B1A|01A, ACC2,1C2F12, AFFA, FA1F1E, E222, 1F1F11, 1E111E, 0F1011},S)
G2 = ({S, B,C}, {0,1},{SB, B0B|1C|, C0C|1B},S)

A. Qual é o tipo (0, 1, 2 ou 3) de cada gramática? Justifique.
B. Faça a derivação de 3 palavras diferentes em cada gramática.
C. Qual é a linguagem gerada em cada caso?

2) Qual é a linguagem gerada para cada uma das gramáticas definidas abaixo:
(Entregar 2 dos 3 exercícios abaixo à escolha do aluno)

A. G1 = ({S, A, B, C, D, E}, {0}, P1, S), P1= {SAC0B, C0000C, CBDB, CBE, 0DD0, ADAC, 0EE0, AE}

B. G2 = ({E,T,F}, {+,*, id}, P2, E), P2 = {E  E + T, E  T, T  T * id, T  id} C. G3 = ({E,O}, {+,*, id}, P3, E), P3 = {E  EOE , E  id, O  +, O  *}

3) Seja o Problema dos Missionários e Canibais, assim definido: “Três canibais e três missionários se encontram à margem direita de um rio. Todos precisam cruzar esse rio, e para isso dispõem de um barco onde cabem somente duas pessoas de cada vez. Os missionários precisam tomar cuidado ao fazer a travessia porque, se em qualquer instante houver mais canibais do que missionários em alguma das margens (havendo missionários naquela margem), os canibais "degustarão" alegremente os missionários. Considerando estas restrições, como fazer com que todas as pessoas cruzem o rio e cheguem ao outro lado sãs e salvas?” .
(Entregar esse exercício)
a) Modele esse problema através de um Autômato Finito, sendo que as transições (alfabeto) representam as possíveis travessias de uma margem a outra e os estados as situações válidas (inicial, final e intermediárias) possíveis de ocorrer dependendo da