Составители:
34
Òàêèì îáðàçîì, ñîîòíîøåíèÿ (4.1) è (4.2) äåéñòâèòåëüíî îïðåäåëÿ-
þò îïåðàòîð ϕ
A
àâòîìàòà A.
Ôóíêöèè ïåðåõîäîâ è âûõîäîâ ïðåäñòàâëÿþòñÿ îáû÷íî àáñòðàêòíû-
ìè ÷àñòè÷íûìè ôóíêöèÿìè δ(a, z) è λ(a, z), çàäàþùèìè îäíîçíà÷íîå
îòîáðàæåíèå íåêîòîðîãî ìíîæåñòâà ïàð (a, z)(a∈A, z∈Z) â ìíîæåñòâà
A è W ñîîòâåòñòâåííî. Äîïóñòèìûìè âõîäíûìè ñëîâàìè äëÿ àâòîìàòà
A íàçûâàþò òå è òîëüêî òå âõîäíûå ñëîâà p, íà êîòîðûõ ñ ïîìîùüþ
ôóíêöèé δ è λ óêàçàííûì âûøå ñïîñîáîì ìîæíî îïðåäåëèòü ñîîòâåò-
ñòâóþùèå èì âûõîäíûå ñëîâà q = ϕ
A
(p).
Àâòîìàò íàçûâàþò êîíå÷íûì, åñëè êîíå÷íû âñå òðè îïðåäåëÿþùèå
åãî ìíîæåñòâà Z, W, A.
Äëÿ ïðèìåðà ñ ëèôòîì ôóíêöèè ïåðåõîäîâ è âûõîäîâ îïðåäåëÿþòñÿ
ñîîòâåòñòâåííî ñëåäóþùèìè ðàâåíñòâàìè:
a(t) = z(t),
w(t) = z(t)a(t1).
Àâòîìàò óïðàâëåíèÿ ëèôòîì êîíå÷åí, õîòÿ îáëàñòü îïðåäåëåíèÿ åãî
îïåðàòîðà ñîñòîèò èç áåñêîíå÷íîãî ìíîæåñòâà äîïóñòèìûõ ñëîâ.
Ïîñêîëüêó äàëüøå áóäóò ðàññìàòðèâàòüñÿ òîëüêî êîíå÷íûå àâòîìà-
òû, ñëîâî êîíå÷íûé áóäåò îïóñêàòüñÿ.
Àâòîìàò íàçûâàþò âïîëíå îïðåäåëåííûì, åñëè åãî ôóíêöèè ïåðåõî-
äîâ è âûõîäîâ çàäàíû íà âñåõ ïàðàõ (a, z), è ÷àñòè÷íûì â ïðîòèâíîì
ñëó÷àå.
Äâà àáñòðàêòíûõ àâòîìàòà ñ÷èòàþòñÿ îäèíàêîâûìè, åñëè îíè îòëè-
÷àþòñÿ äðóã îò äðóãà ëèøü îáîçíà÷åíèÿìè âõîäíûõ è âûõîäíûõ ñèãíà-
ëîâ, ñîñòîÿíèé.
4.3. Ñïîñîáû çàäàíèÿ àáñòðàêòíûõ àâòîìàòîâ
Åñëè çàäàíû âõîäíîé è âûõîäíîé àëôàâèòû àâòîìàòà, à òàêæå ìíî-
æåñòâî åãî ñîñòîÿíèé, ñðåäè êîòîðûõ ôèêñèðîâàíî íà÷àëüíîå ñîñòîÿ-
íèå a
0
, äëÿ çàäàíèÿ àáñòðàêòíîãî àâòîìàòà îñòàåòñÿ çàäàòü ôóíêöèþ
ïåðåõîäîâ δ ôóíêöèþ âûõîäîâ A .
Àâòîìàòû, ôóíêöèè ïåðåõîäîâ è âûõîäîâ êîòîðûõ óäîâëåòâîðÿþò
óñëîâèÿì (4.1), (4.2), íàçûâàþò àâòîìàòàìè Ìèëè. Àâòîìàòû, ó êîòî-
ðûõ ôóíêöèè ïåðåõîäîâ è âûõîäîâ óäîâëåòâîðÿþò óñëîâèÿì
a(t) = δ(a(t1), z(t)), (4.3)
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
