Маьруза 1 Мавзу: Чекли автоматлар. Режа

Маьруза 8.1

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

Режа:

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

Калит сўзлар

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

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

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

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

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

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

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

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

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