1610906281-ae38486ec859a3a9dcd398b8f34f26aa (Лекции конечные автоматы Морозов)

ËÅÊÖÈÈ ÏÎ ÊÎÍÅ×ÍÛÌÀÂÒÎÌÀÒÀÌ È ÀÂÒÎÌÀÒÍÛÌÑÒÐÓÊÒÓÐÀÌ [ÐÀÁÎ×ÈÉÂÀÐÈÀÍÒ]À.Ñ.Ìîðîçîâ2 îêòÿáðÿ 2017 ã.2ÏðåäèñëîâèåÏîñîáèå ñîäåðæèò ðàñøèðåííîå èçëîæåíèå êóðñà, ïðî÷èòàííîãî àâòîðîìïî ïðèãëàøåíèþ â àïðåëå 2014 ãîäà â Åâðàçèéñêîì íàöèîíàëüíîì óíèâåðñèòåòå èì Ë.Í.Ãóìèë¼âà â ã. Àñòàíå (Êàçàõñòàí).Òåîðèÿ êîíå÷íûõ àâòîìàòîâ íàñòîëüêî êðàñèâà è ïðèâëåêàòåëüíà, ÷òîïîñëå ïðî÷òåíèÿ êóðñà ëåêöèé ìíå, êàê è ìíîãèì äðóãèì, áûëî òðóäíîóäåðæàòüñÿ îò îôîðìëåíèÿ èõ â âèäå ïîñîáèÿ.Íàäåþñü, ÷òî îïðàâäàòü ìî¼ ãðàôîìàíñòâî ìîæåò ÷óòü áîëåå àëãåáðîëîãè÷åñêèé ñòèëü èçëîæåíèÿ ìàòåðèàëà, à òàêæå äîáàâëåíèå íîâîé òåìûîá àâòîìàòíûõ ñòðóêòóðàõ.À.Ñ.ÌîðîçîâÍîâîñèáèðñê, Àêàäåìãîðîäîê, 21 ìàÿ 2014 ã.34ÎãëàâëåíèåÏðåäèñëîâèå31Ââåäåíèå72Àâòîìàòíûå ÿçûêè132.1Îñíîâíûå îïðåäåëåíèÿ.

. . . . . . . . . . . . . . . . . . . .132.2Ëåììà î íàêà÷èâàíèè . . . . . . . . . . . . . . . . . . . . . .212.3Íåäåòåðìèíèðîâàííûå àâòîìàòû . . . . . . . . . . . . . . . .252.4Îïåðàöèè íàä àâòîìàòíûìè ÿçûêàìè . . . . . . . . . . . . .322.5Ïîðîæäåíèå àâòîìàòíûõ ÿçûêîâ: ðåãóëÿðíûå âûðàæåíèÿ.342.6Àëãîðèòìè÷åñêàÿ ðàçðåøèìîñòü íåêîòîðûõ ñâîéñòâ. .

. .382.7Ïîðîæäåíèå àâòîìàòíûõ ÿçûêîâ ñ ïîìîùüþ ôîðìàëüíûõãðàììàòèê. . . . . . . . . . . . . . . . . . . . . . . . . . . .2.8Ãîìîìîðôèçìû ÿçûêîâ2.9Îïòèìèçàöèÿ àâòîìàòîâ46. . . . . . . . . . . . . . . . . . . .492.10 Òåîðåìà ÌàéõèëëàÍåðîóäà341. .

. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .Àâòîìàòíûå ñòðóêòóðû58613.1Êîíâîëþöèè è îïðåäåëåíèå àâòîìàòíûõ ìîäåëåé3.2Ñâîéñòâà êîíâîëþöèé è çàìå÷àòåëüíûå ñâîéñòâà àâòîìàò-. . . . . .íûõ ñòðóêòóð . . . . . . . . . . . . . . . . . . . . . . . . . . .62653.3Äåêàðòîâû ïðîèçâåäåíèÿ àâòîìàòíûõ ñòðóêòóð . . . . .

