A Teoria da Computação

Exercício 01

a) O autômato apresentado é sim determinístico. Para cada símbolo de entrada e estado de partida, possuí transição para apenas um outro estado. E possui transição para todos os casos. Logo, como não há “ambiguidade” nas transições, nem faltam transições, podemos defini-lo como determinístico.

b) Considerando a cadeia “abb” teremos:

➢ δ^(q0, a) = δ(δ^(q0, ε), a) = δ(q0, a) = q1

➢ δ^(q1, ab) = δ(δ^(q0, a), b) = δ(q1, b) = q1

➢ δ^(q1, abb) = δ(δ^(q0, ab), b) = δ(q1, b) = q1

Parou no estado “q1”, estado não-final.

c)

Exercício 02

Conjunto de estados: {q0, q1, q2, q3}

Alfabeto: {a, b}

Estado inicial: q0

Estado final: q3

Tabela de transições:

δ a b

->q0 {q1} {q2}

q1 {q1, q3} {q1}

q2 {q2} {q2, q3}

*q3 ∅ ∅

Exercício 03

Utilizando o lema do bombeamento conseguimos provar que essa linguagem não é regular. Supondo que L seja regular, existe uma largura Q de bombeamento, tal que todas as cadeias com tamanho maior que Q, podem ser bombeadas. Pegando uma cadeia maior que Q, dividindo-a em três partes (a, b, c), iremos provar em ‘b’ utilizando os seguintes cenários: ‘b’ possuindo 0 e 1, possuindo apenas 0 e possuindo apenas 1. Em todos eles, multiplicando ‘b’ por um valor maior que 1, as quantidades de 0 e 1 serão diferentes, logo ela não é regular.

Exercício 04

Não tem como esse AP ser determinístico. Para que isso ocorra é preciso adicionar um símbolo ao fim das palavras: #.

Teremos então:

Estados: {q0, q1, q2, q3}

Alfabeto: {a, b}

Alfabeto da pilha: {a, b, $, #}

Estado inicial: q0

Estado inicial da pilha: Z

Conjunto de estados finais: {q2}

Funções:

δ(q0, a, $) = {(q0, a$)}

δ(q0, a, a) = {(q0, aa)}

δ(q0, b, ε) = {(q1, ε)}

δ(q1, b, a) = {(q1, ε)}

δ(q1, b, $) = {(q3, $)}

δ(q1, a, a) = {(q3, ε)}

δ(q1, #, $) = {(q2, $)}

δ(q1, #, a) = {(q2, ε)}

δ(q2, ε, a) = {(q2, ε)}

δ(q3, a, a) = {(q3, ε)}

δ(q3, a, $) =