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

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

Жоспар:

1. Шекті автоматтардың формальді анықтамасы

2. Детерминирлі шекті автомат

3. Шекті автоматты Мур диаграммалары арқылы бейнелеу.

4. Трансляцияның формальды модельдері

5. БНФ-грамматика немесе контекстілі еркін грамматика

6. БНФ-грамматиканың синтаксисі

 

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

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

Енді шекті автоматты формальді анықтамасын келтіреміз:

Анықтама. Шекті автомат (ША)

ША = ( Q, Σ, б, q 0, F) бестігімен анықталады.

Мұнда:

• Q – Жағдайлардыњ шекті жиыны.

• Σ – мүмкін болған енуші символдардыњ шекті жиыны ( енуші алфавит ).

• d - басқару құрылғысын қимылын (поведение) анықтайтын P(Q) жиындағы Q x Σ жиыныныњ бейнесі. (Бұл функцияны өту функциясы деп атайды.) Бұл бейнелеудіњ элементтері ереже деп аталады.

• q 0 € Q – Басқару құрылғысыныњ бастапқы жағдайы.

• F Í Q – cоњғы (терминал ) жағдайлар жиыны.

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

 

 

                    Детерминирлі шекті автоматтар

Детерминантты шекті автоматты жалпы (детерминантты емес) шекті автоматтың дербес жағдай ретінде анықтаймыз. Бұған қосымша кейбір анықтамаларды келтіріп өтеміз.

Анықтама: Автомат детерминантты деп аталады егер 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

 

 

Анықтама:  L тілі шекті автоматпен танылады, егер Lтілініњ әрбір сөзі шекті автоматпен өткізілсе.

 

 

Мысалдар:

1. Айталық детерминирлі шекті автомат былай берілсін::

ША = (Q, ,  , qa F)

Q = { S, A, B, qf},   = {0.1}

= {SO ® qf, SO ® A, A1® B, BO ® qf , BO ® A}

Ауысу диаграммасы былай бейнеленеді.

<идент>:: = <әріп> <идент> :: = <идент><әріп><идент> ::= <идент><цифр><әріп>:: = a½ b½ :..½ = <цифр> ::= <әріп>½ <цифр>

 

 

d :

	1	2	3
<әріп>	2	2	-
<цфр>	4	2	-
<соңы>	4	3	-
<әйтпесе>	4	-	-

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   

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

Бұл матрицаның кейбір элементері- артық. Дәлірек 3-баған тіпті керегі жоқ. Мұндай “артық” жағдайлар қателер тексеру (диагностикасы үшін) қызмет етуї мүмкін. Енуші алфавит-бұл автомат қабылдай алатын объект. Автомат оларды өзара ажыратуға айталық, әріппен цифрларды айыруы міндетті емес.

 

Трансляцияның формальді модельдері бұрын қарастырғандай синтаксистік құрылымдарды оқуға қатысты компиляция теориясының бөлімі стандартты болып келеді және де контексті еркін тілдер теориясына негізделеді. Программалау тілінің синтаксистік формальді анықталуы әдетте  грамматика деп аталады.

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

1. БНФ грамматика немесе контекстілі еркін грамматика
2. Регулярлы грамматика

БНФ грамматика. Ағылшын тіліндегі сөйлем құрылымын қарастыра отырып оның категориялары тілдегі қарапайым хабарлас сөйлем мынадай сөйлемнен тұрады:

Бастауыш |етістік| толықтауыш //The   gіrl (runs) home.

Әрбір категория өз кезегінде ішкі категорияларға бөлінуі мүмкін. Мыс: жоғарыдағы құрылымда бастауыш артикль  және зат есімнен тұрады. Олай болса құрылым былай жазылуы мүмкін.

    артикль |зат есім| етістік | толықтауыш

Бұдан басқа сұраулы сөйлемдердің де құрылымы былай жазылады:

Кәмекші етістік |бастауыш |баяндауыш

Мысалы: dіd| the gіrl| run home?

Келтірілген сөйлемдерді қандай да бір ереженің жиынтығы арүылы сипатттау мүмкін. Яғни біз сөйлемнің хабарлы не сұраулы болатынын айта аламыз немесе оны былай жазуға болады: <сөйлем>::=<хабарлы>| <сұраулы>. Мұндағы :: = белгісі – аталған категорияның белгілерінің оң жағындағы ішкі категорияға бөліну мүмкіндігін білдіреді. Яғни келтірілген құрылымды былайша оқиды. Сөйлемдердің келесі тармақталуы былайша анықталады:

<хабарлы>::=<бастауыш><етістік><толықтауыш>

<бастауыш>::=<артикль><зат есім>

<сұраулы>::= <қосымша етістік><бастауыш><баяндауыш>

осылайша, арнайы жазуды бнф-бэкустың нормал формалары деп атады. Оны 50-ші  жылдардың соңында  algol тілінің синтаксистік  анықталуы ретінде пайдаланып жария етті. Шамамен осы жылдары ноам хомский осыған ұқсас грамматикалық форманы ұсынып, оны контекстілі-еркін грамматика деп атады. Ол табиғи тілдердің синтаксисін келтіру үшін арналды. БНФ және контекстілі еркін грамматика формалары мүмкіндіктері жағынан эквивалентті болып келеді. Айырмашылығы - олардың белгілеулер жүйесінде  ғана, сондыңтан синтаксис мәселен талқылау барысында БНФ грамматика және контексті еркін грамматика терминдері өзара бірін-бірі ауыстыратын сөздер ретінде қолданылады.

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

бастауыш | етістік | толықтауыш

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

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

Мұнда әрбір а элементі кез келген тізбекте b элементінен алдын орналасады. Бұл тілдің құрылымына мұқият зер сала отырып, олардың анықталуының  жеткіліксіз екеніне кәз жеткізуге болады.  Бұл ережелер тілде қандай байланыстарды қолдануға болатындығын анықтайды. Қарапайым жаұдайда грамматикалық ереже жай ғана тіл. Мысалы: <цифр>:: =0|1|2|3|4|5|6|7|8|9. Бұл ереже элементтерді қарапайым тізбелеу арүылы  (0..9) тілді анықтайды. Бұл грамматикалық ереженің оқылуы 0 не 1 және 2 немесе 9 цифр сәзі. Синтаксистік категория  немесе  терминалды емес сим-р деп аталады. Ол осы синтаксисті  ереже  арүылы анықтайтын тілдің  атаулы үызметін атқарады. Тілдегі байланыстарды құрастыратын символдар терминді символдар деп аталады.

Көбіне :: =  белгісі мына            белгісімен  ауысып тұрады. Әсіресе егер жалғыз әріптер түрінде берілсе, осы символдар пайдаланылуы қажет.   Мысалы, <Х>:: =<B>|<С> мына ереже түрінде Х           B|С жазылуы мүмкін. Терминалды емес символдар  жиынын анықтап болған соқ әлдеқайда  байланыстарды сипаттау үшін оларды пайдалануға болады.

Мысалы:  <шартты оператор>:: = іf <логикалық оператор> then <оператор> else <оператор> іf <логикалық өрнек> then <оператор> шартты оператор құрылымын <логикалық өрнек>  және  <оператор> тер-ді. Келтірілетін ереже шартты оператордың екі нұсқасын шығарады. Әрбір нұсқа итералды және синтаксисті потенциалды  біріктірілуі  түрде анықталады.  Ережеде синтаксисті  категория  көрсетілген жағдайда оның орнына осы категория  арқылы анықталатын тіл символдың кез келген байланысу ережесі болады деген сөз.