. .723.4Ôàêòîðû àâòîìàòíûõ ñòðóêòóð74Ïðåäìåòíûé óêàçàòåëü. . . . . . . . . . . . . . . .7656ÎãëàâëåíèåÃëàâà 1ÂâåäåíèåÍàðÿäó ñ îáùèì ïîíÿòèåì âû÷èñëèìîñòè, â òåîðèè àëãîðèòìîâ èçó÷àþòñÿ òàêæå íåêîòîðûå îãðàíè÷åííûå ìîäåëè âû÷èñëèìîñòè, ïðèâîäÿùèå êêëàññàì àëãîðèòìîâ, êîòîðûõ óæå íåäîñòàòî÷íî äëÿ ïîëó÷åíèÿ âñåõ âû÷èñëèìûõ ôóíêöèé, íî êîòîðûå òåì íå ìåíåå îáëàäàþò ðÿäîì äðóãèõ õîðîøèõ ñâîéñòâ. Îäíîé èç òàêèõ ìîäåëåé ÿâëÿþòñÿ êîíå÷íûå àâòîìàòû.Âîçìîæíîñòè êîíå÷íûõ àâòîìàòîâ âåñüìà îãðàíè÷åíû, íî çàòî ìíîãèååñòåñòâåííûå è âàæíûå âîïðîñû äëÿ íèõ àëãîðèòìè÷åñêè ðàçðåøèìû.Òàê, íàïðèìåð, õîðîøî èçâåñòíî, ÷òî íå ñóùåñòâóåò àëãîðèòìà, ïîçâîëÿþùåãî ïî äâóì ïðîãðàììàì (àëãîðèòìàì) âûÿñíÿòü, çàäàþò ëè îíè îäíóè òó æå ôóíêöèþ, â òî âðåìÿ êàê îòâåò íà ñõîäíûé âîïðîñ äëÿ êîíå÷íûõàâòîìàòîâ, à èìåííî, ðàñïîçíàþò ëè äâà êîíå÷íûõ àâòîìàòà îäíî è òîæå ìíîæåñòâî ñëîâ, óæå ìîæíî ïîëó÷àòü ñ ïîìîùüþ åäèíîãî àëãîðèòìà.Êîíå÷íûå àâòîìàòû íàõîäÿò øèðîêîå ïðèìåíåíèå, íàïðèìåð, â ïðàêòè÷åñêîì è òåîðåòè÷åñêîì ïðîãðàììèðîâàíèè, ìîäåëèðîâàíèè ïðîèçâîäñòâåííûõ è òåõíîëîãè÷åñêèõ ïðîöåññîâ.

