Лекция 12 Тақырыбы: Шекті автоматтарды минимизациялау

Лекция 12

Тақырыбы: Шекті автоматтарды минимизациялау

• 
  Алдымен біз х барлық “қол жетпейтін” (недостижимое ) жағдайлардың барлығын жойып тастаймыз
  
• 
  Сосын орындала алатын (қол жететін ) жағдайлардың барлығын айыра алатын (ұқсас неразличимые) жағдайлардың эквивалентті класстарына бөлеміз эквивалентті автоматтарды анықтай алатындығымызды ескеріп, олардың ең ықшамдысын табу үйрену дұрыс болар еді ең ықшам шекті автоматты табу процесін бейнелеу үшін келесі анықтаманы ендіреміз:
  

Егер қайсыбір W қатары t₁ және t₂ жағдайларын ажырататын болса, t₁=б (q₁,a) және t₂= б (q₂,a), онда aW қатары q₁ және q₂ ажырататыны айқын.

Енді шекті автоматтарды минимизациялау процесін бейнелеуге өтеміз.

Біз барлық “ қол жетпейтін “ жағдайларды тауып және оларды жоюдан бастаймыз. Бұдан соң, біз автоматтың жағдайлар жиынын сондай бөлуді табуымыз керек, сонда әрбір ішкі жиын айрылмайтын жағдайларға ие болсын, яғни егер S және T қайсібір ішкі жиынға тиісті болса, онда барлық а € ∑ үшін б(s,t) және б(t,a )да осы ішкі жиынға тиісті болады.

Бұл үшін жағдайлар жиынын 2 ішкі жиынға бөлеміз: F және S-F. Әрі қарай, әрбір ішкі жиынды жоғарыда көрсетілген шартты орындай отырып әрбір ішкі жиынды бөлуге тырысамыз. Егер жағдайлар жиынын бөле алмайтындай ситуация туындаса, онда бөлу процесін аяқтаймыз.

Нәтижеде S₁, …, S_k жағдайлар жиындарының қайсібір жиынтығын аламыз. S_i - ң әрбірі тек ажыратылмайтын жағдайларға ие болады.

Ең соңында минимизацияланған автоматтың жағдайлар жиынына S_i жиындарының әрқайсысының бір-бір элементінен енгіземіз. Осымен процесс аяқталады.

2. Суретте көрсетілген автоматты минимизациялау процессін қарастырайық. Алдымен, “қол жетпейтін” жағдайларды жоямыз. Біздің жағдайда F-ке “қол жетпейтіні” көрініп тұр, сондықтан ол минимизацияланған автоматқа енбейді. Бұдан соң автоматтың жағдайлар жиынын эквивалент класстарға бөлеміз.

1. 
   E, ABCD
   
2. 
   E,ABC, D, өйткені б(D,b)=E
   
3. 
   E, AC, B, D, өйткені б(B,b)=D
   

О
сылайша А және С жағдайлары ажыратылмайтындар. Сондықтан, келесі автоматты аламыз.

Лекция 13

Тақырыбы: Вирт диаграммасы және шекті автомат арасындағы байланыс

1. 
   Вирт диаграммасы бойынша шекті автоматты құру ережелері
   
2. 
   Шекті автоматты құру мысалы. Вирт диаграммасын
   

1. 
   Шекті автоматты құруды Вирт диаграммасын пайдаланып жүзеге асыру ыңғайлы.
   

эквивалентті әдісі деуге болады. Бұлар бір мезгілде тудыру және тану механизмі болып табылады.

Вирт диаграммасы эквивалентті тек терминалдардан тұратын шекті автомат келесі түрде құрылады.

1. 
   Диаграмманың бастапқы доғасы шекті автоматтың бастапқы
   

2. 
   Диаграмманың соңғы доғасы шекті автоматтың аяқтаушы
   

3. 
   Символдар біріктіретін жекелеген доғалардың шығысы және
   

4. 
   Диаграмманың соңғы жағдайлары шекті автоматтың мүмкін
   

5. 
   Доғалар арасында орналасқан терминал символ сәйкес жағдайлар
   

6. 
   Мүмкін болған жағдайларға өтуді қамтамасыз ететін байланыстар
   

Көрнекілік үшін доғаларда шекті автомат жағдайына сәйкес келетін нүктелер бейнеленген. Олар жағдай нөмерімен көрсетілген. Аяқтаушы жағдай “End” белгісі мен көрсетілген. Ескерте кету керек, диаграммадағы әріп және цивра терминал ретінде қарастырылып отыр, өйткені бұл ұғымдар траслитератиор арқылы қалыптасады.

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

Вирт диаграммасы мен шекті автомат арасындағы бір мәнді және жеңіл түсінікті сәйкестіктің бар болуы шекті автоматты құрып отырмай, Вирт диаграммасының тікелей лексикалық анализатор программасын жазуға кірісуге мүмкіндік береді. Бұл программалау тілдерінің элементтерін формальді бейнелеуді оңайлатады.