Prova de Teoria da Computação - UFAL

Prévia do material em texto

Universidade Federal de Alagoas - UFAL 
Instituto de Computação - IC 
Programa de Pós-graduação em Informática - PPGI 
Teoria da Computação 
Primeira Prova – 20/07/2020 
Professor: Leandro Dias da Silva 
Aluno: 
 
Observações: A prova tem duração máxima de quatro horas. A submissão deve ser no 
sistema, em arquivo único. A prova é ​SEM CONSULTA! O JFLAP pode ser utilizado para 
testes, mas no arquivo da prova deve constar o passo a passo das questões. 
 
1. Que tipo de autômato é ilustrado na Figura 1? Que linguagem ele reconhece? 
Mostre a definição formal. Mostre a computação da palavra w=011. A palavra 
é aceita? 
2. Construa o autômato finito não determinístico equivalente ao da Figura 1. 
3. Construa o autômato finito, com alfabeto {a, b}, que reconheça a linguagem 
em que qualquer ocorrência de a é imediatamente sucedida por b. 
4. Descreva a linguagem gerada pelas seguintes expressões regulares: 
a) (a+bc)*; b) a*(c+ε); c) a(b+c)*; d) (a+ε)(b+c)* 
e) Construa o autômato para a expressão do item a). 
5. Defina a gramática G que gera a linguagem L = {w | w é palavra de a(ab)*}. 
Apenas um tipo. Mostre os passos da derivação para palavra w=aabab. 
 
Figura 1 
 
 
Boa Prova!