Êëàññ àëãîðèòìîâ, çàäàâàåìûõêîíå÷íûìè àâòîìàòàìè, íå òàê äàâíî ñòàë èñïîëüçîâàòüñÿ ïðè èçó÷åíèèòàê íàçûâàåìûõ àâòîìàòíûõ ñòðóêòóð. Ýòî íàïðàâëåíèå â ìàòåìàòè÷åñêîé ëîãèêå ÿâëÿåòñÿ ÷àñòüþ íàïðàâëåíèÿ ïî èçó÷åíèþ òàê íàçûâàåìûõêîíñòðóêòèâíûõ èëè âû÷èñëèìûõ ñòðóêòóð òàêèõ ñòðóêòóð, êîòîðûåâ ïðèíöèïå ìîãóò áûòü ðåàëèçîâàíû íà êîìïüþòåðå â âèäå àáñòðàêòíûõòèïîâ äàííûõ. Àâòîìàòíûå ñòðóêòóðû, â îòëè÷èå îò êîíñòðóêòèâíûõ,ïðåäïîëàãàþò èñïîëüçîâàíèå áîëåå ïðîñòûõ àëãîðèòìîâ, è èìåþò ãîðàçäî áîëüøå øàíñîâ áûòü ðåàëèçîâàííûìè íà ðåàëüíûõ êîìïüþòåðàõ.Ìû ïðåäïîëàãàåì, ÷òî ÷èòàòåëü ñâîáîäíî âëàäååò îñíîâíûìè òåîðåòèêîìíîæåñòâåííûìè ïîíÿòèÿìè òèïà ôóíêöèÿ, óïîðÿäî÷åííàÿ ïàðà,7Ãëàâà 1. Ââåäåíèå8äåêàðòîâî ïðîèçâåäåíèå è ò.ï., à òàêæå èìååò ïðåäñòàâëåíèå îá àëãåáðàè÷åñêèõ ñòðóêòóðàõ.Âðåìÿ îò âðåìåíè âñòðå÷àþùååñÿ â òåêñòå ïîíÿòèå àëãîðèòìà ðàññìàòðèâàåòñÿ çäåñü èñêëþ÷èòåëüíî íà èíòóèòèâíîì óðîâíå, õîòÿ è âñåóïîìèíàåìûå çäåñü àëãîðèòìû ìîæíî ïðåäñòàâèòü è ðàññìîòðåòü â ëþáîé èç èçâåñòíûõ ïîëíûõ ôîðìàëèçàöèé, òàêèõ, êàê, íàïðèìåð, ÷àñòè÷íîðåêóðñèâíåû ôóíêöèè, ìàøèíû Òüþðèíãà, íîðìàëüíûå àëãîðèòìû Ìàðêîâà è ò.ä.Êàê îáû÷íî, ÷åðåç÷èñåë.1ÏîäN ìû îáîçíà÷àåì ìíîæåñòâî âñåõ íàòóðàëüíûõàëôàâèòîì ìû áóäåì ïîíèìàòü ëþáîå êîíå÷íîå ìíîæåñòâî.Åãî ýëåìåíòû ìû áóäåì îáû÷íî íàçûâàòü ñèìâîëàìè èëè áóêâàìè.

Âîâñåíå îáÿçàòåëüíî ñ÷èòàòü, ÷òî ñèìâîëû äîëæíû áûòü ïîõîæèìè íà îáû÷íûå áóêâû èëè öèôðû êàêîãîëèáî åñòåñòâåííîãî ÿçûêà. Êîãäà ýòî áóäåò íàì óäîáíî, ìû áóäåì äîïóñêàòü ðàññìîòðåíèå â êà÷åñòâå ñèìâîëîâòàêæå îáúåêòîâ âèäà, íàïðèìåð10èýòîòîæåìîæåòáûòüñèìâîëîìàëôàâèòà,è ò.ï.ñëîâîì íàä àëôàâèòîì A ìû áóäåì ïîíèìàòü ëþáîå îòîáðàæåíèåèç ìíîæåñòâà âèäà {0, .

. . , k − 1}, k ∈ N â A. Ìíîæåñòâî âñåõ ñëîâ íàä∗àëôàâèòîì A áóäåì îáîçíà÷àòü ÷åðåç A . Ìû íå èñêëþ÷àåì èç ðàññìîòÏîäðåíèÿ òàêæå ñëîâà, ÿâëÿþùåõñÿ îòîáðàæåíèÿìè èç ïóñòîãî ìíîæåñòâà(ñîîòâåòñòâþùåãî ñëó÷àþk = 0).Òàêîå ñëîâî ñ òî÷êè çðåíèÿ òåîðèèìíîæåñòâ åäèíñòâåííî, è îíî íàçûâàåòñÿäåò îáîçíà÷àòüñÿ ÷åðåçïóñòûì ñëîâîì.Çäåñü îíî áó-Λ. Ìû áóäåì èçîáðàæàòü ñëîâà â ïðèâû÷íîì íàìâèäå ïðîñòûì ïåðå÷èñëåíèåì âñåõ çíà÷åíèé îòîáðàæåíèé, êîòîðûìè îíèÿâëÿþòñÿ, â ïîðÿäêå âîçðàñòàíèÿ àðãóìåíòà, íàïðèìåð,abbaDGVBFDSèíîãäàñëîâàïîëó÷àþòñÿîîîî÷åíüäëèííûìè.k èç îïðåäåëåíèÿ ñëîâà íàçûâàåòñÿ äëèíîé ýòîãî ñëîâà.

