Лекция 10 Тақырыбы: Детерминирлі, детерминирлі емес шекті автоматтар

Лекция 10

Тақырыбы: Детерминирлі, детерминирлі емес шекті автоматтар

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

ША = (Q,, , q_a F)

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

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

1. БНФ формасында берілген жєне ДША т‰рінде берілген идентификатор ±ѓымын ќарастырайыќ

:

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

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

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

2. Арифметикалық өрнек (жақшасыз)

: : =/<идент>: :=: :=+\ -\ *\ / : <цфр>: :=<цфр>

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

Бұл теорема М^’детерминерлі автоматын құрудың жалпы алгоритімін көрсету жолмен дәлелденеді. Бұл жалпы алгоритм М тілін де анықтайды.

Айталық М=(Q, q₀,F) онда біз М^’=(Q^’,,^’,q₀^’,F^’)былайша анықтаймыз :

- Q^’ M автоматының жағдайлар жиынымен сәйкес келеді.

- q₀^’=q₀

- F^’=

- барлық үшін, мұнда да қайсыбір үшін р бар болады}.

М^’-ң М беретін тілі беретінін көрсетуге болады. Осылайша, детерминерлі және детерминерлі емес шекті автоматтар мен берілетін тілдер класы толық сәйкес келеді. Детерминерлі шекті автоматтар ыңғайлы болғандықтан,тек соларды қарастыратын боламыз.

Лекция 11

Тақырыбы: Шекті автоматтардың эквиваленттілігі.

АНЫҚТАМА. екі жағдай эквивалентті деп аталады, егер үшін

Егер екі жағдай эквивалентті болатын болса үшін жағдайларыда эквивалентті болатыны айқын.

Бұдан бөлек детерминирлігі шекті автоматта б(q,e) ауысуы тек шекті q жағдайы үшін туындауы мүмкін болғандықтан, ешқандай соңғы айақтаушы жағдай. Аяқтаушы емес жағдайға эквивалент бола алмайды.

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

Егер осындай жұптардың біріне аяқтаушы жағдаймен аяқтаушы емес жағдай түсіп қалатын болса онда эквивалентті емес.
2. Жағдайлар жиынын эквивалентті класстарға бөлінетін алгоритімді жазамыз:

(q₁₀,q₂₀) тізімге ендіру ;

тізім =0; (*эквивалентті жиындар жиыны *)

for each(q in Q₁+Q₂) {{S} ті Тізімге қосу;}

While (тізімге өттетін (q_i,q_j) жұбы бар )

(q_i,q_j) жұбын тізімдерінен жою ;

Айталық, А және А¹ болатындай жиындар.

If (A!=A^')

{A=A+A^' ;

for (a frov ∑) {( бq_i,a), бq_j,a),)-ны

тізімге қосу;

Осылайша, егер q₁₀,q₂₀ эквивалентті болатын болса Q₁U Q₂ жиынын эквивалентті жағдайлар жиынынан бөліп тастаймыз. Енді бұл жиындардың ешқайсысыда аяқтаушы және аяқтаушы емес жағдайларға ие еместігін тексеру қалды.