Ўзбекистон республикаси алоқА, ахборотлаштириш ва телекоммуникация технологиялари давлат қЎмитаси тошкент ахборот технологиялари университети

16- расм. Чекли детерминирланган автоматнинг ўтишлари
Бундай автоматни детерминирланган деб аталади, чунки ўтишлар жадвалининг ҳар бир элементида битта ҳолат мавжуд. Детерминирланмаган чекли автомат ҳолида эса ушбу шартга амал қилинмайди.
3.Чекли нодетерминирланган автоматлар.
Қуйидаги ҳолат орқали аниқланган чекли автоматни қараймиз:
M₁ = ( К₁, ₁, δ₁ , S₁ , f₁ ).
Бу ерда К₁={A,B} , ₁={1,0}, S₁={A}, f₁={B}
Ўтишлар эса 10- жадвал ва 17- расмда келтирилган.
10-жадвал

Ҳолатлар
Кириш		А	В
	0		{В}
	1	{A,В}	{B}

17- расм. М1 чекли детерминирланмаган автоматнинг ўтишлари.

Биринчи қатор қабул қилинади, чунки қаторни ўқишда охирги ҳолатга элтувчи ўтиш мавжуд (ўтишлар кетма-кетлиги). Худди шундай охирги бўлмаган қаторга ҳам ўтиш мавжуд, лекин бунинг қаторнинг қабул қилинишига аҳамияти йўқ. Шу сабабли, қатор детерминирланмаган чекли автомат томонидан қабул қилинмаслиги мумкин деган хулосага келишдан аввал, барча мавжуд ўтиш имкониятларини кўриб чиқиш зарур.

М2 чекли детерминирланган М1 га мос келувчи ўша тилни қабул қилувчи автомат мавжуд. М2 автоматнинг ўтишлари 11- жадвал ва 18- расмда келтирилган.
M₂ = ( К₂, ₂, δ₂ , S₂ , f₂ ).
Бу ерда К₂={A,B,C} , ₂={1,0}, S₂={A}, f₂={B}
11-жадвал.

Ҳолатлар
Кириш		А	B	C
	0	C	B	C
	1	В	B	C

0. 
   18-расм. М2 детерминирланган чекли автоматнинг ўтишлари.
   

М1 каби М2 қатор хам 0 ва 1 лардан ташкил топган қаторларни қатор 1 дан бошланган ҳолда қабул қилади. Лекин қаторни М2 ёрдамида англашда қайтиш ҳеч қачон талаб этилмайди, чунки аниқ бир кирувчи белгини ўқиш жараёнида ихтиёрий ҳолатдан бошқа ҳолатга аниқ бир ўтиш амалга оширилади. Бу эса М2 дан фойдаланишда қаторни англаш вақти унинг узунлигига пропорционал бўлади.

Лексик таҳлилга мослик шундан иборатки, 3 турдаги ҳар бир тилга детерминирланган чекли автомат мос келиб у ушбу тилни қаторларини англаш вазифасини бажаради. Масалан, G1 грамматикада генерация қилинган ва қуйидаги туғилувчи қоидалар ёрдамида аниқланган қаторлар

А  1А| 1В | 1

В  0В| 1В | 0 | 1

Бу ерда А бошланғич белги бўлиб, М1 ва М2 ёрдамида англанади.
Грамматикани детерминирланмаган чекли М1 автоматдан қуйидагича олинади:

1. 
   Автоматнинг бошланғич ҳолати грамматика гапининг бошланғич белгиси бўлади.
   

2. δ(А,1) =А, δ(В,0)=В
δ(А,1) =В, δ(В,1)=B
ўтишларга қуйидаги туғилувчи қоидалар мос келади:

А  1А| 1В

В  0В| 1В

А ҳолатда 1 ни ўқишда охирги В ҳолатга ўтиш А  1 га мос келади ва аналогик равишда В  0 | 1
Худди шундай, грамматикадан М1 автоматни келтириб чиқариш мумкин.