Äëèw îáîçíà÷àåòñÿ ÷åðåç |w|. Òàê, íàïðèìåð, |abba| = 4, |Λ| = 0,|ìàòåìàòèêà| = 10.Áóäåì ãîâîðèòü, ÷òî ñëîâî w ñîäåðæèò áóêâó a, åñëè îíà âñòðå÷à×èñëîíà ñëîâàåòñÿ â èçîáðàæåíèè ýòîãî ñëîâà â âèäå ñòðîêè (áîëåå ôîðìàëüíî, åñëè1 Çäåñüìû ñ÷èòàåì0íàòóðàëüíûì ÷èñëîì.9aïðèíàäëåæèò îáëàñòè çíà÷åíèé ñëîâàw).Ïóñòîå ñëîâî íå ñîäåðæèòáóêâ.Íà ñëîâàõ îáû÷íî ðàññìàòðèâàþò ñëåäóþùèå äâå îñíîâíûå îïåðàöèè:Êîíàêòåíàöèÿ.Êîíêàòåíàöèåé ñëîâ α è βíàçîâ¼ì ñëîâîò.å., ïðèìåíåíèå îïåðàöèè êîíêàòåíàöèè ê ñëîâàìαèα · β = αβ ,β ñîñòîèò âïðèïèñûâàíèè âòîðîãî ñëîâà ñðàçó ïîñëå ïåðâîãî, è ðåçóëüòàòîìîïåðàöèè áóäåò ïîëó÷åííîå ñëîâî.

Êàê ïðàâèëî, òî÷êó çíàê êîí-α·βαβ . Ïðèìåðû:êîíêàòåíàöèÿ ñëîâ àâòî è ìàò áóäåò ñëîâî àâòîìàò. Îïåðàöèÿêîíêàòåíàöèè àññîöèàòèâíà: äëÿ ëþáûõ ñëîâ α, β è γ âûïîëíåíî ðàâåíñòâî α(βγ) = (αβ)γ .  ñèëó àññîöèàòèâíîñòè êîíêàòåíàöèè â ïîêàòåíàöèè îïóñêàþò, è âìåñòîïèøóò ïðîñòîäîáíûõ çàïèñÿõ ñêîáêè ïðîñòî îïóñêàþò. Êîììóòàòèâíîñòü, ò.å., ðàâåíñòâî6= ba.αβ = βα,a 6= b, òî abΛw = wΛ = w.âûïîëíåíà íå âñåãäà, íàïðèìåð, åñëèÎ÷åâèäíî, ÷òî äëÿ ëþáîãî ñëîâàÑòåïåíü ñëîâà. Äëÿ êàæäîãîn∈Nwâûïîëíåíîè ëþáîãî ñëîâàwîïðåäåëåíî ñëînâî, íàçûâàåìîå né ñòåïåíüþ ñëîâà w , îáîçíà÷àåìîå ÷åðåç w , êîòîðîå åñòü ðåçóëüòàò êîíêàòåíàöèè ñëîâàëè÷åñòâånðàç. Ïðè ýòîì ñ÷èòàåòñÿ, ÷òîîïðåäåëèòü ñòåïåíè ñëîâàww ñ ñàìèì ñîáîé â êîw0 = Λ.

