_Máquina de Turing

breadcrumb-separator

ESTÁCIO

em 18/11/2024

Conteúdos escolhidos para você

Importância dos Símbolos na Comunicação

Importância dos Símbolos na Comunicação

UNICSUL

exercício estacio

exercício estacio

Símbolos Religiosos e Significados

Símbolos Religiosos e Significados

UNICSUL

Criação de Símbolos para Soluções

Criação de Símbolos para Soluções

O sistema BRAILLE - EXERCÍCIO

O sistema BRAILLE - EXERCÍCIO

ESTÁCIO

Perguntas dessa disciplina

Como podemos definir o conceito de língua do ponto de vista da linguística? A Um órgão do corpo que nos proporciona a fala. B Um conjunto de símbol...

Conforme visto nas aulas e rotas desta disciplina, quanto ao processo de aprendizagem da leitura, relacione corretamente cada um dos cinco conheciment

UNOPAR

O Sistema Braille utiliza 6 pontos em relevo dispostos em duas colunas, possibilitando a formação de _______________ diferentes, usados em textos l...

A escrita pode ter surgido num contexto em que havia atividades com rebanhos e domesticação de animais, estando relacionada com a necessidade de re...

verifique a resposta correta, principalmente da banca UNIFATECIE . Informe a resposta e a letra correta. O sistema de numeração romana já foi o princi

UNIP

Material

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Conteúdos escolhidos para você

Importância dos Símbolos na Comunicação

Importância dos Símbolos na Comunicação

UNICSUL

exercício estacio

exercício estacio

Símbolos Religiosos e Significados

Símbolos Religiosos e Significados

UNICSUL

Criação de Símbolos para Soluções

Criação de Símbolos para Soluções

O sistema BRAILLE - EXERCÍCIO

O sistema BRAILLE - EXERCÍCIO

ESTÁCIO

Perguntas dessa disciplina

Como podemos definir o conceito de língua do ponto de vista da linguística? A Um órgão do corpo que nos proporciona a fala. B Um conjunto de símbol...

Conforme visto nas aulas e rotas desta disciplina, quanto ao processo de aprendizagem da leitura, relacione corretamente cada um dos cinco conheciment

UNOPAR

O Sistema Braille utiliza 6 pontos em relevo dispostos em duas colunas, possibilitando a formação de _______________ diferentes, usados em textos l...

A escrita pode ter surgido num contexto em que havia atividades com rebanhos e domesticação de animais, estando relacionada com a necessidade de re...

verifique a resposta correta, principalmente da banca UNIFATECIE . Informe a resposta e a letra correta. O sistema de numeração romana já foi o princi

UNIP

Prévia do material em texto

Máquina de Turing
1
2
 Mt =(Σ, Q , δ, q0, F, V, β )
Σ :Alfabeto de símbolos da cadeia de entrada ;
Q : Conjuto de estado;
δ : Função de transição;
q0 : Estado inicial ;
F : Conjunto de estados finais;
V : Conjunto de símbolos auxiliares ;
β : Símbolos de células em branco ;
3
11. L= {a b | i >= 1}(2i) i
 L = {aab , aaaabb , aaaaaabbb , .... }
4
δ(q0 , símbolo lido) → (q1 , símbolo escrito , direção)
11. L= {a b | i >= 1}(2i) i
 L = {aaaabb }
δ(q0 , a)→(q1 , X, D)
5
δ(q0 , símbolo lido) → (q1 , símbolo escrito , direção)
11. L= {a b | i >= 1}(2i) i
 L = {aaaabb }
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
δ(q0 , a)→(q1 , X, D)
a a a a b b β
6
aaaabb
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
a ; X
 , D
q0
q1
δ(q4 , β)→(q5 ,β, D)
X a a a b b β
7
aaaabb
a ; X
 , D
a ; X , D
q0
q1 q2
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X a a b b β
8
aaaabb
a ; X
 , D
a ; X , D
q0
q1 q2
a; a , D
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X a a b b β
9
aaaabb
a ; X
 , D
a ; X , D
q0
q1 q2
a; a , D
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X a a b b β
10
aaaabb
a ; X
 , D
a ; X , D b ; Y , E
q0
q1 q2
q3
a; a , D
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X a a Y b β
11
aaaabb
a ; X
 , D
a ; X , D b ; Y , E
q0
q1 q2
q3
a; a , D
a ; a ,E
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X a a Y b β
12
aaaabb
a ; X
 , D
