Дүкендік автоматтар

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

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

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

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

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

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

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

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

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