Automatos [teoria da computação]

TEORIA DA COMPUTAÇÂO – Tarefa 2

Para cada uma das seguintes linguagens regulares definidas sobre o alfabeto Σ, defina um autômato finito determinístico, um não determinístico e um não-determinístico com transições em vazio que reconhecem a linguagem.

Σ = {1,0,a,b,c,d}

⦁ (a|b|c)|d*

Autômato finito deterministico:

Não deterministico:

Com transição em vazio:

⦁ 1 1* 0* 1 1*

Autômato finito deterministico:

Não deterministico:

Com transição em vazio:

⦁ L = {w | w tem ao mesmo tempo um número par de 0's e un número par de 1's}

Autômato finito deterministico:

Não deterministico:

⦁ a* a  b b *  c*  d*

Autômato finito deterministico:

Não deterministico:

Com transição em vazio:

⦁ L = {w | w tem uma quantidade de a igual ao dobro de b}

Não é regular.

⦁ (a|b*)c d d*

Autômato finito deterministico:

Com transição em vazio:

Para cada uma das seguintes linguagens regulares definidas sobre o alfabeto Σ, defina um autômato finito determinístico, um não determinístico e um não-determinístico com transições em vazio que reconhecem a linguagem.

Σ = {1,0,a,b,c,d}

⦁ (a|b|c)|d*

Autômato finito deterministico:

Não deterministico:

Com transição em vazio:

⦁ 1 1* 0* 1 1*

Autômato finito deterministico:

Não deterministico:

Com transição em vazio:

⦁ L = {w | w tem ao mesmo tempo um número par de 0's e un número par de 1's}

Autômato finito deterministico:

Não deterministico:

⦁ a* a  b b *  c*  d*

Autômato finito deterministico:

Não deterministico:

Com transição em vazio: