«Соңғы автоматтар және формальдік тілдер теориясы»

жүктеу 14,81 Mb.

бет	105/127
Дата	21.05.2018
өлшемі	14,81 Mb.
	#15467

1 ... 101 102 103 104 105 106 107 108 ... 127

Негізгі теориялар
Анықтама 3.2.

Зертханалық жұмыс №3
Дербес автоматтар және олардың минимизациясы

Мазмұны: «Автоматтардың эквиваленттілігі», «минимальді шекті автомат» түсінігін енгізу, детерминантты шекті автоматтарды минимизациялауды дағдыландыруды қалыптастыру.

Мақсаты: - «Соңғы автоматтың жетіспеуі», «Автоматтың эквивалентті күйі», «Соңғы автоматтың минималы» түсініктерін қалыптастыру;

-Соңғы автоматтың детерминирлеген минимизациясын меңгеру.

Негізгі теориялар

Соңғы автоматтың 2-і типі бар: Эквивалентті күй және жетіспеушілік күй.

Анықтама 3.1.Соңғы автоматтын М = (Q, T,F, H, Z) екі q және q^′ әртүрлі күйлер n эквивалентті деп аталады. Егер осылардың бір күйінде орналасып, ω: V_T* , |ω|≤n, символының тізбегіне кірсе. Онда автоматтың соңғы күйлердің біреуіне өтуіне мүмкіндік бар.

Анықтама 3.2.Соңғы автоматтың q күйінің жетіспеуі- егерде автоматтың басты күйінен оған жолы болмауы.

Анықтама 3.3. Эквивалентті және жетіспеу күйі сақталмайтын СА – минималды автомат деп аталады.

Алгоритм 3.1.СА қалыпының жетіспеуі

Кіру: КА М = (Q, T, F, H, Z).

Шығу КА)M^′ = (Q^′, T, F^′, H, Z′).

Қадам1.Соңғы автоматтың бастапқы қалпын Q_д қалып тізіміне орналастыру керек, сонда Qд0=H шығады.

Қадам2.Жаңа элементтер үшін тізімдегі қалыпты толтыру үшін қолданылады.

Қадам 3.2-ші қадамды қайталау, қалыпқа жеткен тізім ауыстырылуы тоқталмағанша , егер Qд ф Q-f сонда i:=i+1, әйтпесе Q_д =Qдi

Қадам4. Q жиынындағы СА қалпын щығару үшін Q_д қалыпқа жеткен . Q^′ = Q ∩ Qд болмайды.

Қадам 5.Соңғы қалыпқа және функция жұбына өтуді шектеу, жеткіліксіз күйді құрайды. Z^′ = Z ) = p|q (Q−Q_д)}.

Мысал 3.1. Жеткіліксіз СА күйін М = (Q, T, F, H, Z), мұндағы Q = {A, B, C, D, E,F,G},T= {a, b}, H= {A},Z= {D, E} және 3.1. кестесінде көрсетілген.

Кесте 3.1 – СА функциясының өтуі.

F	А	В	С	D	Е	F	G
а	В			С	В	D	F
Ь	С	D	Е	Е	D	G	Е

урет 3.1 М соңғы автоматтының шығу графы.

Бірізділік СА жетіспеуі мына түрде:

Q₀={A};

Q₁ = {A,B,C};

Q₂={A,B,C,D,E};

Q₃ = {A, B, C, D, E}; Q₂ = Q₃, онда Q_д = {A, B, C, D, E}.

Q_н={F, G }; Q^′= {A,B, C,D,E}; Z^′= {D,E}.

Функцияның M автоматына өтуі кесте3.2. көрсетілген

Кесте3.2 – Функцияның M автоматына өтуі

F	А	В	С	D	Е
а	В			С	В
Ъ	С	D	Е	Е	D

СА граф M^′ жетіспеу күйі 3.2. суретте көрсетілген.

Суретте СА граф M^′ жетіспеу күйі көрсетілген

жүктеу 14,81 Mb.

Достарыңызбен бөлісу:

1 ... 101 102 103 104 105 106 107 108 ... 127