Маъруза Мавзу: Компилятор-Чекли автоматлар. Режа

Маъруза

• Мавзу: Компилятор-Чекли автоматлар.

Режа:

• Чекли автоматлар.
• Чекли детерминирланган автоматлар.
• Чекли нодетерминирланган автоматлар.

Калит сўзлар

• Чекли автомат
• Холатларнинг чекли тўплами
• Чекли кириш алфавити
• Ўтишлар тўплами
• Бошланғич холат
• Охирги холатлар тўплами
• Детерминирланган автомат
• Нодетерминирланган автомат

Чекли автоматлар.

• Чекли автомат - бу қандайдир тилнинг қаторларини англаш учун қурилмадир. Унинг таркибида чекли холатлар тўплами бор бўлиб, уларнинг баъзилари охиргилари деб аталади. Хар бир литернинг ўкилиши давомида назорат қатори холатдан холатга берилган ўтишлар тўпламига мос равишда узатилади. Агар қаторнинг охирги литерасини ўкиганидан сўнг автомат охирги холатлардан бирида бўлса, катор хакида - ушбу автомат билан қабул қилинадиган тилга тегишли - деб айтилади. Бошқа холларда қатор автомат билан қабул килинадиган тилга тегишли эмас деб айтилади.

Чекли автоматлар.

• Чекли автомат формал равишда қуйидаги бешта характеристика билан аниқланади:
• M = ( К, ∑, δ , S0 , f ).
• - (К) холатларнинг чекли тўплами
• - (∑ ) чекли кириш алфавити
• - (δ ) ўтишлар тўплами
• - (S0 К ) бошланғич ҳолат
• - ( f К) охирги ҳолатлар тўплами

Чекли автоматлар.

• Мисол: Автоматнинг ҳолатлари А ва В, кирувчи алфавит {0,1}, бошланғич холати –А , охирги ҳолатлар тўплами -{А}, ўтишлар
• (А,0) = А, (В,0)=В
• (А,1) = В, (В,1)=А
• Бу ўтишлар А ҳолатда 0 ни ўқишда бошқарув А ҳолатга узатилишини англатади, 1 ни ўқишда бошқарув В ҳолатга узатилишини англатади ва х.к. 01001011 қаторни ўқишда бошқарув кетма-кет равишда қуйидаги тартибда узатилади: А,А,В,В,В,А,А,В,А

А сўнгги ҳолат бўлгани учун қатор чекли автомат томонидан қабул қилинади, лекин 00111 қаторни ўқишда автомат қуйидаги ҳолатлар орқали ўтади А,А,А,В,А,В

• А сўнгги ҳолат бўлгани учун қатор чекли автомат томонидан қабул қилинади, лекин 00111 қаторни ўқишда автомат қуйидаги ҳолатлар орқали ўтади А,А,А,В,А,В
• В охирги ҳолат бўлмаганлиги сабабли, бу литер(қатор) қабул қилинмайди, яъни бу қатор ушбу автомат қабул қиладиган тилга тегишли эмас.