Resolução de exercícios de Teoria da Computação

...

- aab

baab

bba

bbba

baabab

- a

b

aa

aaa

bab

- Construa autômatos finitos determinísticos (diagrama de estados) que aceitem cada uma das seguintes linguagens:

- [pic 14]

- [pic 15]

- [pic 16]

- [pic 17]

Respostas:

[pic 18][pic 19][pic 20]

[pic 21]

[pic 22][pic 23][pic 24]

[pic 25]

[pic 26][pic 27][pic 28]

[pic 29]

---------------------------------------------------------------

[pic 30][pic 31][pic 32]

[pic 33]

- Dado o alfabeto Σ*= {a,b}, construa AFDs para as seguintes linguagens:

- [pic 34]

[pic 35]

- [pic 36]

[pic 37]

- [pic 38]

[pic 39]

- [pic 40]

[pic 41]

- Descreva um AFD capaz de reconhecer somente datas válidas (não levando em consideração anos bissextos) no formato americano mês/dia, onde mês e dia são representados com dois dígitos.

[pic 42]

---------------------------------------------------------------

- Construa o respectivo autômato finito que reconhece as sentenças das linguagens abaixo sobre o alfabeto Σ= {0,1}.

- [pic 43]

[pic 44]

- [pic 45]

[pic 46]

- Qual a diferença do AFND e o AFD?

A diferença entre um autômato finito determinístico e um autômato finito não determinístico é que para uma palavra ser aceita no AFD ela tem que ser aceita por todos os caminhos. Já o AFND não, para uma palavra ser aceita em um AFND basta ela ser aceita em um dos caminhos. A palavra para ser rejeitada por um AFND a mesma tem q ser rejeitada por todos os caminhos. Na Rejeição do AFD basta a palavra ser rejeitada por um dos caminhos.

- Seja um autômato finito não determinístico que aceita a linguagem das cadeias de zero ou mais vezes de 0’s e 1’s e que terminam em 01, representado pela linguagem regular (0 + 1) * 01. Construa o grafo respectivo ao AFND e indique pelo menos três palavras válidas.

- Dada a expressão regular tenha dois 0’s consecutivos OU dois 1’s consecutivos }. Construa o autômato finito não determinístico para esta linguagem regular.[pic 47]