Ìîæíî òàêæåïî èíäóêöèè:w0 = Λwn+1 = wn w.Äëÿ ëþáûõm, n ∈ N,î÷åâèäíî, âûïîëíåíîam an = am+n .íà÷àëüíûé ñåãìåíò ñëîâà β , åñëèäëÿ íåêîòîðîãî ñëîâà γ âûïîëíåíî αγ = β . Äâîéñòâåííûì îáðàçîì îïðåäåëÿåòñÿ è ïîíÿòèå êîíöåâîãî ñåãìåíòà: ñëîâî α åñòü êîíöåâîé ñåãìåíòñëîâà β , åñëè äëÿ íåêîòîðîãî ñëîâà γ âûïîëíåíî γα = β .Ñëîâî α íàçûâàåòñÿ ïîäñëîâîì ñëîâà β , åñëè íàéäóòñÿ òàêèå ñëîâà δ0è δ1 , ÷òî β = δ0 αδ1 .Ëþáîå ìíîæåñòâî ñëîâ äàííîãî àëôàâèòà íàçûâàþò ÿçûêîì íàä ýòèì∗àëôàâèòîì, ò.å., ÿçûê íàä A ýòî ëþáîå ïîäìíîæåñòâî â A . Çàìåòèì,Áóäåì ãîâîðèòü, ÷òî ñëîâîαåñòü÷òî îäèí è òîò æå ÿçûê ìîæíî ðàññìàòðèâàòü êàê ÿçûê íàä ðàçíûìèàëôàâèòàìè.

Òàê ïóñòîå ìíîæåñòâî ÿâëÿåòñÿ ÿçûêîì íàä ëþáûì àëôàâèòîì, âñå ïðàâèëüíî ïîñòðîåííûå ïðîãðàììû â ëþáîì ñóùåñòâóþùåìÿçûêå ïðîãðàììèðîâàíèÿ (åñëè ñ÷èòàòü ïðîáåëû è ïåðåõîä íà äðóãóþÃëàâà 1. Ââåäåíèå10ñòðîêó òàêæå ñèìâîëàìè) îáðàçóþò ÿçûê. Ëþáîé åñòåñòâåííûé ÿçûê âíàøåì ïîíèìàíèè ìîæíî ðàññìàòðèâàòü, êàê ÿçûê, åñëè ìû çàôèêñèðóåì ìíîæåñòâî åãî ñëîâ, íàïðèìåð, ñîñòàâèâ åãî ïîëíûé ñëîâàðü.Íàä ÿçûêàìè îáû÷íî ðàññìàòðèâàþò ñëåäóþùèå îïåðàöèè:Ïåðåñå÷åíèå, îáúåäèíåíèå, ðàçíîñòü. Ýòè îïåðàöèè ïîíèìàþòñÿ èîáîçíà÷àþòñÿ òî÷íî òàê æå, êàê ñîîòâåòñòâóþùèå îïåðàöèè íàä{ab, bb} è {bb, ba} áó{ab, bb, ba}, à ðàçíîñòüþ ìíîæåñòâàìè, íàïðèìåð, ïåðåñå÷åíèåì ÿçûêîâ{bb},{ab}.äåò ÿçûêÿçûêèõ îáúåäèíåíèåì ÿçûêÄîïîëíåíèå.

Âñÿêèé ðàç, êîãäà ìû ãîâîðèì î äîïîëíåíèè ÿçûêà, ìûïðåäïîëàãàåì, ÷òî àëôàâèò, íàä êîòîðûì ðàññìàòðèâàåòñÿ äàííûéA òàêîé àëôàâèò, èL ÿçûê íàä ýòèì àëôàâèòîì, òî äîïîëíåíèåì ÿçûêà L ñ÷èòàåòñÿ∗ÿçûê A \ L. Äîïîëíåíèå ÿçûêà L îáîçíà÷àåòñÿ L.ÿçûê, ÿâíî èëè íåÿâíî çàôèêñèðîâàí. ÅñëèÊîíêàòíåíàöèÿ. Ïîäêîíêàòåíàöèåé ÿçûêîâ L0èL1áóäåì ïîíèìàòüÿçûêL0 · L1 = {w0 w1 | wo ∈ L0 , w1 ∈ L1 }.Êàê è â ñëó÷àå êîíêàòåíàöèè ñëîâ, òî÷êó â êà÷åñòâå ñèìâîëà êîíêàòåíàöèè îáû÷íî îïóñêàþò. Î÷åâèäíî, ÷òî∅L = L∅ = ∅,è{Λ}L = L{Λ} = L.Çâ¼çäî÷êà Êëèíè (èíîãäà íàçûâàåìàÿ ïðîñòî ¾çâ¼çäî÷êà¿).

