Ақырлы автоматтарда жұмыс лентасы болмайды

Автоматтың формальды анықтамасы

Инициалданбаған автомат – бұл А = (К, X, Y, δ, γ) түрдегі бестік, мұндағы К – күйлердің жиыны (күйлердің алфавиті); Х – кіру алфавиті; Y – шығу алфавиті; δ – К: Х→К бейнелеуді беретін өту функциясы; γ – К: Х→У бейнелеуді беретін шығу функциясы.

Автоматтың функцияларын келесі түрдегі командалардың жиыны ретінде беруге болады: qx → py, мұндағы q және p ∈ K, x ∈ X, y ∈ Y.

t_i қайсыбір тактісінде басқару құрылғысы q жағдайда болсын, ал кіру лентасынан x символы оқылсын делік. Егер командалардың жиынында qx → py командасы бар болса, онда t_i тактісінде шығу летасына у символы жазылады, ал келесі t_i +1 тактісінде басқару құрылғысы р жағдайына өтеді, яғни:

y(t) = γ(q(t), x(t)), q(t-1) =δ(q(t), x(t)).

Егер qx → py командасы болмаса, онда автомат бұғатталады және t_i моментінде қабылданған символға ешқандай әсер білдірмейді, сонымен қатар уақыттың келесі моментіндегі символдарды да қабылдамайды.

Инициалданбаған автоматтың анықтамасына сәйкес, жағдайдың алғашқы сәтінде автомат ерікті болуы мүмкін.

Егер қандай да бір алғашқы жағдай алдын – ала бекітілген болса, онда мұндай автоматты инициалданған автомат деп атайды, яғни q(0) = q₀.

Инициалданған автомат – бұл А = (К, X, Y, δ, γ, q₀) түріндегі алтылық, мұндағы К – жағдайлардың жиыны (жағдайлардың алфавиті); Х – кіру алфавиті; Y – шығу алфавиті; δ - өту функциясы (К: Х → К бейнелеуі); γ – шығу функциясы (К: Х → У бейнелеуі); q₀ – алғашқы жағдай.

Дәріс

Тақырып:Дүкендік автоматтар. Дүкендік автомат жұмысы.

-грамматика шынжыр құрылымын анықтайды және нақты тілдегі шынжырды құруға мүмкіндік береді.

Формалды тілдер және грамматикалармен байланысты жұмыстарда кіріс лентасынан, басқару құралы және көмекші лента ол дүкен немесе етек деп аталатын көмекші лентадан тұратын дүкендік автомат моделі қолданылады.

Кіріс лентасы торларға бөлініп, ол торларға кіріс алфавитінің символдарын жазуға болады. Кіріс лентасының бастауы (басы) бір жаққа қарай ғана – оңға немесе орнында, қозғалып тұрады. Ол тек оқып тұру қызметін ғана атқарады. Ал көмекші лента оқып оқып және жазып алу қызметтерін атқара алады.

Қарастырылып жатқан кезде бүршік астындағы позицияны дүкен шыңы деп атайды.

дүкендік автомат жеті объектілерінің арақатынасымен анықталады.

функциясы үштігін екілігіне суреттейді, онда және - символ в вершине магазина, для детерминированного автомата или в множество падетерминалданған автоматтар немесе детерминалды емес автомат жиыны үшін дүкеннің шыңындағы символ.

Бұл функция дүкендік автоматтың жай-күйінің кіріс лентасынан және кіріс бүршігінің орын ауыстыруы кезінде болатын жағдайын мазмұндайды. Кейінгіде дүкендік автоматтарды құру кезінде кіріс бүршігінің орын ауыстыруынсыз өзгеретін орын ауыстыру функциясының екі түрі қажет болады:

1 орын ауыстыру функциясы бос символдар кіріс символы ретінде: , ол кіріс лентасының оқылып жатқан бүршігінің астындағы символға қарамастан дүкен шыңынан символын оқып алып, автомат жай-күйін және шыңдарын дүкенге жазып алып өзгертеді.

2 орын ауыстыру функциясы нақты кіріс символымен: , ол шынжырдың жай-күйінің өзгеруі мен жазылуын дүкенге символы кіріс бүршігінен оқылатын жағдайда, ал дүкен шыңында символы тұратын болса, қосып жазады.