Детерминантты шекті автоматтар. Мур диаграммасы

1.

ТАҚЫРЫБЫ: ДЕТЕРМИНАНТТЫ ШЕКТІ АВТОМАТТАР. МУР
ДИАГРАММАСЫ
Кіріспе
Шекті автоматтардың формальді анықтамасы
Детерминирлі шекті автомат
Шекті автоматты Мур диаграммалары арқылы
бейнелеу.
Трансляцияның формальды модельдері
БНФ-грамматика немесе контекстілі еркін грамматика
БНФ-грамматиканың синтаксисі
Қорытынды

2.

Автомат – бұл формальді қабылдаушы жүйе. Автоматтың
ережелері енуші тізбектің берілген тілге тиістілігін анықтайды.
Автомат берілген грамматика эквивалентті деп аталады, егер тек
осы грамматика тудыратын тілді ғана толық қабылдайтын болса.
Шекті автомат – тілдер мен жұмыс істеуде қолданылатын ең
қарапайым механизм. Бұл танушының тұрақты жады
ұяшықтарының жиыны бар. Ал басқару құрылғысы енуші лента
бойымен оңға ғана жылжи алады және жады жағдайын өзгерте
алады. Шекті автоматтың негізгі бөлігі – бұл өту функциясы. Өту
функциясы кез келген ағымдағы жағдай үшін және кез келген
енуші символ үшін мүмкін болған өтулерді анықтайды.

3.

Детерминантты емес дегенді былай ұғу керек: егер берілген
жағдайда әр түрлі жағдайға өту мүмкіндігі бар болса, онда әр бір
жаңа жағдай үшін автоматтың бірнеше көшірмесі құрылады (
дайындалады). Тізбек тілге тиісті деп есептелінеді, егер қадамдар
қатарларының ең құрығанда бір (бір қадамдар қатары) соңғы,
аяқтаушы жағдаймен аяқталса.

4.

Анықтама. Шекті автомат (ША)
ША = ( Q, Σ, б, q 0, F) бестігімен анықталады.
Мұнда:
Q – Жағдайлардыњ шекті жиыны.
Σ – мүмкін болған енуші символдардыњ шекті жиыны ( енуші
алфавит ).
• d - басқару құрылғысын қимылын (поведение) анықтайтын P(Q)
жиындағы Q x Σ жиыныныњ бейнесі. (Бұл функцияны өту
функциясы деп атайды.) Бұл бейнелеудіњ элементтері ереже деп
аталады.
• q 0 € Q – Басқару құрылғысыныњ бастапқы жағдайы.
• F Í Q – cоњғы (терминал ) жағдайлар жиыны.

5.

Детерминирлі шекті автоматтар
Детерминантты шекті автоматты жалпы (детерминантты емес)
шекті автоматтың дербес жағдай ретінде анықтаймыз. Бұған
қосымша кейбір анықтамаларды келтіріп өтеміз.
Анықтама: Автомат детерминантты деп аталады егер d (q,а)
жиынында кез келген q, а үшін жағдайлар саны 1-ден артпаса.
Егер d (q,а) әрдайым дәл 1 жағдайдан тұрса (яғни анықталмаған
ауысулары жоқ), орнда автоматты толық анықталған деп атайды.
Анықтама: алфавитінен құрылған W = а1... ак сөзін М=(Q, )
шекті автоматты өткізеді, егер мынадай q1,q2,…,qn жағдайлар
қатары бар болса; q1= qo, qn Î F және кез – келген i,j үшін
• 1£ I<n, 1£ j < k (qi aj) = qi + 1

6.

Грамматика программалау тілдің анықталуы үшін
мүмкін символдар тізбегін анықтайтын ережелер
жиынтығынан
тұрады.
Формальді
грамматика
дегеніміз
қатаң белгілеулер жүйесінен тұратын
грамматика,
компиляциялау
технологиясында
грамматиканың 2 класы қолданылады:
• БНФ грамматика немесе контекстілі еркін грамматика
• Регулярлы грамматика

7.

БНФ грамматика. Ағылшын тіліндегі сөйлем құрылымын
қарастыра отырып оның категориялары тілдегі қарапайым
хабарлас сөйлем мынадай сөйлемнен тұрады:
Бастауыш |етістік| толықтауыш //The gіrl (runs) home.
Әрбір категория өз кезегінде ішкі категорияларға бөлінуі
мүмкін. Мыс: жоғарыдағы құрылымда бастауыш
артикль және зат есімнен тұрады. Олай болса құрылым
былай жазылуы мүмкін.
артикль |зат есім| етістік | толықтауыш

8.

БНФ грамматиканың синтаксисі. БНФ грамматика
программалау тілдерін анықтайтын грамматика
ережелерінің аяқталған жиынтығынан тұрады. Бұл
ережелерді қарастырмас бұрын тіл түсінігіне тоқталайық.
Синтаксис мәндермен емес тікелей формалармен жұмыс
істейтін болғандыңтан синтаксис тұрғысынан алып
қарағанда программалау тілі әрқайсысы символдар
жиынтығынан тұратын дұрыс программаның жиынтығы.
Семантикаға қатысты синтаксисті дұрыс программа
ешқандай мәнге ие болмауы мүмкін жағдайда мысалдарға
қайта оралсақ, онда келесі сөйлем мына ережелерге сәйкес
келеді:
• бастауыш | етістік | толықтауыш

9.

Бұл анықтау негізінде келесі аталғандарды тіл деп
қарастыруға болады.
Си-дегі барлық меншіктеу операциялардың жиынтығы.
Си-гі барлық программаның жиынтығы.
lіsp-тегі барлық аталғандардың жиынтығы.
a және b элементтен тұратын тізбектер жиынтығы