• Disciplina: Teoria da Computação
• Período: 2019.1

Aviso!

As questões apresentadas a seguir são descrições baseadas em relatos de um ou mais alunos que fizeram tal avaliação. Logo, não há garantia de que os enunciados sejam iguais aos originais, tampouco que estejam livres de erros. Esteja ciente dessas considerações ao utilizar esse material!

Questões

Questão 1

Construa dois autômatos, A1 e A2, tal que Σ = {0,1} e em que L(A1) = {w E Σ\ | w tem comprimento múltiplo de 3}* e L(A2) = {w E Σ\ | w é um número binário divisível por 5}*.

Questão 2

Prove que, dados dois autômatos finitos (A1 e A2) com o mesmo alfabeto, a operação de subtração (A1 - A2) resulta em um autômato finito.

• Observação: Foi permitido provar formalmente ou realizar a subtração dos autômatos da questão anterior.

Questão 3

Demonstre a execução do autômato não-determinístico a seguir para as seguintes entradas 01011, 1110 e 000. Destaque se essas entradas são ou não aceitas por ele.

• Observação: Não foi possível reproduzir o autômato.

Questão 4

Bônus: Dados dois autômatos finitos (A1 e A2), prove que sua intersecção ainda resulta em um autômato finito mesmo que, no alfabeto de um deles, existe um símbolo que não está contido no alfabeto do outro.