ÅñëèL ÿçûê, òî çâ¼çäî÷êà Êëèíè îò ýòîãî ÿçûêà, îáîçíà÷àåìàÿL∗ ,îïðåäåëÿåòñÿ, êàê âñåâîçìîæíûå êîíå÷íûå êîíêàòåíàöèè ñëîâ èçýòîãî ÿçûêà, âêëþ÷àÿ òàêæå è ïóñòóþ êîíêàòåíàöèþ:L∗ = {w0 . . . wk−1 | k ∈ N, w0 , . . . , wk−1 ∈ L}.Çàìåòèì, ÷òî âñåãäà âûïîëíåíî ñâîéñòâîΛ ∈ L∗ . Çàñëóæèâàåò âíè-ìàíèÿ ðàâåíñòâî∅∗ = {Λ}∗ = {Λ}.Ëåãêî ïðîâåðÿþòñÿ ñëåäóþùèå ñâîéñòâà:1.L0 ⊆ L12.L ⊆ L∗ ,âëå÷¼òL∗0 ⊆ L∗1 ,113.(L∗ )∗ = L∗ .w ∈ L∗ , òî ñóùåñòâóåò∗òàêîå, ÷òî w ∈ L0 .4. åñëèêîíå÷íîå ïîäìíîæåñòâîL0 ⊆ LÓïðàæíåíèÿ.1. Äîêàçàòü, ÷òî äëÿ ëþáûõ ÿçûêîâ âûïîëíåíî A(BC) = (AB)C .2.

Äîêàçàòü, ÷òî äëÿ ëþáîãî ÿçûêà L âûïîëíåíî L∗L∗ = L∗.3. Äîêàçàòü, ÷òî äëÿ ëþáîãî ÿçûêà L âûïîëíåíîL∗ L ∪ {Λ} = L∗ = LL∗ ∪ {Λ}.4. Äîêàçàòü ðàâåíñòâî: A(B ∪ C) = AB ∪ AC .5. Äîêàçàòü âêëþ÷åíèå: A(B ∩ C) ⊆ AB ∩ AC .6. Ïðèâåñòè ïðèìåð ÿçûêîâ A, B, C , äëÿ êîòîðûõ âêëþ÷åíèå AB ∩ AC ⊆A(B ∩ C) íå âûïîëíåíî.7. Äîêàçàòü âêëþ÷åíèå: (A ∪ B)∗ ⊇ A∗ ∪ B ∗.8. Ïðèâåñòè ïðèìåð ÿçûêîâ A è B , äëÿ êîòîðûõ âêëþ÷åíèå A∗ ∪ B ∗ ⊇(A ∪ B)∗ íå âûïîëíåíî.9. Êàêèå èç âêëþ÷åíèé (A ∩ B)∗ ⊆ A∗ ∩ B ∗, A∗ ∩ B ∗ ⊆ (A ∩ B)∗ èñòèííûäëÿ ëþáûõ ÿçûêîâ A è B , à êàêèå íåò?10. Ïóñòü A íåêîòîðûé àëôàâèò, è u, v ∈ A∗. Äîêàçàòü, ÷òî uA∗ ∩ vA∗ 6= ∅ýêâèâàëåíòíî òîìó, ÷òî õîòÿ áû îäíî èç ñëîâ u, v ÿâëÿåòñÿ íà÷àëüíûìñåãìåíòîì äðóãîãî.12Ãëàâà 1.

