1610906281-d25a58898a45262b0b837c281ba962eb (824376), страница 6
Текст из файла (страница 6)
Äðóãèõ âûäåëåííûõ ñîñòîÿíèé íåò.ÄîïîëíåíèåÏåðåñå÷åíèåÊîíêàòåíàöèÿdiH iH iA1diA2diHHH iA1iΛHHHj i*iΛA2diËþáîé ïóòü âäîëü äóã íîâîãî àâòîìàòà, íà÷èíàþùèéñÿ â íà÷àëüíîì ñîñòîÿíèèè çàêàí÷èâàþùèéñÿ â âûäåëåííîì ñîñòîÿíèè, ðàçáèâàåòñÿ íà äâà ó÷àñòêà. Ïåðâûéó÷àñòîê ñîñòîèò òîëüêî èç äóã àâòîìàòà A1 è çàêàí÷èâàåòñÿ â îäíîì èç (áûâøèõ)âûäåëåííûõ ñîñòîÿíèé A1 . Âòîðîé ó÷àñòîê íà÷èíàåòñÿ ñ Λ-ïåðåõîäà, îñòàëüíûå åãîïåðåõîäû ïîëíîñòüþ ñîäåðæàòñÿ âíóòðè àâòîìàòà A2 , è çàêàí÷èâàåòñÿ â îäíîì èçâûäåëåííûõ ñîñòîÿíèé íîâîãî àâòîìàòà. Îòñþäà ñëåäóåò, ÷òî L(A) = L(A1 )L(A2 ).. Ïî çàäàííîìó ä.ê.à.
A ïîñòðîèì àâòîìàò A0 , ðàñïîçíàþùèéÿçûê (L(A))∗ , ñëåäóþùèì îáðàçîì (ñì. ñõåìó ïîñòðîåíèÿ íà ðèñóíêå):à) Ââåä¼ì íîâîå íà÷àëüíîå ñîñòîÿíèå q00 , ñäåëàâ åãî îäíîâðåìåííî âûäåëåííûì, èäîáàâèâ íîâóþ äóãó, âûõîäÿùóþ èç q00 , âõîäÿùóþ â íà÷àëüíîå ñîñòîÿíèå q0 àâòîìàòàA, è ïîìå÷åííóþ ñèìâîëîì Λ.á) Äîáàâèì â àâòîìàò A íîâûå äóãè, âûõîäÿùèå èç âñåõ âûäåëåííûõ ñîñòîÿíèéàâòîìàòà A, âõîäÿùèå â q0 , è ïîìå÷åííûå ñèìâîëîì Λ.â) Âûäåëåííûìè ñîñòîÿíèÿìè àâòîìàòà A0 îáúÿâëÿþòñÿ âñå âûäåëåííûå ñîñòîÿíèÿ A è ñîñòîÿíèå q00 .Çâ¼çäî÷êà Êëèíè24Ãëàâà II. Êîíå÷íûå àâòîìàòû è ôîðìàëüíûå ãðàììàòèêèA0diH iq0AdiHHHd iq00Λ- ?iq0 6ΛdiAΛdiÄîêàæåì, ÷òî (L(A))∗ = L(A0 ).
Äëÿ ýòîãî ñíà÷àëà óñòàíîâèì ñïðàâåäëèâîñòüâêëþ÷åíèÿ (L(A))∗ ⊆ L(A0 ). Ïóñòü ñëîâî w ∈ (L(A))∗ . Åñëè w = Λ, òî w ∈ L(A0 )â ñèëó ïóíêòà (à). Åñëè æå w 6= Λ, òî ñëîâî w ïðåäñòàâèìî â âèäå w = w1 . . . wn , ãäåwi ∈ L(A) äëÿ êàæäîãî 1 6 i 6 n. Ñëåäîâàòåëüíî, äëÿ êàæäîãî 1 6 i 6 n ñëîâî wi÷èòàåòñÿ âäîëü ñëåäóþùåãî ïóòè â àâòîìàòå A:siki isi1 i si2r1 −→ . .
. −−→rki ∈ F,q0 = r0i −→â êîòîðîì ïîñëåäíåå ñîñòîÿíèå rki i ÿâëÿåòñÿ âûäåëåííûì â A.  ñèëó ïóíêòà (à) äëÿi = 1 â àâòîìàòå A0 ñóùåñòâóåò Λ-ïåðåõîä èç q00 â q0 = r01 . Ñëåäîâàòåëüíî, ñëîâî w1áóäåò ÷èòàòüñÿ âäîëü ñëåäóþùåãî ïóòè â àâòîìàòå A0 :q0011s1k1 1Λ 1 s1 1 s2−→ r0 −→ r1 −→ . . . −−→ rk1 . ñèëó ïóíêòà (á) äëÿ 2 6 i 6 n â íîâîì àâòîìàòå A0 ñóùåñòâóåò Λ-ïåðåõîä èçñîñòîÿíèÿ rki−1â ñîñòîÿíèå r0i = q0 . Òàêèì îáðàçîì, äëÿ êàæäîãî 2 6 i 6 n ñëîâî wii−1áóäåò ÷èòàòüñÿ âäîëü ñëåäóþùåãî ïóòè â àâòîìàòå A0 :iisiki iΛ i s1 i s2−−→ rki .rki−1−→r−→r−→...01i−1Ñîåäèíèâ ïîñëåäîâàòåëüíî âñå òàêèå ïóòè â îäíó öåïî÷êó, ìû ïîëó÷èì ïóòü â àâòîìàòå A0 , êîòîðûé íà÷èíàåòñÿ â ñîñòîÿíèè q00 , çàêàí÷èâàåòñÿ â íåêîòîðîì âûäåëåííîìñîñòîÿíèè àâòîìàòà A0 , è âäîëü äóã êîòîðîãî ÷èòàåòñÿ w.
Ñëåäîâàòåëüíî, w ∈ L(A0 ).Òåïåðü óñòàíîâèì îáðàòíîå âêëþ÷åíèå L(A0 ) ⊆ (L(A))∗ . Ïóñòü w ∈ L(A0 ). Ìîæíîñ÷èòàòü, ÷òî w 6= Λ (ñëó÷àé ïóñòîãî ñëîâà òðèâèàëåí). Ñëåäîâàòåëüíî, w ÷èòàåòñÿâäîëü ïóòè â àâòîìàòå A0 , êîòîðûé íà÷èíàåòñÿ â ñîñòîÿíèè q00 è çàêàí÷èâàåòñÿ âíåêîòîðîì âûäåëåííîì ñîñòîÿíèè q 0 .
Ïîñêîëüêó â A0 íåò äóã, âõîäÿùèõ â ñîñòîÿíèåq00 , çàêëþ÷àåì, ÷òî q00 6= q 0 . Ïîýòîìó ñîñòîÿíèå q 0 ÿâëÿåòñÿ âûäåëåííûì è â èñõîäíîìàâòîìàòå A.p1Hd iq0p2p3r1r2rnΛ- i-... - id Λ - i- . . . - id - . . . - i- . . . - idw1w2wnΛÏîñêîëüêó w 6= Λ, ïåðâîé äóãîé äàííîãî ïóòè îáÿçàí áûòü Λ-ïåðåõîä q00 −→ q0 .Ïóñòü â äàííîì ïóòè âñòðå÷àåòñÿ ðîâíî n ïóñòûõ ïåðåõîäîâ. Äëÿ 1 6 i 6 n ââåä¼ìñëåäóþùèå îáîçíà÷åíèÿ. Ïóñòü i-é ïóñòîé ïåðåõîä, âñòðåòèâøèéñÿ â äàííîì ïóòè,Λèìååò âèä pi −→ ri . Òîãäà p1 = q00 è äëÿ êàæäîãî 2 6 i 6 n ñîñòîÿíèå pi ÿâëÿåòñÿâûäåëåííûì â èñõîäíîì àâòîìàòå A.
Êðîìå ýòîãî, ri = q0 äëÿ âñåõ 1 6 i 6 n. Äëÿ1 6 i 6 n − 1 îáîçíà÷èì ÷åðåç wi ñëîâî, êîòîðîå ÷èòàåòñÿ âäîëü ó÷àñòêà ïóòè,25 7. Ñâîéñòâà àâòîìàòíûõ ÿçûêîâíà÷èíàþùåãîñÿ â ri è çàêàí÷èâàþùåãîñÿ â pi+1 . ×åðåç wn îáîçíà÷èì ñëîâî, êîòîðîå÷èòàåòñÿ âäîëü ó÷àñòêà ïóòè, íà÷èíàþùåãîñÿ â rn è çàêàí÷èâàþùåãîñÿ â q 0 .Äëÿ êàæäîãî 1 6 i 6 n ó÷àñòîê ïóòè, âäîëü êîòîðîãî ÷èòàåòñÿ wi , ïîëíîñòüþñîäåðæèòñÿ â àâòîìàòå A, íà÷èíàåòñÿ â ñîñòîÿíèè q0 è çàêàí÷èâàåòñÿ â íåêîòîðîìâûäåëåííîì ñîñòîÿíèè àâòîìàòà A. Ñëåäîâàòåëüíî, wi ∈ L(A). Òàêèì îáðàçîì, w =w1 . .
. wk ∈ (L(A))∗ .ïðÿìîå ïðåäûäóùåé òåîðåìå ìîæíî ïðåäëîæèòüäîêàçàòåëüñòâî çàìêíóòîñòè àâòîìàòíûõ ÿçûêîâ îòíîñèòåëüíî ïåðåñå÷åíèÿ, à èìåííî, åñëè çàäàíûäâà ä.ê.à. A1 = hQ1 , A, δ1 , q01 , F1 i è A2 = hQ2 , A, δ2 , q02 , F2 i, òî îïðåäåëèì ä.ê.à. A1 × A2 ,êîòîðûé íàçûâàåòñÿèñõîäíûõ àâòîìàòîâ, ñëåäóþùèì îáðàçîì: A1 × A2 = hQ1 × Q2 , A, δ, hq01 , q02 i, F1 × F2 i, ãäå ôóíêöèÿ ïåðåõîäà δ(hq1 , q2 i, a) =hδ1 (q1 , a), δ2 (q2 , a)i äëÿ ëþáûõ q1 ∈ Q1 , q2 ∈ Q2 , a ∈ A. Íåñëîæíî óáåäèòüñÿ â òîì,÷òî L(A1 × A2 ) = L(A1 ) ∩ L(A2 ).Çàìå÷àíèå.ïðÿìûì ïðîèçâåäåíèåìËþáîé êîíå÷íûé ÿçûê ÿâëÿåòñÿ àâòîìàòíûì.Äîêàçàòåëüñòâî.
à) Íåòðóäíî ïîñòðîèòü â ÿâíîì âèäå àâòîìàòû,Òåîðåìà 11.ðàñïîçíàþùèåÿçûêè ∅, {Λ}, {a}, ãäå a áóêâà.á) Èç (à) è òåîðåìû 10 (êîíêàòåíàöèÿ) ñëåäóåò, ÷òî ëþáîé ÿçûê âèäà {w}, ãäå w ñëîâî, ÿâëÿåòñÿ àâòîìàòíûì.â) Èç (á) è òåîðåìû 10 (îáúåäèíåíèå) ñëåäóåò, ÷òî ëþáîé íåïóñòîé êîíå÷íûé ÿçûêÿâëÿåòñÿ àâòîìàòíûì.Ïóñòü L àâòîìàòíûé ÿçûê. Òîãäà ñóùåñòâóåò n >1 òàêîå, ÷òî äëÿ ëþáîãî ñëîâà w ∈ L, ãäå |w| > n, ñóùåñòâóåò ïðåäñòàâëåíèå ââèäå w = xyz, ãäå y 6= Λ, |xy| 6 n è xyiz ∈ L äëÿ âñåõ i > 0.Äîêàçàòåëüñòâî. Ïóñòü A ä.ê.à. òàêîé, ÷òî L(A) = L, è ïóñòü n ÷èñëî ñîËåììà 12(î íàêà÷èâàíèè).ñòîÿíèé àâòîìàòà A. Ðàññìîòðèì ïðîèçâîëüíîå ñëîâî w ∈ L ñî ñâîéñòâîì |w| > n.Ñëåäîâàòåëüíî, ìîæíî ïðåäñòàâèòü w = s1 .
. . sn sn+1 . . . sm , ãäå si áóêâû. Òàê êàêw ðàñïîçíàåòñÿ àâòîìàòîì A, òî ñóùåñòâóåò ïóòü ïî äóãàì A, íà÷èíàþùèéñÿ â íà÷àëüíîì ñîñòîÿíèè, çàêàí÷èâàþùèéñÿ â âûäåëåííîì ñîñòîÿíèè, è âäîëü êîòîðîãî÷èòàåòñÿ ñëîâî w.s1 ...H ixq- i -. . .yq- i -. . .sn+1sn- i- . . . sm- idzÐàññìîòðèì ïåðâûå n ïåðåõîäîâ â ýòîì ïóòè, âäîëü êîòîðûõ ÷èòàþòñÿ ïåðâûå náóêâ ñëîâà w. Òàê êàê ÷èñëî ñîñòîÿíèé, ïðîéäåííûõ íà ýòîì ó÷àñòêå ïóòè, ðàâíîn + 1, òî ñóùåñòâóåò õîòÿ áû îäíî ñîñòîÿíèå q , êîòîðîå âñòðå÷àåòñÿ íå ìåíåå äâóõðàç.Ïóñòü x ÷àñòü ñëîâà s1 . . . sn , êîòîðàÿ ÷èòàåòñÿ îò íà÷àëüíîãî ñîñòîÿíèÿ äî ïåðâîãî ïîïàäàíèÿ â ñîñòîÿíèå q ; y ÷àñòü ñëîâà s1 .
. . sn , êîòîðàÿ ÷èòàåòñÿ îò ïåðâîãîïîïàäàíèÿ â ñîñòîÿíèå q äî ïîñëåäíåãî ïîïàäàíèÿ â ñîñòîÿíèå q ; z îñòàëüíàÿ ÷àñòüw (ñì. ðèñóíîê). Òîãäà y 6= Λ è |xy| 6 n. Êðîìå ýòîãî, ÷òåíèå ïîäñëîâà y íà÷èíàåòñÿ è çàêàí÷èâàåòñÿ â ñîñòîÿíèè q . Ñëåäîâàòåëüíî, ýòîò ó÷àñòîê ìîæíî óäàëèòü èçíàøåãî ïóòè èëè ïðîéòè ïî íåìó ïðîèçâîëüíîå êîëè÷åñòâî ðàç. Îòñþäà çàêëþ÷àåì,÷òî ñëîâî xy i z ∈ L(A) äëÿ âñåõ i > 0.26Ãëàâà II. Êîíå÷íûå àâòîìàòû è ôîðìàëüíûå ãðàììàòèêèÔîðìàëüíàÿ çàïèñü óòâåðæäåíèÿ ëåììû î íàêà÷èâàíèè èìååò äîñòàòî÷íî ñëîæíóþ ëîãè÷åñêóþ ñòðóêòóðó:Çàìå÷àíèå.∀L L àâòîìàòíûé −→ ∃n n > 1 & ∀w (w ∈ L & |w| > n) −→∃x, y, z(w = xyz & y 6= Λ & |xy| 6 n & ∀i(i > 0 → xy i z ∈ L)).Ñ òî÷íîñòüþ äî ýêâèâàëåíòíîñòè çàïèñàííàÿ âûøå ôîðìóëà èìååò êâàíòîðíóþ ïðèñòàâêó ∀L∃n∀w∃x, y, z∀i ñ ïÿòüþ ãðóïïàìè ÷åðåäóþùèõñÿ êâàíòîðîâ.
Âàæíî òàêæåïîìíèòü, ÷òî åñëè â ëîãè÷åñêîé ôîðìóëå âèäà Φ → Ψ ïîñûëêà Φ ëîæíà, òî íåçàâèñèìî îò çíà÷åíèÿ Ψ ôîðìóëà Φ → Ψ èñòèííà.  ÷àñòíîñòè, óòâåðæäåíèå ëåììû îíàêà÷èâàíèè îñòà¼òñÿ âåðíûì è äëÿ ñëîâ w ∈ L ñ óñëîâèåì |w| < n.Ñóùåñòâóþò íåàâòîìàòíûå ÿçûêè.Äîêàçàòåëüñòâî. Ðàññìîòðèì ÿçûê L = {ambm | m ∈ ω} íàä àëôàâèòîì {a, b}. ÄîïóÑëåäñòâèå 13.ñòèì, L àâòîìàòíûé. Ñëåäîâàòåëüíî, ñóùåñòâóåò n > 1 êàê â ëåììå î íàêà÷èâàíèè.Ðàññìîòðèì ñëîâî an bn ∈ L. Äëèíà |an bn | > n. Ñëåäîâàòåëüíî, ïî ëåììå ìîæíî ïðåäñòàâèòü an bn = xyz , ãäå y 6= Λ, |xy| 6 n è xy i z ∈ L äëÿ ëþáîãî i > 0.
Îòñþäà ñëåäóåò,÷òî ñóùåñòâóåò k > 1 òàêîå, ÷òî y = ak , è ñëîâî x íå ñîäåðæèò áóêâ b. Ñëåäîâàòåëüíî,ñëîâî xz = an−k bn ∈ L, ÷òî íåâîçìîæíî, ïîñêîëüêó n − k < n. Òàêèì îáðàçîì, L íåÿâëÿåòñÿ àâòîìàòíûì.Çàìå÷àíèå. Ëåììà î íàêà÷èâàíèè ÿâëÿåòñÿ íåîáõîäèìûì óñëîâèåì àâòîìàòíîñòèÿçûêà. Ýòî óñëîâèå ÿâëÿåòñÿ äîñòàòî÷íî ñèëüíûì è äåìîíñòðèðóåò îïðåäåë¼ííóþîãðàíè÷åííîñòü âû÷èñëèòåëüíûõ âîçìîæíîñòåé êîíå÷íûõ àâòîìàòîâ. Íàïðèìåð, êàêìû çàìåòèëè, íèêàêîé êîíå÷íûé àâòîìàò íå ñïîñîáåí ðàñïîçíàòü ÿçûê {am bm | m ∈ω}. Îäíàêî íåñëîæíî ïîñòðîèòü ôîðìàëüíóþ ãðàììàòèêó, êîòîðàÿ ïîðîæäàåò ýòîòÿçûê.
Äðóãèìè ñëîâàìè, íå ëþáóþ àëãîðèòìè÷åñêè ðàçðåøèìóþ çàäà÷ó ìîæíî ðåøèòü ñ ïîìîùüþ êîíå÷íûõ àâòîìàòîâ. Òåì íå ìåíåå, ÿçûê êîíå÷íûõ àâòîìàòîâ îêàçûâàåòñÿ äîñòàòî÷íûì äëÿ àëãîðèòìè÷åñêîãî îïèñàíèÿ ìíîãèõ âàæíåéøèõ êëàññîâçàäà÷ â ðàçëè÷íûõ ðàçäåëàõ ìàòåìàòèêè è ïðèëîæåíèÿõ. 8.Ðåãóëÿðíûå ÿçûêè ýòîì ïàðàãðàôå áóäåò ïðåäëîæåí äðóãîé ïîäõîä äëÿ îïèñàíèÿ êëàññà àâòîìàòíûõÿçûêîâ. Áóäåò äîêàçàíî, ÷òî àâòîìàòíûå ÿçûêè ýòî â òî÷íîñòè òå ÿçûêè, êîòîðûåèìåþò ¾ñèíòàêñè÷åñêîå¿ îïèñàíèå â òåðìèíàõ ðåãóëÿðíûõ âûðàæåíèé.Ïóñòü A êîíå÷íûé àëôàâèò, íå ñîäåðæàùèé ñèìâîëîâ (, ), ∪, ∗.Îïðåäåëèì ïî èíäóêöèè ìíîæåñòâîíàä àëôàâèòîì A:Îïðåäåëåíèå.ðåãóëÿðíûõ âûðàæåíèé10 . Ìíîæåñòâà ∅ è a, ãäå a ∈ A, ÿâëÿþòñÿ ðåãóëÿðíûìè âûðàæåíèÿìè.20 . Åñëè α è β ðåãóëÿðíûå âûðàæåíèÿ, òî (αβ), (α ∪ β) è (α∗ ) òîæå ÿâëÿþòñÿ.ðåãóëÿðíûìè âûðàæåíèÿìèÒàêèì îáðàçîì, ñëîâî â àëôàâèòå A∪{(, ), ∪, ∗ } íàçûâàåòñÿ ðåãóëÿðíûì âûðàæåíèåì,åñëè îíî ìîæåò áûòü ïîëó÷åíî êîíå÷íûì ÷èñëîì ïðèìåíåíèé ïóíêòîâ 10 è 20 .27 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
