Atividade Compiladores

CURSO: SISTEMAS DE INFORMAÇÃO - EAD
DISCIPLINA: Linguagens Formais e Compiladores
SEMESTRE: 2013.1
PROFESSOR: Marcos Pacheco

Avaliação 1 – Parte 1
VALOR TOTAL: 6,0 (seis) PONTOS (0,6 cada)

BAREMA DE CORREÇÃO
Obs: As respostas dos alunos podem estar escritas de outra forma desde que atenda a idéia central da proposta de resposta para a questão.
QUESTÃO 01) Após seu estudo e entendimento sobre a Aula 01 explique, com suas próprias palavras, o que você entende por:
a) ALFABETO ∑
b) FECHAMENTO REFLEXIVO DE UM ALFABETO ∑*
+
c) FECHAMENTO TRANSITIVO DE UM ALFABETO ∑
d) PALAVRA
Os conceitos dos itens a) a d) estão presentes na aula 01. Basta comparar e ver se o aluno compreendeu estes conceitos. Deve ser utilizada as próprias palavras do aluno. É claro que podem haver conceitos na resposta mas a resposta deverá ser percebida como de caráter pessoal

QUESTÃO 02) Dado o AUTÔMATO a seguir responda:

a) Este autômato é determinístico ou não determinístico? Por quê?
Um autômato finito determinístico (AFD, ou DFA em inglês) é um autômato que se encontra sempre em um único estado após ler uma sequencia qualquer de entrada. O termo “determinístico” implica que existe um e somente um estado ao qual o autômato pode transitar a partir de seu estado atual.

Diferentemente dos AFDs (autômatos finitos determinísticos) os autômatos finitos não-determinísticos podem estar em vários estados ao mesmo tempo.
Neste caso o autômato é determinístico, pois se encontra sempre em um único estado após ler uma sequencia qualquer de entrada. Apesar de q2 ter duas possibilidades ao ler 1 ou 0 fica no mesmo estado
b) As palavras 111101, 110111, 10001, 01, 101010, são reconhecidas por este autômato? Mostre o passo a passo e indique sua resposta.
Neste caso mostrar o passo a passo para cada palavra. Parecido com o passo a passo da aula 2:
Inicia no estado q1
Segue a transição de q1 para q2 (Le 1)
Segue a transição de q2 para q2 (Le 1 novamente)
Segue a