Formal diLLƏr və avtomatlar nəZƏRİYYƏSİ


Tyurinq maşını üzərində əməllər



Yüklə 281 Kb.
səhifə9/25
tarix02.01.2022
ölçüsü281 Kb.
#43181
növüMühazirə
1   ...   5   6   7   8   9   10   11   12   ...   25
formal dillər və avtomatlar nəzəriyyəsi.Mühazirələr

3.6. Tyurinq maşını üzərində əməllər.


  1. Tyurinq maşınının kompoziyası.

Tutaq ki, T1 və T2 maşınlarının P1 və P2 proqramları var..Hesab edək ki,bu maşınların daxili əlifbaları kəsişmir:haradaki, qz1 - T1 maşınının son vəziyyəti,q02 - T2 maşınının başlanğıc vəziyyəti.

P1 proqramının hər yerində qz1 son vəziyyətini T2 maşınının q02 başlanğıc vəziyyəti ilə əvəz edək və yaranmış proqramı P2 proqramı ilə birləşdirək.Yeni yaranmış P proqramı (qz1, q02) vəziyyətlərinə uyğun olaraq T1 və T2 maşınlarının kompoziyası olan T maşınını təyin edir.Maşınların kompoziyasını T1 .T2 və ya T1 T2 kimi işarələyə bilərik.Maşınların daha ətraflı kompoziyası aşağıdakı kimi olacaqdır:
T= T(T1 ,T2 (qz1, q02)) , haradaki,

T1=(Q1,A1, δ1,P01,Pz1,a01,a11) ,

T2=(Q2,A2, δ2,P02,Pz2,a02,a12) .

Tutaq ki,

a01=a02=a0

a11=a12=a1

Onda T1 T2 kompoziyalarının xarici əlifbası T1 və T2 maşınlarının xarici əlifbalarının birləşməsindən əmələ gələcəkdir.

Alqoritmlər üzərində aparılan kompozisiya əməliyyatı əvvəlcədən məlum olan sadə alqoritmlərdən daha mürəkkəb alqoritmlərin alınmasına gətirib cıxarır.



  1. Tyurinq maşınının iterasiyası

Bu əməliyyatı ancaq bir maşında yerinə yetirmək olar.Tutaq ki, qz – T maşınının son vəziyyətidir və qn isə T maşınının hər hansı sonuncu olmayan bir vəziyyətidir. T maşınının P proqramının hər yerində qz –i qn ilə əvəz edək.Alınmış proqram yeni T(qz, qn) maşınını təyin edəcəkdir,hansı ki, (qz, qn) vəziyyətlərinə görə T maşınının iterasiyası adlanacaqdır.

  1. Tyurinq maşınının budaqlanması.

Tutaq ki, T1 , T2 və T3 Tyurinq maşınları uyğun olaraq P1,P2 və P3 proqramları ilə verilmişdir.Hesab edək ki,bu maşınların daxili əlifbası cüt-cüt kəsişmir və tutaq ki, qz11 və q z12 - T1 maşınını hər hansı müxtəlif vəziyyətləridir.

P1 proqramının hər yerində qz11 vəziyyətini T2 maşınının başlanğıc olan q02 ilə,qz12 vəziyyətini isə T3 maşınının q03 başlanğıc vəziyyəti ilə əvəz edək .Sonra yeni proqramı P2 və P3 proqramları ilə birləşdirək.Bu zaman Tyurinq maşınının P proqramını almış olarıq və bu aşağıdakı kimi işarələnəcəkdir


T=T(T1,( qz11, q02),T2(qz12, q03), T3)

T maşını T1 maşını ilə ilə idarə olunan T2 və T3 maşınlarının budaqlanmasından əmələ gəlmişdir.




Yüklə 281 Kb.

Dostları ilə paylaş:
1   ...   5   6   7   8   9   10   11   12   ...   25




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin