Лекция 8. Тақырыбы: Шекті автоматтарды минимизациялау

Лекция 9.

Тақырыбы: Магазинді автомат

1. 
   Магазинді автоматтар
   
2. 
   Детерминирлі магазинді автоматтар
   

1. Магазинді автоматтарды магазиндік жадысы бар автоматтар не МП автоматтар депте атайды. Ол формольді түрде былай анықталады:

Анықтама. МП- автомат Р═(Q, ∑‚ Г, , q₀, Z₀,F) жетілігімен анықталады. Мұндағы:

-Q- жағдайлардың шекті жиыны.

-∑- шекті енуші алфавит.

-Г- магазиндік символдардың шекті алфавиті.

-- ауысу функциясы, Q х (∑U{е})х Г жиынның QxГ ^* жиынының ішкі жиыныдарында бейнеленуі.

- q₀ €Q- басқару құрылғысының бастапқы жағдайы.

- Z₀ €Г- бастапқы моментте магазинде орналасқан символ (бастапқы символ)

- F Q- аяқтаушы символдар жиыны.

(q, ω,a) € QxΣ*хГ*, мұнда q –басқару құрылғысының ағымдағы жағдайы, ω-енушітізбектің пайдаланылмаған бөлігі.(Егер ω=, онда барлық енуші тізбек оқылған деп есептелінеді), а-магазин мәні (а-тізбегінің сол жақ бірінші символы магазиннің жоғарғы символы деп саналады; егер а= болса, онда магазин бос деп есептеледі.).

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

МП-автомат пен танылатын тілдер классы, дәлме-дәл КБ- грамматикалармен берілетін тілдер классымен сәйкес түседі. (мұны дәлелдеп отырмаймыз).

МП- автоматтқа мысал

{0ⁿ1^h I n≥0} тілік танитын МП –автоматтты қарастырамыз.

Айталық P=({ q_0, q_1, q₂ },{0,1},{Z, 0},, q₀, Z, {q₀} ), мұнда :

 (q_0, 0,Z)={(q₁, OZ)}

 (q_1,0, 0)={(q₁, OO)}

 (q₁, 1,0)={(q₂, )}

 (q₂, ,z)={(q_0,, )}

Автомат жұмысының енуші тізбектен бастапқы нольдерді магазинге көшіру және бұдан кейінгі әрбір оқылған бірлікке магазиннен бір-бір нольден алып тастап отырудан тұрады.

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

Анықтама:МП-автомат P=(Q,,,Г,q_0,,,Z_0,,F) детерминирлі деп аталады, егер әрбір qQ және ZГ үшін келесі бекітімдердің біреуі дұрыс болатын болса:

-(q,a,z)-ң a және (q,e.z)= үшін біреуден артық элемменті жоқ.

-(q,a,z)-ң барлық а және (q,e,z)үшін біреуден артық элемменті жоқ.

Өкінішке орай,дитирмирирлі МП-автоматтар барлық КБ-тілдер классының ішкі жиынын ғана бейнелейді. Ол ішкі жиын детерминирлі КБ -тілдері деп аталады. Бұл тілдер классын LR(k)-грамматикалар деп те атайды, өйткені олар тізбекті солдан оңға қарай бір мәнді анықталуы мүмкін. Тізбектің алдын К символға дейін ғана қарай алады.

Детерминирлі КБ-тілдер, КБ-тілдердің толық классы сияқты, бұлармен анықталатын тілдің бостығын не берілген тізбектің тілге тиістілігін тексеруге мүмкіндік береді. Бірақ детерминирлі КБ-тілдер кейбір маңызды теориялық-жиындық қассиеттерге ие емес. Мысалы: детерминирлі КБ-тілдер қиылысу, толықтырылып не біріктіруге қатысты тұйықталмаған.

Бұған қарамастан, компиляция әдісі тұрғысыннан алғанда, LR(k)-грамматикалар классы үлкен маңызға ие. Өйткені, синтаксистік айқындау (разбор) құралдары осы грамматикаларға негізделген.