a ; X , D b ; Y , E
q0
q1 q2
q3
a; a , D
a ; a ,E
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X a a Y b β
13
aaaabb
a ; X , D
a ; X , D b ; Y , E
X ; X , Dq0
q1 q2
q3
a; a , D
a ; a ,E
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X a a Y b β
14
aaaabb
a ; X , D
a ; X , D b ; Y , E
X ; ,X , Dq0
q1 q2
q3
a; a , D
a ; a ,E
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X X a Y b β
15
aaaabb
a ; X , D
a ; X , D b ; Y , E
X ; ,X , Dq0
q1 q2
q3
a; a , D
a ; a ,E
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X X X Y b β
16
aaaabb
a ; X , D
a ; X , D b ; Y , E
X ; ,X , Dq0
q1 q2
q3
a; a , D
Y ; Y , D
a ; a ,E
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X X X Y b β
17
aaaabb
a ; X , D
a ; X , D b ; Y , E
X ; ,X , Dq0
q1 q2
q3
a; a , D
Y ; Y , D
a ; a ,E
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X X X Y Y β
18
aaaabb
a ; X , D
a ; X , D b ; Y , E
X ; ,X , Dq0
q1 q2
q3
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X X X Y Y β
19
aaaabb
a ; X , D
a ; X , D b ; Y , E
X ; ,X , Dq0
q1 q2
q3
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X X X Y Y β
20
aaaabb
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
q0
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X X X Y Y β
21
aaaabb
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
q0
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
X X X X Y Y β
22
aaaabb
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 ,β, D)
δ a b X Y β
q0 (q1 , X, D)
q1
q2
q3
q4
q5
23
 (q2 , X, D)
(q2 , a, D) (q2 , Y, D) (q3 , Y, E) 
(q3 , a, E) (q3 , Y, E)
(q4 , Y, D)
(q4 , Y, D) (q5 ,β, D)
(q0 , X, D)
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , DTabela
Obrigado!
24
a a b β
25
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 , β, D)
aab
a a b β
26
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , β)→(q5 , β, D)
aab
27
δ(q0 ,a,)→(q1 , X, D)
δ(q1 ,a,)→(q2 , X, D)
δ(q2 ,a,)→(q2 , a, D) 
δ(q2 ,Y,)→(q2 , Y, D) 
δ(q2 ,b)→(q3 , Y, E) 
δ(q3 ,a,)→(q3 , a, E)
δ(q3 ,Y,)→(q3 , Y, E)
δ(q3 ,X,)→(q0 , X, D)
δ(q0 ,Y,)→(q4, Y, D)
δ(q4 ,Y,)→(q4 , Y, D)
δ(q4 ,#,)→(q5 , #, D)
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , #)→(q5 , #, D)
28
δ(q0 , a)→(q1 , X, D)
δ(q1 , a)→(q2 , X, D)
δ(q2 , a)→(q2 , a, D)
δ(q2 , Y)→(q2 , Y, D) 
δ(q2 , b)→(q3 , Y, E) 
δ(q3 , a)→(q3 , a, E)
δ(q3 , Y)→(q3 , Y, E)
δ(q3 , X)→(q0 , X, D)
δ(q0 , Y)→(q4 , Y, D)
δ(q4 , Y)→(q4 , Y, D)
δ(q4 , #)→(q5 , #, D)
29
δ(q0 ,a,)→(q1 , X, D)
δ(q1 ,a,)→(q2 , X, D)
δ(q2 ,a,)→(q2 , a, D) 
δ(q2 ,Y,)→(q2 , Y, D) 
δ(q2 ,b)→(q3 , Y, E) 
δ(q3 ,a,)→(q3 , a, E)
δ(q3 ,Y,)→(q3 , Y, E)
δ(q3 ,X,)→(q0 , X, D)
δ(q0 ,Y,)→(q4 , Y, D)
δ(q4 ,Y,)→(q4 , Y, D)
δ(q4 ,#,)→(q5 , #, D)
δ a b X Y β
q0 (q1 , X, D)
q1
q2
q3
q4
q5
30
 (q2 , X, D)
(q2 , a, D) (q2 , Y, D) (q3 , Y, E) 
(q3 , a, E) (q3 , Y, E)
(q4 , Y, D)
(q4 , Y, D) (q5 ,β, D)
(q0 , X, D)
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , DTabela
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
31
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
32
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
33
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
34
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
35
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
36
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
37
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
38
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
39
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
40
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
41
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D
a ; X , D
a ; X , D b ; Y , E
X ; ,X , D
Y ; Y , D
 β ; β, D
42
q0
q5
q1 q2
q3
q4
a; a , D
Y ; Y , D
Y ; Y ,E
a ; a ,E
Y ; Y , D