1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 4
Текст из файла (страница 4)
Ìû áóäåì ãîâîðèòü, ÷òî êîíå÷íûé àâòîìàòA = (Q, A, δ, q0 , F )ðàñïîçíàåò (èëè ïðèíèìàåò) ñëîâî s ∈ A∗ åñëè δ ∗ (q0 , s) ∈ F . Ìíîæåñòâîâñåõ ñëîâ, ðàñïîçíàâàåìûõ êîíå÷íûì àâòîìàòîì A îáîçíà÷èì T (A), ò.å.T (A) = {s ∈ A∗ | δ ∗ (q0 , s) ∈ F } .Åñëè L = T (A), òî áóäåì ãîâîðèòü, ÷òî ÿçûê L ðàñïîçíàåòñÿ êîíå÷íûìàâòîìàòîì A. Áóäåì ãîâîðèòü, ÷òî ÿçûê L ÿâëÿåòñÿ àâòîìàòíûì ,åñëè äëÿ ïîäõîäÿùåãî êîíå÷íîãî àâòîìàòà A âûïîëíÿåòñÿ L = T (A).Àâòîìàòíûå ÿçûêè òàêæå íàçûâàþòñÿ ÿçûêàìè, ðàñïîçíàâàåìûìè êîíå÷íûìè àâòîìàòàìè.Åñëè ïðåäñòàâèòü àâòîìàò â ãðàôè÷åñêîì âèäå, òî åãî ðàáîòó ïðè ïîëó÷åíèè íà âõîä ñèìâîëîâ ñëîâà s = s0 s1 .
. . sk ìîæíî ïðåäñòàâèòü ñåáåêàê ïóòåøåñòâèå èç íà÷àëüíîãî ñîñòîÿíèÿ q0 âäîëü ñòðåëîê, ïîìå÷åííûõñèìâîëàìè s0 s1 . . . sk . Ïðè ýòîì ñëîâî s ðàñïîçíàåòñÿ (ïðèíèìàåòñÿ) àâòîìàòîì åñëè ïóòåøåñòâèå çàêàí÷èâàåòñÿ â âûäåëåííîì ñîñòîÿíèè è íåðàñïîçíàåòñÿ (íå ïðèíèìàåòñÿ) â ïðîòèâíîì ñëó÷àå.24Ãëàâà 2. Êîíå÷íûå àâòîìàòû è ãðàììàòèêè2.2 Íåäåòåðìèíèðîâàííûå àâòîìàòûÍåäåòåðìèíèðîâàííûå1 êîíå÷íûå àâòîìàòû óäîáíûé èíñòðóìåíò äëÿäîêàçàòåëüñòâà òåîðåì îá îáû÷íûõ êîíå÷íûõ àâòîìàòàõ.
Îíè îòëè÷àþòñÿ îò îáû÷íûõ ëèøü òåì, ÷òî â íèõ ïåðåõîä â ñëåäóþùåå ñîñòîÿíèå çàäàííåîäíîçíà÷íî. Âìåñòî âïîëíå îïðåäåëåííîãî ñîñòîÿíèÿ δ(q, s), â êîòîðîåäîëæåí ïåðåéòè àâòîìàò, íàõîäÿùèéñÿ â ñîñòîÿíèè q ïîñëå ïîëó÷åíèÿíà âõîä ñèìâîëà s, â íåäåòåðìèíèðîâàííûõ àâòîìàòàõ çàäàåòñÿ ìíîæåñòâî âîçìîæíûõ ñîñòîÿíèé ∆(q, s), ò.å. ñîñòîÿíèé, â êîòîðûå âîçìîæåíïåðåõîä èç ñîñòîÿíèÿ q ïðè ïîëó÷åíèè ñèìâîëà s (ìîæåò ñëó÷èòüñÿ, ÷òîçíà÷åíèå ∆(q, s) ðàâíî ∅; òîãäà ïåðåõîä èç äàííîãî ñîñòîÿíèÿ íè â êàêîåäðóãîå ñîñòîÿíèå íåâîçìîæåí). Ïðè ýòîì ðàáîòó íåäåòåðìèíèðîâàííîãî àâòîìàòà ìîæíî ïðåäñòàâëÿòü ñåáå êàê ïîñëåäîâàòåëüíûé ïåðåõîä èçîäíîãî ñîñòîÿíèÿ ê äðóãîìó âîçìîæíîìó â äàííûé ìîìåíò ñîñòîÿíèþ.Èòàê, íåäåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò A ýòî óïîðÿäî÷åííàÿ ïÿòåðêà (Q, A, ∆, q0 , F ), â êîòîðîé âñå êîìïîíåíòû èìåþò òîò æåñàìûé ñìûñë ÷òî è ó êîíå÷íûõ àâòîìàòîâ çà èñêëþ÷åíèåì ôóíêöèè ïåðåõîäîâ ∆, êîòîðàÿ ÿâëÿåòñÿ îòîáðàæåíèåì èç Q × A âî ìíîæåñòâî âñåõïîäìíîæåñòâ ìíîæåñòâà Q.Íåäåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû òàêæå äîïóñêàþò èçîáðàæåíèå â ãðàôè÷åñêîì âèäå.
Ïðè ýòîì èç îäíîãî êðóæêà, ñîîòâåòñòâóþùåãî ñîñòîÿíèþ àâòîìàòà, óæå ìîæåò âûõîäèòü íå îäíà à íåñêîëüêî(â òîì ÷èñëå è íèñêîëüêî) ñòðåëîê, ïîìå÷åííûõ îäíîé è òîé æå áóêâîéàëôàâèòà.Áóäåì ãîâîðèòü, ÷òî ñëîâî s = s0 s1 . . . sk ðàñïîçíàåòñÿ íåäåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì, A = (Q, A, ∆, q0 , F ) åñëè ñóùåñòâóåòïîñëåäîâàòåëüíîñòü ñîñòîÿíèé ýòîãî àâòîìàòà q0 = r0 , r1 , . .
. , rk+1 òàêàÿ,÷òîr1 ∈ ∆(r0 , s0 )r2 ∈ ∆(r1 , s1 )...rk+1 ∈ ∆(rk , sk )è ïðè ýòîì rk+1 ∈ F . Èíà÷å ãîâîðÿ, ïðè ïîñëåäîâàòåëüíîé ïîäà÷å íàâõîä àâòîìàòà ñèìâîëîâ ñëîâà s ñóùåñòâóåò âîçìîæíàÿ ïîñëåäîâàòåëüíîñòü ïåðåõîäîâ èç ñîñòîÿíèÿ â ñîñòîÿíèå â ñîîòâåòñòâèè ñ ïîñëåäîâàòåëüíî ïîäàííûìè íà âõîä ñèìâîëàìè ñëîâà s, îêàí÷èâàþùàÿñÿ íà1Ïî àíãëèéñêè determine îïðåäåëÿòü.2.2. Íåäåòåðìèíèðîâàííûå àâòîìàòû25âûäåëåííîå ñîñòîÿíèå, òî åñòü íà ñîñòîÿíèå èç F . Ìû áóäåì êàê è ðàíüøå îáîçíà÷àòü ÷åðåç T (A) ìíîæåñòâî âñåõ ñëîâ, ðàñïîçíàâàåìûõ íåäåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì A. Ïðè ãðàôè÷åñêîì èçîáðàæåíèè àâòîìàòà ýòî îïðåäåëåíèå ìîæíî ñôîðìóëèðîâàòü è òàê: ñëîâîs = s0 s1 .
. . sk ïðèíèìàåòñÿ àâòîìàòîì åñëè è òîëüêî åñëè â ýòîì àâòîìàòå èìååòñÿ ïóòü ïî äóãàì èç íà÷àëüíîãî ñîñòîÿíèÿ â íåêîòîðîåâûäåëåííîå ñîñòîÿíèå, âäîëü äóã êîòîðîãî ÷èòàåòñÿ ýòî ñëîâî s.Èñêëþ÷èòåëüíî âàæíûì äëÿ íàñ ÿâëÿåòñÿ ñëåäóþùåå ñâîéñòâî ýêâèâàëåíòíîñòè êîíå÷íûõ àâòîìàòîâ è íåäåòåðìèíèðîâàííûõ êîíå÷íûõàâòîìàòîâ:Òåîðåìà 2.2.1 Ïóñòü A íåäåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò.Òîãäà ñóùåñòâóåò êîíå÷íûé àâòîìàò A òàêîé, ÷òî T (A) = T (A).Äîêàçàòåëüñòâî. Îïðåäåëèì ïî àâòîìàòó A = (Q, A, ∆, q0 , F ) äåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò A = (Q, A, ∆, q 0 , F ) ñëåäóþùèì îáðàçîì:• Q åñòü ìíîæåñòâî âñåõ ïîäìíîæåñòâ Q,S• ∆(q, a) = r∈q ∆(r, a), äëÿ âñåõ q ∈ Q, a ∈ A• q 0 = {q0 },©ª• F = q ∈ Q | q ∩ F 6= ∅è ïîêàæåì, ÷òî ýòîò àâòîìàò ãîäèòñÿ äëÿ ðàñïîçíàâàíèÿ ÿçûêà T (A).Äëÿ ýòîãî äîêàæåì äâà âêëþ÷åíèÿ: T (A) ⊆ T (A) è T (A) ⊆ T (A).Äîêàæåì ïåðâîå âêëþ÷åíèå T (A) ⊆ T (A). Ïðåäïîëîæèì, ÷òî ñëîâîs = s0 s1 .
. . sk ∈ T (A). Òîãäà ñîãëàñíî îïðåäåëåíèþ ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü ñîñòîÿíèé r0 , r1 , . . . , rk , rk+1 àâòîìàòà A òàêàÿ, ÷òî q0 = r0èr1 ∈ ∆(r0 , s0 )r2 ∈ ∆(r1 , s1 )...rk+1 ∈ ∆(rk , sk )è rk+1 ∈ F . Äàâàéòå ïîñìîòðèì ÷òî ïðîèçîéäåò åñëè ìû ïîäàäèì íàâõîä àâòîìàòà A ïîñëåäîâàòåëüíîñòü ñèìâîëîâ s = s0 s1 . .
. sk . ÀâòîìàòA áóäåò ïîñëåäîâàòåëüíî íàõîäèòüñÿ â íåêîòîðûõ ñîñòîÿíèÿõq 0 = r0 , r1 = ∆(r0 , s0 ), . . . , rk = ∆(rk−1 , sk−1 ), rk+1 = ∆(rk , sk ).26Ãëàâà 2. Êîíå÷íûå àâòîìàòû è ãðàììàòèêèÍàøà çàäà÷à ïîêàçàòü, ÷òî rk+1 ∈ F . Èç ýòîãî áóäåò ñëåäîâàòü, ÷òîs ∈ T (A).
Äëÿ ýòîãî äîñòàòî÷íî ïîêàçàòü, ÷òî äëÿ âñåõ i = 0, . . . , k +1 âûïîëíåíî ri ∈ ri . Îòñþäà è ïðè i = k + 1 áóäåò ñïðàâåäëèâî, ÷òîrk+1 ∈ rk+1 , à ïîñêîëüêó rk+1 ∈ F , îòñþäà ïîëó÷èì rk+1 ∩ F 6= ∅; â ñèëóîïðåäåëåíèÿ ìíîæåñòâà F èìååì rk+1 ∈ F .Äîêàæåì ýòî ïî èíäóêöèè. Äëÿ i = 0 ýòî î÷åâèäíî òàê êàê ïî îïðåäåëåíèþ r0 = q0 ∈ {q0 } = q 0 = r0 . Äàëåå, åñëè óæå èçâåñòíî, ÷òî ri ∈ ri ,ìû ïîëó÷èì[ri+1 ∈ ∆(ri , si ) ⊆∆(q, si ) = ∆(ri , si ) = ri+1 .q∈riÒàêèì îáðàçîì, èíäóêöèîííûé øàã äîêàçàí.Äîêàæåì âòîðîå âêëþ÷åíèå T (A) ⊆ T (A).
Âîçüìåì ïðîèçâîëüíîå ñëîâî s ∈ T (A) è ïîäàäèì åãî áóêâû ïîñëåäîâàòåëüíî íà âõîä àâòîìàòà A.Àâòîìàò A áóäåò ïîñëåäîâàòåëüíî íàõîäèòüñÿ â íåêîòîðûõ ñîñòîÿíèÿõq 0 = r0 , r1 = ∆(r0 , s0 ), . . . , rk = ∆(rk−1 , sk−1 ), rk+1 = ∆(rk , sk ) ∈ F .Ïîñêîëüêó rk+1 ∈ F , â ñèëó îïðåäåëåíèÿ F íàéäåòñÿ ñîñòîÿíèå rk+1 ∈F ∩ rk+1 . ÄëÿS íàñ âàæíî, ÷òî rk+1 ∈ F . Èñïîëüçóÿ òî, ÷òî rk+1 ∈ rk+1 =∆(rk , sk ) = r∈rk ∆(r, sk ), ìû ïîëó÷èì, ÷òî ñóùåñòâóåò ñîñòîÿíèå rk ∈ rkòàêîå ÷òî rk+1 ∈ ∆(rk , sk ).
Ïîñëåäîâàòåëüíî ïðèìåíÿÿ òå æå ñàìûå ðàññóæäåíèÿ ê rk , rk−1 , . . . ìû ïîëó÷èì, ÷òî ñóùåñòâóåò ïîñëåäîâàòåëüíîñòüñîñòîÿíèé r0 , . . . , rk , rk+1 òàêàÿ, ÷òî ri ∈ ri è ri+1 ∈ ∆(ri , si ) äëÿ âñåõi = 0, . . . , k . Ïðè ýòîì r0 ∈ r0 = q 0 = {q0 }, òî åñòü r0 = q0 . Îòñþäà ïîîïðåäåëåíèþ ïîëó÷èì, ÷òî s ∈ T (A). ¤Óïðàæíåíèÿ1. Ïîñòðîéòå è èçîáðàçèòå ãðàôè÷åñêè êîíå÷íûé àâòîìàò A, ðàñïîçíàþùèéà) ÿçûê L = ∅ íàä àëôàâèòîì A = {0};á) ÿçûê L = {Λ} íàä àëôàâèòîì A = {0};â) ÿçûê L = {0} íàä àëôàâèòîì A = {0, 1};ã) ÿçûê L = A (ò.å., ìíîæåñòâî îäíîýëåìåíòíûõ ñëîâ) íàä àëôàâèòîìA = {0, 1, 2};ä) ÿçûê L = {0}∗ íàä àëôàâèòîì A = {0, 1};å) ÿçûê L = {0, 1}∗ íàä àëôàâèòîì A = {0, 1, 2};æ) ÿçûê, ñîñòîÿùèé èç ñëîâ, íà÷èíàþùèõñÿ íà 00 íàä àëôàâèòîì A ={0, 1};ç) ÿçûê, ñîñòîÿùèé èç ñëîâ, íå íà÷èíàþùèõñÿ íà 00 íàä àëôàâèòîìA = {0, 1};è) ÿçûê, ñîñòîÿùèé èç ñëîâ, íà÷èíàþùèõñÿ íà 01 íàä àëôàâèòîì A =2.2.
Íåäåòåðìèíèðîâàííûå àâòîìàòû27{0, 1, 2};ê) ÿçûê, ñîñòîÿùèé èç ñëîâ, îêàí÷èâàþùèõñÿ íà 00 íàä àëôàâèòîì A ={0, 1};ë) ÿçûê, ñîñòîÿùèé èç ñëîâ, îêàí÷èâàþùèõñÿ íà 01 íàä àëôàâèòîì A ={0, 1, 2};ì) ÿçûê, ñîñòîÿùèé èç ñëîâ, ñîäåðæàùèõ ðîâíî îäèí ñèìâîë 1 è ðîâíî 2ñèìâîëà 0 íàä àëôàâèòîì A = {0, 1, 2};í) ÿçûê, ñîñòîÿùèé èç ñëîâ, ñîäåðæàùèõ ÷åòíîå ÷èñëî ñèìâîëîâ 1 èíå÷åòíîå ÷èñëî ñèìâîëîâ 2 íàä àëôàâèòîì A = {0, 1, 2};î) ÿçûê L = {1. . 1} 6= Λ | n ∈ N} íàä àëôàâèòîì A = {0, 1};| .{z2nï) ÿçûê L = {s ∈ A | â ñëîâå s ðàçíîñòü ÷èñëà ñèìâîëîâ 0 è ÷èñëà ñèìâîëîâ 1 ÷åòíà} íàä àëôàâèòîì A = {0, 1};ð) ÿçûê L = {f . .
. f (0) | n ∈ N} íàä àëôàâèòîì A = {f, 0, (, )};| {z }nñ) ÿçûê L = {s ∈ {a, b}∗ | â s íå âñòðå÷àåòñÿ ïîäðÿä äâå áóêâû b};ò) ÿçûê L = {s ∈ {a, b}∗ | â s âñòðå÷àåòñÿ äâå áóêâû b ïîäðÿä};ó) ÿçûê L = {s ∈ {a, b}∗ | â s åñòü ïîäñëîâî abab};ô) ÿçûê L = {s ∈ {a, b}∗ | â s íå ñîäåðæèòñÿ ïîäñëîâî abab};õ) ÿçûê L = {s ∈ {a, b}∗ | â s âñòðå÷àåòñÿ äâå áóêâû a ïîäðÿä è äâå áóêâûb ïîäðÿä};2. Ïîñòðîèòü êîíå÷íûé àâòîìàò, ðàñïîçíàþùèé çàïèñè ÷åòíûõ íàòóðàëüíûõ ÷èñåë â àëôàâèòå {0, .
. . , 9}.3. Ïîñòðîèòü êîíå÷íûé àâòîìàò, ðàñïîçíàþùèé çàïèñè öåëûõ ÷èñåë âèäà 0,+a0 a1 . . . an , −a0 a1 . . . an , (a0 6= 0) ai ∈ {0, . . . , 9} â àëôàâèòå {+, −, 0, . . . , 9}.4.∗Ðàññìîòðèì ïðèìåð íà ñëîæåíèå ñòîëáèêîì â äâîè÷íîé ñèñòåìå:1 0 01 0 1 1.1 1 1 1Äîïîëíèì ïóñòûå ìåñòà ñèìâîëîì ∗:∗1110101101.1 ∗100Ñ ýòèì ïðèìåðîì ìîæíî àññîöèèðîâàòü ñëîâî 1 0 1 1 1111xâ àëôàâèòå èç ñèìâîëîâ âèäà y , x, y, z ∈ {∗, 0, 1}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
