Сабақ тақырыбы: Абстрактылы Пост машинасы Сабақ мақсаты: Студенттерге Пост машинасында есеп шығаруды уйрету

 

№ 6-7 зертханалық жұмыс  

Сабақ тақырыбы: Абстрактылы Пост машинасы 

 

Сабақ мақсаты: Студенттерге Пост машинасында есеп шығаруды уйрету.

 

Қарастырылатын негізгі мәселелер: Пост машинасында есептерге программа 

құру.

 

Абстрактілі Поста машинасы бірдей секцияларға бөлінген шексіз лентадан, сондай-

ақ  оқитын-жазатын  бастиектен  тұрады.  Әрбір  секция  бос  (оған  ештеңе  жазылмаған), 

немесе  толтырылған  (белгіленген  -  оған  белгі  жазылған)  болуы  мүмкін.  Қай  секция  бос, 

қайсысы  белгіленгендігі  туралы  ақпарат  –  лентаның  қалып-күйі  (басқаша  айтқанда 

лентаның қалып-күйі – белгілерді секция бойынша үлестіру, яғни секцияның әрбір сандық 

номіріне  немесе  белгі  немесе  “бос”  таңбасын  сәйкестендіретін  функция)  ұғымы 

енгізіледі.  Машинаның  жұмыс  процесінде  лентаның  күйі  өзгереді.  Лентаның  күйі  мен 

бастиектің жағдайы туралы ақпарат Пост машинасының күйін сипаттайды.  

Бақылайтын секциядағы бастиекті «

» таңбасымен, ал секция ішіндегі белгіні «M» 

таңбасымен белгілейміз. Бос секция ешқандай белгіден тұрмайды. Бір тактыда (оны қадам 

деп  атайды)  бастиек  бір  секцияға  оңға  немесе  солға  ығыса  алады  және  белгіні  қояды 

немесе  жояды.  Поста  машинасының  жұмысы  –  берілген  жеке  бұйрықтардан  тұратын 

бағдарламамаға  сәйкес  бір  күйден  екінші  күйге  өту  болып  табылады.  Әрбір  команданың 

құрылымы  мынадай:  xKy,  мұндағы  x  –  орындалатын  команды  номері;  K  –  орындалатын 

әрекет  туралы  нұсқау;  y  –  келесі  команда  номері  (мұрагер).  Алты  әрекеттен  тұратын 

машина командаларының жүйесі келесі кестеде келтірілген: 

Рет 

№  

 

Команда 

команда 

жазылуы 

машина әрекетін сипаттау 

1 

Қадам 

оңға 

X

y 

Бастиекті бір секцияға оңға 

ығыстыру 

2 

Қадам 

солға 

X

y 

Бастиекті бір секцияға солға 

ығыстыру 

3 

Белгіні 

қою 

XMy 

Бақыланатын секцияға белгі қою 

4 

Белгіні 

өшіру 

XCy 

Бақыланатын секциядан белгіні 

жою 

5 

Басқаруды 

беру 

 

Бақыланатын секцияда белгі 

болмаса басқару y

1

 командасына, ал 

белгі болса –y

2

 командасына 

беріледі. 

6 

Тоқтату 

x тоқта 

Машина жұмысын тоқтату 

Бұл тізім келесі шарттармен толықтырылу керек: 

 

 командасы тек бос секцияда ғана орындалуы мүмкін;  

 

 командасы тек толтырылған секцияға ғана қолданылады;  

 

кез  келген  команданың  мұрагерінің  номері  наследника  любой  команды  (y) 

берілген бағдарламада міндетті түрде болатын команда номеріне сәйкес келуі тиіс.  

Егер  берілген  шарттар  орындалмаса,  онда  машинаның  нәтижесіз  тоқтатылуы 

болады,  яғни  жоспарланған  нәтижені  алғанға  дейінгі  тоқтату.  Бұл  жағдайдан   

командасымен  тоқтатудың  айырмашылығы  ол  нәтиже  береді,  яғни  алгоритм 

орындалуының нәтижесі алынғаннан кейін тоқтайды. Сондай-ақ, егер бір  де бір  команда 

тоқта  командасының  номеріне  көрсетілмесе  немесе  бағдарлама  бұл  командаға  өтпесе  -  

машина ешқашан да тоқтатылмайтын жағдай да болуы мүмкін.  

Тағы  бір  ескеретін  мәселе:  кез  келген  шектелген  алфавит  таңбалары  цифрлармен 

кодталатын болғандықтан, берілген сөзді түрлендіру сандарды өңдеудің кейбір ережелері 

түрінде  көрсетілуі  мүмкін.  Сондықтан  Пост  машинасында  тек  бүтін  оң  сандарды 

жазу(көрсету) қарастырылады.  

 

k  бүтін  саны  Пост  машинасының  лентасында   k+1  бірінің  артына  бірі  орналасқан 

белгіленген  секциялар  түрінде  жазылады,  яғни  унарлық  санау  жүйесі  қолданылады. 

Санның көрші жазулары лентада бір немесе бірнеше бос секциялармен бөлінген. Төменде 

0, 2 және 3 сандарының жазылу мысалы келтірілген. 

M  M M M       M M M M