期末-計算理論5.2圖靈機

機機的設計技術機的變形算法的定義-?

(

?

K2013

年5月2

日吳鋌-?(?K杭州電子科技大學計算機學院機機的設計技術機的變形算法的定義??

-論題1機吳鋌-?(?K杭州電子科技大學計算機學院機機的設計技術機的變形算法的定義??

-論題1機2機的設計技術吳鋌-?(?K杭州電子科技大學計算機學院機機的設計技術機的變形算法的定義??

-論題1機2機的設計技術3機的變形吳鋌-?(?K杭州電子科技大學計算機學院機機的設計技術機的變形算法的定義??

-論題1機2機的設計技術3機的變形4

算法的定義吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機：與有?

自

相比，?有?

限大的

(帶子)

?

可以任意訪?

數(shù)據(jù)；吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機：與有?

自

相比，?有?

限大的

(帶子)

?

可以任意訪?

數(shù)據(jù)；能夠模擬實際計算機的所有計算行?；吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機：與有?

自

相比，?有?

限大的

(帶子)

?

可以任意訪?

數(shù)據(jù)；能夠模擬實際計算機的所有計算行?；存在

機?

法解決的?

題；吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機：與有?

自

相比，?有?

限大的

(帶子)

?

可以任意訪?

數(shù)據(jù)；能夠模擬實際計算機的所有計算行?；存在

機?

法解決的?

題；有?

自

與

機的?

別：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機：與有?

自

相比，?有?

限大的

(帶子)

?

可以任意訪?

數(shù)據(jù)；能夠模擬實際計算機的所有計算行?；存在

機?

法解決的?

題；有?

自

與

機的?

別：機在帶子上既能讀也能寫；吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機：與有?

自

相比，?有?

限大的

(帶子)

?

可以任意訪?

數(shù)據(jù)；能夠模擬實際計算機的所有計算行?；存在

機?

法解決的?

題；有?

自

與

機的?

別：機在帶子上既能讀也能寫；機的讀寫頭能向左、右移動；吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機：與有?

自

相比，?有?

限大的

(帶子)

?

可以任意訪?

數(shù)據(jù)；能夠模擬實際計算機的所有計算行?；存在

機?

法解決的?

題；有?

自

與

機的?

別：機在帶子上既能讀也能寫；機的讀寫頭能向左、右移動；機的帶子?限長；吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機：與有?

自

相比，?有?

限大的

(帶子)

?

可以任意訪?

數(shù)據(jù)；能夠模擬實際計算機的所有計算行?；存在

機?

法解決的?

題；有?

自

與

機的?

別：機在帶子上既能讀也能寫；機的讀寫頭能向左、右移動；機的帶子?限長；機進入

或接受狀態(tài)則立即停機，否則永不停止；吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義??

1

(

?(?

(

Q,

P

,

Γ,

δ,q0,

qaccept,

qreject))吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義??

1

(

?(?

(

Q,

P

,

Γ,

δ,q0,

qaccept,

qreject))Q

?

G

8

?吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義??

1

(

?(?

(

Q,

P

,

Γ,

δ,q0,

qaccept,

qreject))Q

?

G

8

?P

?

?

\

i

1

L

?

?

A

?

?

白??

6∈P

?吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義??

1

(

?(?

(

Q,

P

,

Γ,

δ,q0,

qaccept,

qreject))Q

?

G

8

?P

?

?

\

i

1

L

?

?

A

?

?

白??

6∈P

?Γ

??

i

1

L

?

??

∈

Γ,

P

?

Γ

?吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義??

1

(

?(?

(

Q,

P

,

Γ,

δ,q0,

qaccept,

qreject))Q

?

G

8

?P

?

?

\

i

1

L

?

?

A

?

?

白??

6∈P

?Γ

??

i

1

L

?

??

∈

Γ,

P

?

Γ

?δ

:Q

×?！鶴

×Γ

×{L,R}為=????~X

δ

(

q,

a)

=

(r,

b,L

)

L

?吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義??

1

(

?(?

(

Q,

P

,

Γ,

δ,q0,

qaccept,

qreject))Q

?

G

8

?P

?

?

\

i

1

L

?

?

A

?

?

白??

6∈P

?Γ

??

i

1

L

?

??

∈

Γ,

P

?

Γ

?δ

:Q

×Γ→Q

×Γ

×{L,R}為=????~X

δ

(

q,

a)

=

(r,

b,L

)

L

?^

b

?

a

??

\

G

r

?吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義??

1

(

?(?

(

Q,

P

,

Γ,

δ,q0,

qaccept,

qreject))Q

?

G

8

?P

?

?

\

i

1

L

?

?

A

?

?

白??

6∈P

?Γ

??

i

1

L

?

??

∈

Γ,

P

?

Γ

?δ

:Q

×Γ→Q

×Γ

×{L,R}為=????~X

δ

(

q,

a)

=

(r,

b,L

)

L

?^

b

?

a

??

\

G

r

?? ?

?

?

?吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義??

1

(

?(?

(

Q,

P

,

Γ,

δ,q0,

qaccept,

qreject))Q

?

G

8

?P

?

?

\

i

1

L

?

?

A

?

?

白??

6∈P

?Γ

??

i

1

L

?

??

∈

Γ,

P

?

Γ

?δ

:Q

×?！鶴

×Γ

×{L,R}為=????~X

δ

(

q,

a)

=

(r,

b,L

)

L

?^

b

?

a

??

\

G

r

?? ?

?

?

?q0,

qaccept,

qreject

∈

Q

?

O

L

???

!

?

!

?

?

G

??qaccept

6=

qreject?吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義機常用術語：格局/瞬時描述：產(chǎn)生：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義機常用術語：格局/瞬時描述：對于狀態(tài)q、Γ上的字符串u,v，uqv表示產(chǎn)生：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義機常用術語：格局/瞬時描述：對于狀態(tài)q、Γ上的字符串u,v，uqv表示當c

狀態(tài)?q，當c

帶內(nèi)容?uv；產(chǎn)生：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義機常用術語：格局/瞬時描述：對于狀態(tài)q、Γ上的字符串u,v，uqv表示當c

狀態(tài)?q，當c

帶內(nèi)容?uv；讀寫頭?于v的第一個符號，v最后符號后全?空x

符；產(chǎn)生：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義機常用術語：格局/瞬時描述：對于狀態(tài)q、Γ上的字符串u,v，uqv表示當c

狀態(tài)?q，當c

帶內(nèi)容?uv；讀寫頭?于v的第一個符號，v最后符號后全?空x

符；產(chǎn)生：對于格局uaqibv，若吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義機常用術語：格局/瞬時描述：對于狀態(tài)q、Γ上的字符串u,v，uqv表示當c

狀態(tài)?q，當c

帶內(nèi)容?uv；讀寫頭?于v的第一個符號，v最后符號后全?空x

符；產(chǎn)生：對于格局uaqibv，若δ(qi,b)=(qj,c,L)，則δ(qi,b)=(qj,c,R)，則吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義機常用術語：格局/瞬時描述：對于狀態(tài)q、Γ上的字符串u,v，uqv表示當c

狀態(tài)?q，當c

帶內(nèi)容?uv；讀寫頭?于v的第一個符號，v最后符號后全?空x

符；產(chǎn)生：對于格局uaqibv，若δ(qi,b)=(qj,c,L)，則格局uaqibv產(chǎn)生δ(qi,b)=(qj,c,R)，則格局uaqibv產(chǎn)生吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義機常用術語：格局/瞬時描述：對于狀態(tài)q、Γ上的字符串u,v，uqv表示當c

狀態(tài)?q，當c

帶內(nèi)容?uv；讀寫頭?于v的第一個符號，v最后符號后全?空x

符；產(chǎn)生：對于格局uaqibv，若δ(qi,b)=(qj,c,L)，則格局uaqibv產(chǎn)生uqj

acvδ(qi,b)=(qj,c,R)，則格局uaqibv產(chǎn)生吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義機常用術語：格局/瞬時描述：對于狀態(tài)q、Γ上的字符串u,v，uqv表示當c

狀態(tài)?q，當c

帶內(nèi)容?uv；讀寫頭?于v的第一個符號，v最后符號后全?空x

符；產(chǎn)生：對于格局uaqibv，若δ(qi,b)=(qj,c,L)，則格局uaqibv產(chǎn)生uqj

acvδ(qi,b)=(qj,c,R)，則格局uaqibv產(chǎn)生uacqj

v吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義機常用術語：格局/瞬時描述：對于狀態(tài)q、Γ上的字符串u,v，uqv表示當c

狀態(tài)?q，當c

帶內(nèi)容?uv；讀寫頭?于v的第一個符號，v最后符號后全?空x

符；產(chǎn)生：對于格局uaqibv，若δ(qi,b)=(qj,c,L)，則格局uaqibv產(chǎn)生uqj

acv格局qibv產(chǎn)生δ(qi,b)=(qj,c,R)，則格局uaqibv產(chǎn)生uacqj

v吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義機常用術語：格局/瞬時描述：對于狀態(tài)q、Γ上的字符串u,v，uqv表示當c

狀態(tài)?q，當c

帶內(nèi)容?uv；讀寫頭?于v的第一個符號，v最后符號后全?空x

符；產(chǎn)生：對于格局uaqibv，若δ(qi,b)=(qj,c,L)，則格局uaqibv產(chǎn)生uqj

acv格局qibv產(chǎn)生δ(qi,b)=(qj,c,R)，則格局uaqibv產(chǎn)生uacqj

v吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義機常用術語：格局/瞬時描述：對于狀態(tài)q、Γ上的字符串u,v，uqv表示當c

狀態(tài)?q，當c

帶內(nèi)容?uv；讀寫頭?于v的第一個符號，v最后符號后全?空x

符；產(chǎn)生：對于格局uaqibv，若δ(qi,b)=(qj,c,L)，則格局uaqibv產(chǎn)生uqj

acv格局qibv產(chǎn)生qj

cvδ(qi,b)=(qj,c,R)，則格局uaqibv產(chǎn)生uacqj

v吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義?始格局：接受格局：格局：識別：M

識別的語言L(M

)：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義?始格局：q0w，即處于?始狀態(tài)q0，讀寫頭處于帶子最左側(cè)；接受格局：格局：識別：M

識別的語言L(M

)：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義?始格局：q0w，即處于?始狀態(tài)q0，讀寫頭處于帶子最左側(cè)；接受格局：狀態(tài)?qaccept；格局：識別：M

識別的語言L(M

)：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義?始格局：q0w，即處于?始狀態(tài)q0，讀寫頭處于帶子最左側(cè)；接受格局：狀態(tài)?qaccept；格局：狀態(tài)?qreject；識別：M

識別的語言L(M

)：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義?始格局：q0w，即處于?始狀態(tài)q0，讀寫頭處于帶子最左側(cè)；接受格局：狀態(tài)?qaccept；格局：狀態(tài)?qreject；識別：如果對于輸入w，存在格局序列C1,·

·

·

,Ck，使得M

識別的語言L(M

)：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義?始格局：q0w，即處于?始狀態(tài)q0，讀寫頭處于帶子最左側(cè)；接受格局：狀態(tài)?qaccept；格局：狀態(tài)?qreject；識別：如果對于輸入w，存在格局序列C1,·

·

·

,Ck，使得1

C1是

機M在輸入w上的?

始格局；M

識別的語言L(M

)：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義?始格局：q0w，即處于?始狀態(tài)q0，讀寫頭處于帶子最左側(cè)；接受格局：狀態(tài)?qaccept；格局：狀態(tài)?qreject；識別：如果對于輸入w，存在格局序列C1,·

·

·

,Ck，使得C1是

機M在輸入w上的?

始格局；Ci產(chǎn)生Ci+1；M

識別的語言L(M

)：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義?始格局：q0w，即處于?始狀態(tài)q0，讀寫頭處于帶子最左側(cè)；接受格局：狀態(tài)?qaccept；格局：狀態(tài)?qreject；識別：如果對于輸入w，存在格局序列C1,·

·

·

,Ck，使得C1是

機M在輸入w上的?

始格局；Ci產(chǎn)生Ci+1；Ck

是接受格局M

識別的語言L(M

)：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義?始格局：q0w，即處于?始狀態(tài)q0，讀寫頭處于帶子最左側(cè)；接受格局：狀態(tài)?qaccept；格局：狀態(tài)?qreject；識別：如果對于輸入w，存在格局序列C1,·

·

·

,Ck，使得C1是

機M在輸入w上的?

始格局；Ci產(chǎn)生Ci+1；Ck

是接受格局則稱M

識別(接受)w。M

識別的語言L(M

)：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義?始格局：q0w，即處于?始狀態(tài)q0，讀寫頭處于帶子最左側(cè)；接受格局：狀態(tài)?qaccept；格局：狀態(tài)?qreject；識別：如果對于輸入w，存在格局序列C1,·

·

·

,Ck，使得C1是

機M在輸入w上的?

始格局；Ci產(chǎn)生Ci+1；Ck

是接受格局則稱M

識別(接受)w。M識別的語言L(M

)：M

識別（接受）的字符串集合；X??

?{x|qstart

x

`

α1

tα2,

x

∈

,

t

∈

qaccept,

α1

,

α

∈

Γ

}吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義??

2

(

?(

?

?

O

)??

3

(

??

)??

4

(

?(

?

?

)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義??

2

(

?(

?

?

O

)X

J

,

?

?

?

U

,

?

?(??

O

?

K

???

?(?

?

O

?

4

8

?

q

?

?

?

"??

3

(

??

)??

4

(

?(

?

?

)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義??

2

(

?(

?

?

O

)X

J

,

?

?

?

U

,

?

?(??

O

?

K

???

?(?

?

O

?

4

8

?

q

?

?

?

"??

3

(

??

)[

?

?

? ?

(

? ?

為?

????

4

(

?(

?

?

)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機的定義??

2

(

?(

?

?

O

)X

J

,

?

?

?

U

,

?

?(??

O

?

K

???

?(?

?

O

?

4

8

?

q

?

?

?

"??

3

(

??

)[

?

?

? ?

(

? ?

為?

????

4

(

?(

?

?

)X

J

,

?

?

?

U ,

?

?

(

? ?

?K

???

?(?

?

?

4

8

?

?

"吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

1

(

E

?

?

為L

=

{0n1n|n

≥

1}

TM)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

1

(

E

?

?

為L

=

{0n1n|n

≥

1}

TM)基本思路：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

1

(

E

?

?

為L

=

{0n1n|n

≥

1}

TM)基本思路：從最左側(cè)開始，進入以下循環(huán)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

1

(

E

?

?

為L

=

{0n1n|n

≥

1}

TM)基本思路：從最左側(cè)開始，進入以下循環(huán)循環(huán)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

1

(

E

?

?

為L

=

{0n1n|n

≥

1}

TM)基本思路：從最左側(cè)開始，進入以下循環(huán)循環(huán)將0改成X，然后向右移動直到到達1；吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

1

(

E

?

?

為L

=

{0n1n|n

≥

1}

TM)基本思路：從最左側(cè)開始，進入以下循環(huán)循環(huán)將0改成X，然后向右移動直到到達1；將1改成Y

，然后向左移動直到發(fā)現(xiàn)某個X；吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

1

(

E

?

?

為L

=

{0n1n|n

≥

1}

TM)基本思路：從最左側(cè)開始，進入以下循環(huán)循環(huán)將0改成X，然后向右移動直到到達1；將1改成Y

，然后向左移動直到發(fā)現(xiàn)某個X；對于X

右側(cè)的0重復以上操作；吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例1

δ(q0,

0)

=

(q1,

X,

R)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例1

δ(q0,

0)

=

(q1,

X,

R)將0改成X吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)將0改成X吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)將0改成X向右找1吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)將0改成X向右找1吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)將0改成X向右找1向右找1吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例將0改成X向右找1向右找11

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)將0改成X向右找1向右找1將1改成Y

，返回吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例將0改成X向右找1向右找1將1改成Y

，返回1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)5

δ(q2,

Y

)

=

(q2,

Y,

L)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例將0改成X向右找1向右找1將1改成Y

，返回1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)5

δ(q2,

Y

)

=

(q2,

Y,

L)6

δ(q2,

X

)

=

(q0,

X,

R)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例將0改成X向右找1向右找1將1改成Y

，返回1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)5

δ(q2,

Y

)

=

(q2,

Y,

L)6

δ(q2,

X

)

=

(q0,

X,

R)遇X

右移，進入狀態(tài)q0及(1)循環(huán)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例將0改成X向右找1向右找1將1改成Y

，返回1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)5

δ(q2,

Y

)

=

(q2,

Y,

L)6

δ(q2,

X

)

=

(q0,

X,

R)7

δ(q2,

0)

=

(q2,

0,

L)遇X

右移，進入狀態(tài)q0及(1)循環(huán)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例將0改成X向右找1向右找1將1改成Y

，返回1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)5

δ(q2,

Y

)

=

(q2,

Y,

L)6

δ(q2,

X

)

=

(q0,

X,

R)7

δ(q2,

0)

=

(q2,

0,

L)遇X

右移，進入狀態(tài)q0及(1)循環(huán)向左找X

后面的0吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例將0改成X向右找1向右找1將1改成Y

，返回1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)5

δ(q2,

Y

)

=

(q2,

Y,

L)遇X

右移，進入狀態(tài)q0及(1)循環(huán)向左找X

后面的06

δ(q2,

X

)

=

(q0,

X,

R)7

δ(q2,

0)

=

(q2,

0,

L)8

δ(q0,

Y

)

=

(q3,

Y,

R)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例將0改成X向右找1向右找1將1改成Y

，返回1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)5

δ(q2,

Y

)

=

(q2,

Y,

L)6

δ(q2,

X

)

=

(q0,

X,

R)7

δ(q2,

0)

=

(q2,

0,

L)8

δ(q0,

Y

)

=

(q3,

Y,

R)遇X

右移，進入狀態(tài)q0及(1)循環(huán)向左找X

后面的00已全改?X

后遇到Y(jié)

，進入q3吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例將0改成X向右找1向右找1將1改成Y

，返回1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)5

δ(q2,

Y

)

=

(q2,

Y,

L)遇X

右移，進入狀態(tài)q0及(1)循環(huán)向左找X

后面的00已全改?X

后遇到Y(jié)

，進入q36

δ(q2,

X

)

=

(q0,

X,

R)7

δ(q2,

0)

=

(q2,

0,

L)8

δ(q0,

Y

)

=

(q3,

Y,

R)9

δ(q3,

Y

)

=

(q3,

Y,

R)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例將0改成X向右找1向右找1將1改成Y

，返回91

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)5

δ(q2,

Y

)

=

(q2,

Y,

L)6

δ(q2,

X

)

=

(q0,

X,

R)7

δ(q2,

0)

=

(q2,

0,

L)8

δ(q0,

Y

)

=

(q3,

Y,

R)δ(q3,

Y

)

=

(q3,

Y,

R)遇X

右移，進入狀態(tài)q0及(1)循環(huán)向左找X

后面的00已全改?X

后遇到Y(jié)

，進入q3向右找吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例將0改成X向右找1向右找1將1改成Y

，返回9遇X

右移，進入狀態(tài)q0及(1)循環(huán)向左找X

后面的00已全改?X

后遇到Y(jié)

，進入q3向右找1

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)5

δ(q2,

Y

)

=

(q2,

Y,

L)6

δ(q2,

X

)

=

(q0,

X,

R)7

δ(q2,

0)

=

(q2,

0,

L)8

δ(q0,

Y

)

=

(q3,

Y,

R)δ(q3,

Y

)

=

(q3,

Y,

R)10

δ(q3,

)

=

(q4,

,

0)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例將0改成X向右找1向右找1將1改成Y

，返回91

δ(q0,

0)

=

(q1,

X,

R)2

δ(q1,

0)

=

(q1,

0,

R)3

δ(q1,

Y

)

=

(q1,

Y,

R)4

δ(q1,

1)

=

(q2,

Y,

L)5

δ(q2,

Y

)

=

(q2,

Y,

L)6

δ(q2,

X

)

=

(q0,

X,

R)7

δ(q2,

0)

=

(q2,

0,

L)8

δ(q0,

Y

)

=

(q3,

Y,

R)δ(q3,

Y

)

=

(q3,

Y,

R)遇X

右移，進入狀態(tài)q0及(1)循環(huán)向左找X

后面的00已全改?X

后遇到Y(jié)

，進入q3向右找10

δ(q3,

)

=

(q4,

,

0)0,1個數(shù)相當，接受并停機吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例：吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例：δ(q3,

1)

=

(qreject,

1,

0)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例：δ(q3,1)=(qreject,1,0)1的個數(shù)比0的個數(shù)多，吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例，：δ(q3,1)=(qreject,1,0)1的個數(shù)比0的個數(shù)多δ(q3,

0)

=

(qreject,

0,

0)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例，：δ(q3,1)=(qreject,1,0)1的個數(shù)比0的個數(shù)多δ(q3,0)=(qreject,0,0)1后面還有0，吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例，，：δ(q3,1)=(qreject,1,0)1的個數(shù)比0的個數(shù)多δ(q3,0)=(qreject,0,0)1后面還有0δ(q1,

)

=

(qreject,

,

0)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例，，：δ(q3,1)=(qreject,1,0)1的個數(shù)比0的個數(shù)多δ(q3,0)=(qreject,0,0)1后面還有0δ(q1,)=(qreject,,0)0的個數(shù)比1的個數(shù)多，吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例01XY吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例01XYq0

(q1,

X,

R)(q3,

Y,

R)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例01XYq0

(q1,

X,

R)(q3,

Y,R)q1

(q1,

0,

R)(q2,

Y,

L)(q1,

Y,R)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例01XYq0

(q1,

X,

R)(q3,

Y,

R)q1

(q1,

0,

R)(q2,

Y,

L)(q1,

Y,

R)q2

(q2,

0,

L)(q0,

X,

R)(q2,

Y,

L)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例01XYq0(q1,

X,

R)(q3,

Y,

R)q1(q1,

0,

R)(q2,

Y,

L)(q1,

Y,

R)q2(q2,

0,

L)(q0,

X,

R)(q2,

Y,

L)q3(q3,

Y,

R)(q4,

,

R)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例01XYq0(q1,

X,

R)(q3,

Y,

R)q1(q1,

0,

R)(q2,

Y,

L)(q1,

Y,

R)q2(q2,

0,

L)(q0,

X,

R)(q2,

Y,

L)q3(q3,

Y,

R) (q4,

,

R)q4吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：q00011吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：q00011`

Xq1011吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：q00011`

Xq1011`

X0q111吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：q00011`

Xq1011`

X0q111`

Xq20Y

1吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：`

X0q111`

Xq20Y

1q00011`

Xq1011`

q2X0Y

1吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：`

X0q111`

Xq20Y

1q00011`

Xq1011`

q2X0Y

1

`

Xq00Y

1吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：q00011`

Xq1011`

q2X0Y

1

`

Xq00Y

1`

X0q111

`

Xq20Y

1`

XXq1Y

1吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：q00011`

Xq1011`

q2X0Y

1

`

Xq00Y

1`

X0q111`

Xq20Y

1`

XXq1Y

1`

XXYq11吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：`

X0q111`

Xq20Y

1`

XXq1Y

1`

XXYq11q00011`

Xq1011`

q2X0Y

1

`

Xq00Y

1`

XXq2Y

Y吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：`

X0q111`

Xq20Y

1`

XXq1Y

1`

XXYq11q00011`

Xq1011`

q2X0Y

1

`

Xq00Y

1`

XXq2Y

Y

`

Xq2XY

Y吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：q00011`

Xq1011`

q2X0Y

1

`

Xq00Y

1`

XXq2Y

Y

`

Xq2XY

Y`

X0q111`

Xq20Y

1`

XXq1Y1`

XXYq11`

XXq0Y

Y吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：q00011`

Xq1011`

q2X0Y

1

`

Xq00Y

1`

XXq2Y

Y

`

Xq2XY

Y`

X0q111`

Xq20Y

1`

XXq1Y1`

XXY

q11`

XXq0YY

`

XXY

q3Y吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：`

X0q111`

Xq20Y

1`

XXq1Y1`

XXY

q11`

XXq0YY

`

XXY

q3Yq00011`

Xq1011`

q2X0Y

1

`

Xq00Y

1`

XXq2Y

Y

`

Xq2XY

Y`

XXY

Yq3吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00011：`

X0q111`

Xq20Y

1`

XXq1Y1`

XXY

q11`

XXq0YY

`

XXY

q3Yq00011`

Xq1011`

q2X0Y

1

`

Xq00Y

1`

XXq2Y

Y

`

Xq2XY

Y`

XXY

Yq3

`

XXY

Yq4吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00010:q00010吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00010:q00010`

Xq1010吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00010:q00010`

Xq1010`

X0q110吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00010:q00010`

Xq1010`

X0q110`

Xq20Y

0吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00010:`

X0q110`

Xq20Y

0q00010`

Xq1010`

q2X0Y

0吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00010:`

X0q110`

Xq20Y

0q00010`

Xq1010`

q2X0Y

0

`

Xq00Y

0吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00010:q00010`

Xq1010`

q2X0Y

0

`

Xq00Y

0`

X0q110`

Xq20Y

0`

XXq1Y

0吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00010:q00010`

Xq1010`

q2X0Y

0

`

Xq00Y

0`

X0q110`

Xq20Y

0`

XXq1Y0`

XXYq10吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例考慮初始格局?q00010:`

X0q110`

Xq20Y

0`

XXq1Y0`

XXYq10q00010`

Xq1010`

q2X0Y

0

`

Xq00Y

0`

XXY

0q1吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例q0startq1q2q3q4Y

→

Y,

R,

0

→

0,

R0

→

X,

R

1

→

Y,

LY

→

Y,

L,

0

→

0Y

→

Y,

RX

→

X,

RY

→

Y,

R→

,

0吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

2

(

E

?

?

為{

+1|n

≥

0}

TM)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

2

(

E

?

?

為{

+1|n

≥

0}

TM)δ(q0,

a)

=

(q1,

X,

R)吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

2

(

E

?

?

為{

+1|n

≥

0}

TM)δ(q0,

a)

=

(q1,

X,

R)將a改寫?X吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

2

(

E

?

?

為{

+1|n

≥

0}

TM)δ(q0,

a)

=

(q1,

X,

R)δ(q1,

a)

=

(q1,

a,

R)將a改寫?X吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

2

(

E

?

?

為{

+1|n

≥

0}

TM)δ(q0,

a)

=

(q1,

X,

R)δ(q1,

a)

=

(q1,

a,

R)將a改寫?X向右找b吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

2

(

E

?

?

為{

+1|n

≥

0}

TM)δ(q0,

a)

=

(q1,

X,

R)δ(q1,

a)

=

(q1,

a,

R)δ(q1,

Y

)

=

(q1,

Y,

R)將a改寫?X向右找b吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算法的定義機示例~

2

(

E

?

?

為{

+1|n

≥

0}

TM)δ(q0,

a)

=

(q1,

X,

R)δ(q1,

a)

=

(q1,

a,

R)δ(q1,

Y

)

=

(q1,

Y,

R)將a改寫?X向右找b向右找b吳鋌-?(?K杭州電子科技大學計算機學院機的設計技術機的變形算