! 
Turing
2
! 
! 
! 
! 
! 
" 
" 
" 
3
$ 1 0 1 1 0 0 0 0 0 B B B B B B
q0
q1
$ 1 0 1 1 0 0 0 0 0 B B B B B B
$ 1 0 1 1 0 0 0 0 0 B B B B B B
B
δ(q1,0)=(q2,x,R)
!
• 
• 
• 
q2
x
q2
B
$ 1 x 1 1 0 0 0 0 0 B B B B B B
! 
Turing
(q, b, D)
Turing
Q, Σ, Γ
3
(D=L
D=R)
! 
q
b
! 
! 
3
! 
! 
(Q, Σ, Γ, δ, q0, qaccept, qreject)
! 
Q
! 
Σ
B, $
! 
Γ
Σ
! 
δ: Q’ × Γ → Q’ × Γ × {L, R}
{B, $} Γ
Q’ = Q−{qaccept , qreject }
(q, b, D)
p
7
a
(p, a)
! 
q0 Q
! 
qaccept
Q
! 
qreject
Q
qreject ≠ qaccept
δ: Q’ × Γ → Q’ × Γ × {L, R}
! 
Turing
M
q Q
δ(p, a) = (q, b, D)
δ
δ(p, a) = (q, b, D)
# 
a=$!
!b=$
# 
a=$!
!D=R
! 
q
a
! 
! 
D
b
{L, R}
! 
Turing
w=w1w2…wn
M=(Q, Σ, Γ, δ, q0, qaccept, qreject)
" 
q0
0
n+1
" 
$
i =1,…,n
qaccept
i
wi
B
1
" 
q0
$ 1 0 1 1 0 0 0 0 0 B B B B B B
B
Turing
qreject
δ
a
M
Γ
" 
" 
" 
Turing
C0C1…Ck
C0
w
M
Ci
Ck
w
M
w
" 
Ci+1
" 
Turing
M
M
w L
M
w
w L
M
w
L
Turing
L
w
Turing
L
L={ w | |w|a=|w|b }
Turing
!
" 
" 
" 
" 
" 
Turing
M
M
w L
M
w
w L
M
w
L
Turing
L
Turing
L
w
L
Turing
L
Turing
! 
Turing
! 
δ(p, a)=(q, b, D)
B,$→R
q2
x→R
p
! 
a→b, D
p
b→x,R
a→x,R
q
qaccept
δ(p, a)=(q, a, D)
a→D
a,x→R
B→L
→R
q1
q4
$→R
b→x,R
q
B, $→R
a→x,R
q3
b,x→R
! 
L={ anbn | n≥0 }
a,b,x,B→L
Turing
! 
L={ w#w | w
{0,1}* }
qreject
Turing
x→R
0,1→R
x,$,B→R
! 
1,#,$,B→R
0,1→R
0,1→R
q6
0,1,x,#→L
0→x,L
q1
→R
q2
B→L
q9
q4
1→x,R
→R
q8
#→R
$, B→R
q7
B→R
qaccept
0,1,#,$→R
x,$,B→R
0,#,$,B→R
x→R
! 
x→R
x→R
0→x,R
1→x,L
B,x,$→R
,x,$→R
q5
→R
q3
B→R
→R
L={ 0n | m ≥ 0
Turing
0,1→R
n=2m}
qreject
L={ wwR | w
{0,1}* }
Turing

Languages and Finite Automata

3. クラス P 定義3.1 クラスP

Horaire EPC 2014 - 2015 CB1

N Bar Emulation EXT Rito 3X25 of 5H11 EXT AAA #+11967377 [AMF]

Languages and Finite Automata