Лекция 6 Таќырыбы: Мили және Мур автоматтары

Лекция 6

Таќырыбы: Мили және Мур автоматтары

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

Шығу функцияларының түріне қарай Мили және Мур автоматтары деп ажыратылады.

   Q – жағдайлардың шекті жиыны;

    E – енуші сигналдардың шекті жиыны (енуші алфавит)

    Y – шығушы сигналдардың шекті жиыны (шығушы алфавит)

    δ: Q×E→Q – ауысу функциялары

және абстрактілі T = {0, 1, 2, …} уақыттағы Q, E, Y жиындары элементтерінің арасында мынадай байланыс бар:

q(t+1)= δ(q(t),e(t)),

y(t) = λ(q(t),x(t)), tєT

(Отображения δ и λ получили названия, соответственно функции переходов и функции выходов автомата A).

Мили автоматының ерекшелігі шығару функциясы екі аргументті болып табылады және е(t) енуші каналда символ болған жағдайда ғана y(t) шығу каналында символ пайда болады.

Шығушы сигналдың тек жағдайға ғана тәуелді болуы Мур типіндегі автоматтарға тән. Мур автоматында шығару функциясы шығушы символ мәнін тек бір ғана аргумент – автомат жағдайына қарап анықтайды.

Мур типті детерминант шекті автомат деп мына алтылықты айтамыз: A=(Q, E, Y, q₀, δ, μ)

мұндағы Q, E, Y, q₀, δ — Мили типіндегі автомат анықтамасына сәйкес келеді, ал μ

түріндегі бейнелеу болып табылады және уақыт ішіндегі жағдайлар мен шығушы сигналдардың тәуелділігі мына теңдікпен беріледі:

Мур автоматының ерекшелігі мынада: автомат q(t) жағдайында тұрған уақыт аралығының барлығында шығу каналында y(t) символы бар болады.

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

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

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

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

- q₀^’=q₀

- F^’=

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

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

Лекция 7.

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

1. Шекті автоматтардың эквиваленттілігі

2. Мур теоремасы

3. Жағдайлар жиынын эквивалент класстарға бөлетін алгоритм

1. АНЫҚТАМА. екі автоматты эквивалентті деп аталады, егер олар ∑ алфавиті үстіндегі бір, және сол бір тілді ғана танитын болса.

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

орындалса.

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

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

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

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

2. Мур теоремасы

Мур теоремасы ( файл-конечные автоматы1)
Енуші алфавиттері бірдей екі шекті автомат A = а, E_а, Y_а, q_0а, δ_а λ_а > және В = < Q_b, E_b, Y_b, q_0b, δ_b, λ_b s0в, δdв, vв> эквивалентті деп аталады егер с одинаковым входным алфавитом являются эквивалентными тогда и только тогда, когда для любого достижимого состояния (sa, sb) в их прямом произведении справедливо: для любого сигнала х из Х, va(sa, x) = vb(sb, x).

b/(1,1)


Ya b/(1,0) b/(1,0)

X b/(1,1) a/(0,0)
a/(0,0)

Yb
b/(0,1) a/(0,0) a/(0,0)

a/(0,0) b/(0,0) a/(0,0)


Произведение получено на примере двух автоматов А и В, изображенных выше.
В этом автомате (произведение) есть недостижимые состояния (см. определение). Если их выбросить, то получим


b/(1,1) a/(0,0)


b/(1,1) a/(0,0) a/(0,0)

b/(0,0)

3. Жағдайлар жиынын эквивалент класстарға бөлетін алгоритм

Жағдайлар жиынын эквивалентті класстарға бөлінетін алгоритімді жазамыз:

(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₂ жиынын эквивалентті жағдайлар жиынынан бөліп тастаймыз. Енді бұл жиындардың ешқайсысыда аяқтаушы және аяқтаушы емес жағдайларға ие еместігін тексеру қалды.