Tyurinq maşınının qrafla təsviri
Tyurinq maşınını qrafla təsvir edərkən hər bir vəziyyətə qrafın zirvəsi,hər bir əmrə isə -işarələnmiş əyrini uyğunlaşdırmaq lazımdır.
Yuxarıda baxdığımız misala uyöun olaraq Tyurinq maşını qraf şəklində aşağıdakı kimi olacaqdır:
Başlanğıc və son zirvələr adətən seçilməlidir:şəkildə onlar qara dairələrlə işarələnmişdir,Əgər Tyurinq maşınının işinin növbəti taktında lentdəki simvol dəyişmirsə,onda əmrin sağında onu yazmasaq da olar.(qz vəziyyətində ε).
Tyurinq maşınının cədvəllə təsvir edilməsi
Bu üsulla təsvir zamanı cədvəl aşağıdakı üsulla tərtib edilir:hər vəziyyətə sətir,giriş əlifbasının hər bir simvoluna isə sütun uyğun gəlir.Cədvəlin xanalarında isə(sətir və sütunun birləşməsində) yerinə yetiriləcək hərəkət(ya da əmrin sağ tərəfi).
Verilmiş misal öçün Tyurinq maşının uyğun cədvəli aşağıdakı kimi olacaqdır:
|
0
|
1
|
Ε
|
q0
|
q01R
|
q00R
|
q1 εL
|
q1
|
q10L
|
q11L
|
qz εL
|
Giriş zəncirinin çevrilməsinin Tyurinq maşını proqram ilə yerinə yetirmək olar.Bu proqram 6 əmrdən ibarətdir.
Dostları ilə paylaş: |