AEC 6 AP E MT 2014 GABARITO

ATIVIDADE EXTRA-CLASSE – LFA

ATIVIDADE EXTRA-CLASSE
6 – Autômato de Pilha e Máquina de Turing
GABARITO
1-) Dado o APD abaixo:
(0,,0)

q1

($,,$)

(1,0,)

q2

(0,,)

q3

($,$,)

q4

Verifique se o mesmo reconhece as palavras a seguir. a-) w = $001$
R: É reconhecida.
Símbolo Lido



$
0
0
1
$

Símbolo Não-Lido
$001$
001$
01$
1$
$



b-) w = $0011$
R: Não é reconhecida.
Símbolo Lido
Símbolo Não-Lido
$0011$

$
0011$
0
011$
0
11$
1
1$
1
$

Prof. Clayton A. Valdo, M.Sc.

Estado Atual q2 q2 q3 q3 q4 $
$0
$0
$



Estado Atual q2 q2 q3 q3
-



Pilha



Pilha

$
$0
$0
$
$

1

ATIVIDADE EXTRA-CLASSE – LFA

c-) w = $000111$
R: Não é reconhecida.
Símbolo Lido
Símbolo Não-Lido
$000111$

$
000111$
0
00111$
0
0111$
0
111$
1
11$
1
1$
1
$ d-) w = $00011$
R: É reconhecida.
Símbolo Lido



$
0
0
0
1
1
$

Símbolo Não-Lido
$00011$
00011$
0011$
011$
11$
1$
$



e-) w = $01$
R: Não é reconhecida.
Símbolo Lido
Símbolo Não-Lido
$01$

$
01$
0
1$
1
$ f-) w = $00011$
R: É reconhecida.
Símbolo Lido



$
0
0
0
1
1
$

Símbolo Não-Lido
$00011$
00011$
0011$
011$
11$
1$
$



Prof. Clayton A. Valdo, M.Sc.

Estado Atual



q2 q2 q2 q3 q3 q3 -

$
$0
$00
$00
$0
$
$

Estado Atual q2 q2 q2 q3 q3 q3 q4 

Pilha

$
$0
$00
$00
$0
$



Estado Atual q2 q3
-



Pilha

$
$
$

Estado Atual q2 q2 q2 q3 q3 q3 q4 Pilha



Pilha

$
$0
$00
$00
$0
$



2

ATIVIDADE EXTRA-CLASSE – LFA

g-) w = $0001$
R: Não é reconhecida.
Símbolo Lido
Símbolo Não-Lido
$0001$

$
0001$
0
001$
0
01$
0
1$
1
$
$


Estado Atual

Pilha



q2 q2 q2 q3 q3
-

$
$0
$00
$00
$0
$0

2-) Dado o APND abaixo:
(0,,0)

q1

($,,$)

(1,0,)

q2

(,,)

q3

($,$,)

q4

Verifique se este APND reconhece as mesmas palavras do exercício anterior. a-) w = $001$
R: Não é reconhecida.
Símbolo Lido
Símbolo Não-Lido
Estado Atual
Pilha
$001$


$
001$ q2 $
0
01$ q2 $0
0
1$ q2 $00
1$
q3
$00

1
$ q3 $0
$
q3
$
 b-) w = $0011$
R: É reconhecida.
Símbolo Lido



$
0
0



1
1
$

Símbolo Não-Lido
$0011$
0011$
011$
11$
11$
1$
$