ÂâåäåíèåÃëàâà 2Àâòîìàòíûå ÿçûêè2.1Îñíîâíûå îïðåäåëåíèÿÑóùåñòâóåò ðÿä ïðîöåññîâ, êîòîðûå ìîæíî ïðåäñòàâèòü ñåáå ñëåäóþùèìîáðàçîì: â êàæäûé ìîìåíò âðåìåíè îáúåêò íàõîäèòñÿ â îäíîì èç òàêíàçûâàåìûõñîñòîÿíèé(íàïðèìåð, ïðî êîìïüþòåð ìîæíî ñêàçàòü, ÷òîîí âûêëþ÷åí, âêëþ÷¼í è ðàáîòàåò, çàâèñ èëè âûïîëíÿåò ïðîãðàììó), èâ ðåçóëüòàòå âíåøíåãî âîçäåéñòâèÿ îáúåêò ïåðåõîäèò â äðóãîå ñîñòîÿíèå, êîòîðîå ïîëíîñòüþ îïðåäåëåíî ñàìèì ýòèì âíåøíèì âîçäåéñòâèåìè òåêóùèì ñîñòîÿíèåì. Òàêèå ïðîöåññû ìîæíî ìîäåëèðîâàòü òàê íàçûâàåìûìèêîíå÷íûìè àâòîìàòàìè. êà÷åñòâå ïåðâîãî ïðèìåðà ðàññìîòðèì ñèòóàöèþ, êîãäà â äâåðè èìååòñÿ äâà çàìêà, êîòîðûå ìû îáîçíà÷èìAèB.Ïðè êàæäîì ïîâîðîòåêëþ÷à â ëþáîì èç ýòèõ çàìêîâ ìû ïåðåâîäèì ñîîòâåòñòâóþùèé çàìîêèç ïîëîæåíèÿ ¾çàêðûòî¿ â ïîëîæåíèå ¾îòêðûòî¿ è íàîáîðîò.

Ñîñòîÿíèÿýòîé ñèñòåìû áóäóò îïðåäåëÿòüñÿ îòêðûòîñòüþ è çàêðûòîñòüþ çàìêîâèB . Ïîýòîìó ìû ñ÷èòàåì, ÷òî íàøà ñèñòåìà áóäåò00: îáà çàìêà çàêðûòû,01: ïåðâûé çàìîê çàêðûò, à âòîðîé îòêðûò,10: ïåðâûé çàìîê îòêðûò, à âòîðîé çàêðûò,11: îáà çàìêà îòêðûòû.Aèìåòü 4 ñîñòîÿíèÿ:Âîçäåéñòâîâàòü íà íàøó ñèñòåìó ìû áóäåì ïîâîðà÷èâàíèåì êëþ÷à âîäíîì èç çàìêîâA èëè B (áóäåì îáîçíà÷àòü ýòè âîçäåéñòâèÿ ñîîòâåòA èëè B ). Î÷åâèäíî, ÷òî âñå âîçìîæíûå ïåðåõîäû èçñòâåííî ñèìâîëìèîäíîãî ñîñòîÿíèÿ â äðóãîå îïèñûâàþòñÿ ñëåäóþùåé òàáëèöåé:13Ãëàâà 2. Àâòîìàòíûå ÿçûêè14AB0001101110110001 .01001110Çäåñü â âåðõíåé ñòðîêå âûïèñàíû ñîñòîÿíèÿ ñèñòåìû, ñáîêó ïåðå÷èñëåíûâñå âîçìîæíûå âîçäåéñòâèÿ, à â ñîîòâåòñòâóþùåé ñòðîêå òàáëèöû óêàçàíî ñîñòîÿíèå, â êîòîðîå ñèñòåìà ïåðåéä¼ò â ðåçóëüòàòå ýòîãî âîçäåéñòâèÿ.Ðàçóìååòñÿ, ïîâîðà÷èâàÿ êëþ÷è â çàìêàõ, ìû ïðåñëåäóåì îïðåäåë¼ííóþöåëü, íàïðèìåð, ìû õîòèì îòêðûòü ýòó äâåðü.