3. Регулярные выражения. Алгебра регулярных выражений. Уравнения в регулярных выражениях. Теорема Клини (1162494), страница 2
Текст из файла (страница 2)
Êàæäûé àâòîìàòíûé ÿçûê ÿâëÿåòñÿðåãóëÿðíûì ÿçûêîì.Äîêàçàòåëüñòâî. Ïóñòü A = (Σ, S, I , F , T ) êîíå÷íûé àâòîìàò áåç ε -ïåðåõîäîâ, è ïðè ýòîìI ∩ F = ∅ . Ïîñòðîèì ðåãóëÿðíîå âûðàæåíèå,îïèñûâàþùåå àâòîìàòíûé ÿçûê L(A) .Äëÿ ýòîãî ñîñòàâèì è ðåøèì ñèñòåìó óðàâíåíèéíàä ðåãóëÿðíûìè âûðàæåíèÿìè.ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÒåîðåìà 3.5. Êàæäûé àâòîìàòíûé ÿçûê ÿâëÿåòñÿðåãóëÿðíûì ÿçûêîì.Äîêàçàòåëüñòâî. Ïóñòü A = (Σ, S, I , F , T ) êîíå÷íûé àâòîìàò áåç ε -ïåðåõîäîâ, è ïðè ýòîìI ∩ F = ∅ . Ïîñòðîèì ðåãóëÿðíîå âûðàæåíèå,îïèñûâàþùåå àâòîìàòíûé ÿçûê L(A) .Äëÿ ýòîãî ñîñòàâèì è ðåøèì ñèñòåìó óðàâíåíèéíàä ðåãóëÿðíûìè âûðàæåíèÿìè.1). Äëÿ êàæäîãî ñîñòîÿíèÿ s, s ∈ S , ââåäåìïåðåìåííóþ Xs , à òàêæåìíîæåñòâî ïàð00 aIn(s) = {(s , a) : s −→ s ∈ T } .ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛ2). Äëÿ êàæäîãî ñîñòîÿíèÿ s,óðàâíåíèåXs =Xs ∈S,ñîñòàâèìXs 0 · a + δs ,(s 0 ,a)∈In(s)ãäå δs = 1 , åñëè s ∈ I , è δs = 0 èíà÷å.ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÀ îòêóäà âçÿëèñü ýòè óðàâíåíèÿ?ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÀ îòêóäà âçÿëèñü ýòè óðàâíåíèÿ?Ðàññìîòðèì ñîñòîÿíèå s0 àâòîìàòà.a0?s0 *YHH6 HHa3a1HHa2s1s3s2ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÀ îòêóäà âçÿëèñü ýòè óðàâíåíèÿ?Ðàññìîòðèì ñîñòîÿíèå s0 àâòîìàòà.a0?Ls0 s 0 *YHH6 HHa3a1HHa2Ls1 s 1s3 Ls3Ls2 s 2È ïóñòü Ls ýòî ÿçûê, ñîñòîÿùèé èç ñëîâ,êîòîðûå ïðî÷èòûâàåò àâòîìàò, äîñòèãíóâñîñòîÿíèÿ si , 0 ≤ i ≤ 3 .iÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÒîãäà êàæäîå ñëîâî w ÿçûêà Ls ïðåäñòàâèìî ââèäå w = wi · ai äëÿ íåêîòîðîãî ñëîâà wi , wi ∈ Li .0a0?w0 s 0 *YHH6 HHa3a1H a2Hw1 s1s3 w3w2 s 2ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÒîãäà ñïðàâåäëèâî ðàâåíñòâîLs0 = Ls0 · a0 + Ls1 · a1 + Ls2 · a2 + Ls3 · a3.a0?Ls0 s 0 *YHHa16 HHa3HHa2Ls1 s 1s 3 Ls3Ls2 s 2ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÒîãäà ñïðàâåäëèâî ðàâåíñòâîLs0 = Ls0 · a0 + Ls1 · a1 + Ls2 · a2 + Ls3 · a3.a0?Ls0 s 0 *YHHa16 HHa3HHa2Ls1 s 1s 3 Ls3Ls2 s 2Îòñþäà è âîçíèêàåò óðàâíåíèåXs0 = Xs0 · a0 + Xs1 · a1 + Xs2 · a2 + Xs3 · a3ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛ3).
Íàéäåì ðåøåíèå ýòîé ñèñòåìû óðàâíåíèé{Xs = Rs : s ∈ S},ìåòîäîì Ãàóññà (èñêëþ÷åíèåì ïåðåìåííûõ),èñïîëüçóÿ óòâåðæäåíèå 3.3.Ñîãëàñíî ýòîìó óòâåðæäåíèþ (à òàêæåïîñëåäóþùåé çàäà÷å) òàêîå ðåøåíèå áóäåòåäèíñòâåííûì.ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛ4) Èíäóêöèåé ïî äëèíå ñëîâà w ïîêàæåì, ÷òîw ∈ L(Rs ) òîãäà è òîëüêî òîãäà, êîãäà ñëîâî wäîïóñêàåòñÿ êîíå÷íûì àâòîìàòîìAs = (Σ, S, I , {s}, T ) : ýòî ëåãêî âèäíî èçóñòðîéñòâà óðàâíåíèéXs =X(s 0 ,a)∈In(s)Xs 0 · a + δs ,ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛ4) Èíäóêöèåé ïî äëèíå ñëîâà w ïîêàæåì, ÷òîw ∈ L(Rs ) òîãäà è òîëüêî òîãäà, êîãäà ñëîâî wäîïóñêàåòñÿ êîíå÷íûì àâòîìàòîìAs = (Σ, S, I , {s}, T ) : ýòî ëåãêî âèäíî èçóñòðîéñòâà óðàâíåíèéXs =XXs 0 · a + δs ,(s 0 ,a)∈In(s)5). Òîãäà L(A) = L( P Rs ) .s∈FQEDÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÇàäà÷à 10. À çà÷åì ìíå ïîíàäîáèëîñü â íà÷àëåäîêàçàòåëüñòâà îãîâîðèòü óñëîâèå I ∩ F = ∅ ?È êàê íóæíî ìîäèôèöèðîâàòü äîêàçàòåëüñòâîòåîðåìû 3.5, åñëè ýòî óñëîâèå íå âûïîëíåíî?ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛa?s0 dbs1 6 cÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛa?s0 dbs1 6 cX0 = X0 · a + X1 · d + 1X1 = X0 · b + X1 · c + 0ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛa?s0 dbs1 6 cX0 = X0 · a + (X1 · d + 1)X1 = X0 · b + X1 · cÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛa?s0 dbs1 6 cX0 = (X1 · d + 1) · a∗X1 = X0 · b + X1 · cÓòâåðæäåíèå 3.3 î ðåøåíèè óðàâíåíèéÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛa?s0 dbs1 6 cX0 = (X1 · d + 1) · a∗X1 = (X1 · d + 1) · a∗ · b + X1 · cÈñêëþ÷åíèå ïåðåìåííîé X0ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛa?s0 dbs1 6 cX0 = (X1 · d + 1) · a∗X1 = X1 · (da∗ b + c) + a∗ bÏðèâåäåíèå ïîäîáíûõ ñëàãàåìûõÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛa?s0 dbs1 6 cX0 = (X1 · d + 1) · a∗X1 = a∗ b(da∗ b + c)∗Óòâåðæäåíèå 3.3 î ðåøåíèè óðàâíåíèéÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛa?s0 dbs1 6 cÈñêîìîå ðåãóëÿðíîå âûðàæåíèåR = a∗b(da∗b + c)∗ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÒåîðåìà 3.6.
[Ñ. Êëèíè] Ôîðìàëüíûé ÿçûêÿâëÿåòñÿ àâòîìàòíûì òîãäà è òîëüêî òîãäà, êîãäàîí ÿâëÿåòñÿ ðåãóëÿðíûì.ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÒåîðåìà 3.6. [Ñ. Êëèíè] Ôîðìàëüíûé ÿçûêÿâëÿåòñÿ àâòîìàòíûì òîãäà è òîëüêî òîãäà, êîãäàîí ÿâëÿåòñÿ ðåãóëÿðíûì.Ýòà òåîðåìà î÷åíü âàæíà äëÿ ïîñòðîåíèÿàëãîðèòìîâ ïîèñêà ñòðîê (òåêñòîâ, ïîòîêîâ äàííûõè ïð.), ïîäïàäàþùèõ ïîä çàäàííûé øàáëîí.Îáëàñòè ïðèìåíåíèÿ: èíòåðíåò-ïîèñê, ïîñòðîåíèåòàáëèö ìàðøðóòèçàöèè, îáíàðóæåíèåâðåäîíîñíîãî êîäà, âûÿâëåíèå ïëàãèàòà, è ïð.ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÏðèíöèï ïðèìåíåíèÿ:1. Èíòåðåñóþùåå ìíîæåñòâî ñòðîê îïèñûâàåì ââèäå øàáëîíà P , êîòîðîìó ñîîòâåòñòâóåòíåêîòîðîå ðåãóëÿðíîå âûðàæåíèå R .2. Äëÿ ðåãóëÿðíîãî âûðàæåíèÿ R ñòðîèì(íåäåòåðìèíèðîâàííûé) êîíå÷íûé àâòîìàò A .3.
Ïðîâîäèì äåòåðìèíèçàöèþ àâòîìàòà A èïîëó÷àåì äåòåðìèíèðîâàííûé àâòîìàò A0 .4. Íà âõîä àâòîìàòà A0 ïîäàåì ñòðîêó w .Àâòîìàò A0 äîñòèãàåò ôèíàëüíîãî ñîñòîÿíèÿòîãäà è òîëüêî òîãäà, êîãäà w ïîäïàäàåò ïîäøàáëîí P .ÇÀÄÀ×À ÏÎÈÑÊÀ ÏÎ ØÀÁËÎÍÓÎñíîâíûå êîíñòðóêöèè ÿçûêà îïèñàíèÿ øàáëîíîâ:IIIIIII? ëþáàÿ áóêâà;∗ ëþáîå ñëîâî;{a1 , a2 , a3 : +} ëþáàÿ èç áóêâ a1 , a2 , a3 ;{b1 , b2 : −} ëþáàÿ èç áóêâ êðîìå b1 , b2 ;R[5 : 8] øàáëîí R , ïîâòîðÿþùèéñÿ ïîäðÿäíå ìåíåå 5 è íå áîëåå 8 ðàç;R1 &R2 ïåðåñå÷åíèå øàáëîíîâ R1 è R2 ;R1 + R2 àëüòåðíàòèâíûé âûáîð(îáúåäèíåíèå) øàáëîíîâ R1 è R2 .ÇÀÄÀ×À ÏÎÈÑÊÀ ÏÎ ØÀÁËÎÍÓÏðèìåð. Ïóñòü Σ = {a, b, c} .
Òîãäà øàáëîíó{b : −}[1 : 2] ∗ b?ñîîòâåòñòâóåò ðåãóëÿðíîå âûðàæåíèå((a + c) + (a + c)(a + c))(a + b + c)∗ b(a + b + c)ÇÀÄÀ×À ÏÎÈÑÊÀ ÏÎ ØÀÁËÎÍÓÍàèáîëüøóþ âû÷èñëèòåëüíóþ òðóäíîñòü èìååòýòàï ïðåîáðàçîâàíèÿ íåäåòåðìèíèðîâàííîãîêîíå÷íîãî àâòîìàòà â äåòåðìèíèðîâàííûé,ïîñêîëüêó çäåñü âîçìîæåí ýôôåêò¾êîìáèíàòîðíîãî âçðûâà¿ ÷èñëà ñîñòîÿíèé.Îäíàêî äëÿ íåêîòîðûõ øèðîêî èñïîëüçóåìûõøàáëîíîâ ñîîòâåòñòâóþùèå äåòåðìèíèðîâàííûåàâòîìàòû èìåþò ïðîñòîå óñòðîéñòâî è ñòðîÿòñÿäîâîëüíî ýôôåêòèâíî.ÀËÃÎÐÈÒÌ ÀÕÎÊÎÐÀÑÈÊÐàññìîòðèì çàäà÷ó ïîèñêà âõîæäåíèé çàäàííîãîñëîâà w = x1x2 .
. . xk â ïðîèçâîëüíîé ñòðîêå.ÀËÃÎÐÈÒÌ ÀÕÎÊÎÐÀÑÈÊÐàññìîòðèì çàäà÷ó ïîèñêà âõîæäåíèé çàäàííîãîñëîâà w = x1x2 . . . xk â ïðîèçâîëüíîé ñòðîêå.Ôîðìàëüíî ýòó çàäà÷ó ìîæíî ïîñòàâèòü òàê:ïîñòðîèòü àëãîðèòì, ðàñïîçíàþùèé âñå ñëîâà,èìåþùèå ñóôôèêñ w .Ñëîâà ýòîãî ÿçûêà îïèñûâàþòÿ øàáëîíîì∗x1 x2 . . . xk è ðàñïîçíàþòñÿ íåäåòåðìèíèðîâàííûìêîíå÷íûì àâòîìàòîì ïðîñòîãî âèäàa1 , a2 , . . . , an?- ss01 x x12r r r-xkskÀËÃÎÐÈÒÌ ÀÕÎÊÎÐÀÑÈÊÍî êàê ïîñòðîèòü äåòåðìèíèðîâàííûé àâòîìàò?ÀËÃÎÐÈÒÌ ÀÕÎÊÎÐÀÑÈÊÍî êàê ïîñòðîèòü äåòåðìèíèðîâàííûé àâòîìàò?Óäîáíîå ðåøåíèå ïðèäóìàëè â 1965 ãîäó ÀëüôðåäÀõî è Ìàðãåðåò Êîðàñèê.Ìèíèìàëüíûé äåòåðìèíèðîâàííûé àâòîìàò,ðàñïîçíàþùèé âñå òåêñòû, îêàí÷èâàþùèåñÿñòðîêîé w = x1x2 . .
. xk , èìååò âèäAw = (Σ, S, {s0 }, {sk }, T ) , ãäåS = {s0 , s1 , . . . , sk } ;äëÿ ëþáûõ si , si ∈ S,y è y , y ∈ Σ, â ìíîæåñòâåT åñòü ïåðåõîä si −→ sj , ãäåj = max(` : x1 x2 . . . x` ∈ Suff (x1 x2 . . . xi y )) :¾èùè ìàêñèìàëüíûé ïðåôèêñ w , ÿâëÿþùèéñÿñóôôèêñîì ïðî÷èòàííîé ÷àñòè òåêñòà¿IIÀËÃÎÐÈÒÌ ÀÕÎÊÎÐÀÑÈÊÅñëè Σ = {a, b} è w = abaaba , òî ìèíèìàëüíûéäåòåðìèíèðîâàííûé àâòîìàò Aw , ðàñïîçíàþùèéÿçûê (a + b)∗abaaba èìååò ñëåäóþùèé âèä. baa?? b s0 a s1 b s2 a s5 a s6s3 a s4 b IIIIbabbÀËÃÎÐÈÒÌ ÀÕÎÊÎÐÀÑÈÊÏðåäëîæåííûé àëãîðèòì ñòðîèò àâòîìàò Aw çàâðåìÿ O(|w |2) è îáíàðóæèâàåò âñå âõîæäåíèÿñòðîêè w â òåêñòå äëèíû n çà âðåìÿ O(n) .ÇÀÄÀ×À 11.Ðàçðàáîòàéòå îáîáùåíèå ïðåäëîæåííîãî ìåòîäà,êîòîðîå ïîçâîëÿåò äëÿ ïðîèçâîëüíîãî ìíîæåñòâàñòðîê D = {w1, w2, . . . , wm } ïîñòðîèòüìèíèìàëüíûé äåòåðìèíèðîâàííûé êîíå÷íûéàâòîìàò AD , ðàñïîçíàþùèé âñå ñëîâà,îêàí÷èâàþùèåñÿ õîòÿ áû îäíîé èç ñòðîêìíîæåñòâà D .ÒÅÕÍÎËÎÃÈß ÏÐÈÌÅÍÅÍÈß ÊÎÍÅ×ÍÛÕÀÂÒÎÌÀÒÎÂÑôîðìóëèðóéòå çàäà÷ó ïîèñêà èëè ðàñïîçíàâàíèÿíà ÿçûêå ñëîâàðíûõ øàáëîíîâÒÅÕÍÎËÎÃÈß ÏÐÈÌÅÍÅÍÈß ÊÎÍÅ×ÍÛÕÀÂÒÎÌÀÒÎÂÑôîðìóëèðóéòå çàäà÷ó ïîèñêà èëè ðàñïîçíàâàíèÿíà ÿçûêå ñëîâàðíûõ øàáëîíîâ⇓Òðàíñëèðóéòå øàáëîíâ ðåãóëÿðíîå âûðàæåíèåÒÅÕÍÎËÎÃÈß ÏÐÈÌÅÍÅÍÈß ÊÎÍÅ×ÍÛÕÀÂÒÎÌÀÒÎÂÑôîðìóëèðóéòå çàäà÷ó ïîèñêà èëè ðàñïîçíàâàíèÿíà ÿçûêå ñëîâàðíûõ øàáëîíîâ⇓Òðàíñëèðóéòå øàáëîíâ ðåãóëÿðíîå âûðàæåíèå⇓Ïîñòðîéòå äëÿ ðåãóëÿðíîãî âûðàæåíèÿíåäåòåðìèíèðîâàííûé àâòîìàòÒÅÕÍÎËÎÃÈß ÏÐÈÌÅÍÅÍÈß ÊÎÍÅ×ÍÛÕÀÂÒÎÌÀÒÎÂÑôîðìóëèðóéòå çàäà÷ó ïîèñêà èëè ðàñïîçíàâàíèÿíà ÿçûêå ñëîâàðíûõ øàáëîíîâ⇓Òðàíñëèðóéòå øàáëîíâ ðåãóëÿðíîå âûðàæåíèå⇓Ïîñòðîéòå äëÿ ðåãóëÿðíîãî âûðàæåíèÿíåäåòåðìèíèðîâàííûé àâòîìàò⇓Äåòåðìèíèçèðóéòå ýòîò àâòîìàòÒÅÕÍÎËÎÃÈß ÏÐÈÌÅÍÅÍÈß ÊÎÍÅ×ÍÛÕÀÂÒÎÌÀÒÎÂÑôîðìóëèðóéòå çàäà÷ó ïîèñêà èëè ðàñïîçíàâàíèÿíà ÿçûêå ñëîâàðíûõ øàáëîíîâ⇓Òðàíñëèðóéòå øàáëîíâ ðåãóëÿðíîå âûðàæåíèå⇓Ïîñòðîéòå äëÿ ðåãóëÿðíîãî âûðàæåíèÿíåäåòåðìèíèðîâàííûé àâòîìàò⇓Äåòåðìèíèçèðóéòå ýòîò àâòîìàò⇓Ìèíèìèçèðóéòå ïîëó÷åííûé àâòîìàòÒÅÕÍÎËÎÃÈß ÏÐÈÌÅÍÅÍÈß ÊÎÍÅ×ÍÛÕÀÂÒÎÌÀÒÎÂÑôîðìóëèðóéòå çàäà÷ó ïîèñêà èëè ðàñïîçíàâàíèÿíà ÿçûêå ñëîâàðíûõ øàáëîíîâ⇓Òðàíñëèðóéòå øàáëîíâ ðåãóëÿðíîå âûðàæåíèå⇓Ïîñòðîéòå äëÿ ðåãóëÿðíîãî âûðàæåíèÿíåäåòåðìèíèðîâàííûé àâòîìàò⇓Äåòåðìèíèçèðóéòå ýòîò àâòîìàò⇓Ìèíèìèçèðóéòå ïîëó÷åííûé àâòîìàòÂû ïîñòðîèëè îïòèìàëüíóþ ïðîãðàììó ïîèñêà!ÄÂÓÑÒÎÐÎÍÍÈÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛÊîíå÷íûé àâòîìàò ìîæíî ðàññìàòðèâàòü êàêìåõàíè÷åñêîå óñòðîéñòâî, êîòîðîå äâèæåòñÿ âîäíó ñòîðîíó ïî ëåíòå, íà êîòîðîé çàïèñàíîçàäàííîå ñëîâî â àëôàâèòå Σ .
Ëåíòàîêàí÷èâàåòñÿ ãðàíè÷íûì ìàðêåðîì a, a∈/ Σ .Ñëîâî äîïóñêàåòñÿ àâòîìàòîì, åñëè ïðèäîñòèæåíèè ãðàíè÷íîãî ìàðêåðà àâòîìàòîêàçûâàåòñÿ â ôèíàëüíîì ñîñòîÿíèè.x1 x2 x3 · · ·⇑q0· · · xN a-ÄÂÓÑÒÎÐÎÍÍÈÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛÊîíå÷íûé àâòîìàò ìîæíî ðàññìàòðèâàòü êàêìåõàíè÷åñêîå óñòðîéñòâî, êîòîðîå äâèæåòñÿ âîäíó ñòîðîíó ïî ëåíòå, íà êîòîðîé çàïèñàíîçàäàííîå ñëîâî â àëôàâèòå Σ . Ëåíòàîêàí÷èâàåòñÿ ãðàíè÷íûì ìàðêåðîì a, a∈/ Σ .Ñëîâî äîïóñêàåòñÿ àâòîìàòîì, åñëè ïðèäîñòèæåíèè ãðàíè÷íîãî ìàðêåðà àâòîìàòîêàçûâàåòñÿ â ôèíàëüíîì ñîñòîÿíèè.x1 x2 x3 · · ·⇑qi1· · · xN a-ÄÂÓÑÒÎÐÎÍÍÈÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛÊîíå÷íûé àâòîìàò ìîæíî ðàññìàòðèâàòü êàêìåõàíè÷åñêîå óñòðîéñòâî, êîòîðîå äâèæåòñÿ âîäíó ñòîðîíó ïî ëåíòå, íà êîòîðîé çàïèñàíîçàäàííîå ñëîâî â àëôàâèòå Σ . Ëåíòàîêàí÷èâàåòñÿ ãðàíè÷íûì ìàðêåðîì a, a∈/ Σ .Ñëîâî äîïóñêàåòñÿ àâòîìàòîì, åñëè ïðèäîñòèæåíèè ãðàíè÷íîãî ìàðêåðà àâòîìàòîêàçûâàåòñÿ â ôèíàëüíîì ñîñòîÿíèè.x1 x2 x3 · · ·⇑qi2· · · xN a-ÄÂÓÑÒÎÐÎÍÍÈÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛÊîíå÷íûé àâòîìàò ìîæíî ðàññìàòðèâàòü êàêìåõàíè÷åñêîå óñòðîéñòâî, êîòîðîå äâèæåòñÿ âîäíó ñòîðîíó ïî ëåíòå, íà êîòîðîé çàïèñàíîçàäàííîå ñëîâî â àëôàâèòå Σ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
