Automatos

2 - Autômato com Pilha tem um grande poder computacional visto que ele tem uma pilha que lhe oferece características além de um AFD e AFND porque com a pilha o autómato consegue saber quantas vezes um determinado variável já foi lido possibilitando reconhecer linguagem como anbn .

3- A palavra ab não é reconhecida pelo autómato porque a configuração para a cadeia é:
(q0,, ab, $) (q1, ABC) depois o autómato não lê nada
(q1, e, A)(q0,$BC )
(q0, b)() o autómato fica bloqueado e a cadeia não será aceite porque a não se encontra vazia

4)
a) (q0,, 0|1, e) (q0, X) |- (q0, 1, X)(q1, e) a cadeia não é aceite porque apesar de a cadeia é completamente lida mas o autómato não está num estado final e a pilha não esta fazia.

b) (q0,, 0|01, e) (q0, X) |- (q0, 0|1, e)(q0, XX) |- (q0, 1, X)(q1, X) a cadeia não é aceite porque o autómato não está num estado final e a pilha não esta fazia.

c) (q0,, 0|00111, e) (q0, X) |- (q0, 0|0111, e)(q0, XX) |- (q0, 0|111, e)(q0, XXX) |- (q1, 1|11, e)(q1, XX) |- (q1, 1|1, e)(q1, X) |- (q1, 1, e)(q1, e) a cadeia é aceite por pilha vazia

d) (q0,, 0|10, e) (q0, X) |- (q0, 1|0, X)(q1, e) |- (q1, 0, ) a cadeia não é aceite porque o autómato não consegue ler toda a cadeia.

5)
A) ) (S, a|aabb, B) (S, A) |- (S, a|abb, A) (S, AA) |- (S, a|bb, A) (S, AAA) |- (S, b|b, A) (S, AA)
|- (S, b, A) (S, A) a cadeia não é aceite porque apesar de a cadeia é completamente lida mas o autómato não está num estado final e a pilha não esta fazia.

b) (S, a|abbb, B) (S, A) |- (S, a|bbb, A) (S, AA) |- (S, b|bb, A) (S, A) |- (S, b|b, A) (S, e) a cadeia não é aceite porque o autómato não consegue ler toda a cadeia.

c) (S, a|abb, B) (S, A) |- (S, a|bb, A) (S, AA) |- (S, b|b, A) (S, A) |- (S, b, A) (S, e) ) a cadeia é aceite por pilha vazia

d) (S, b|baa, B) (S, e) |- (S, b|aa, ) a cadeia não é aceite porque o autómato não consegue ler toda a cadeia.

6 – consideremos o símbolo inicial da pilha “#”
7)considerando o “e” como