Iv_task6 (XPS13_s conflicted copy 2014-12-02) (1178903), страница 2
Текст из файла (страница 2)
Äàííàÿ ãðàììàòèêà ÿâëÿåòñÿ ðåãóëÿðíîé ïðàâîëèíåéíîé, òî åñòü ìû ìîæåì ïîñòðîèòü ÍÊÀ.5baSbS3aBaF2b aS1AbaA1aF1aS2Äàííûé àâòîìàò áûë ïîñòðîåí ïðåäëîæåííûì íà ñåìèíàðå àëãîðèòìîì.Çàäà÷à 3Ðàññìîòðèì ñëîâî w = abaaa.Ýòî ñëîâî âûâîäèòñÿ èç S äâóìÿ ñïîñîáàìè.S → abaA → abaaaS → abaaaS → abaA → abaaB → abaaaS → abaaa(8)Ãäå îáà âûâîäà ëåâîñòîðîííèå, òî åñòü ïî óïðàæíåíèþ 1 ãðàììàòèêà íåîäíîçíà÷íàÇàäà÷à 4Íå âåðíî, ïóñòü Γ çàäàíà ñëåäóþùèì îáðàçîì:S → aS1S → aS2S1 → aS2 → b(9)Äàííàÿ ãðàììàòèêà ÿâëÿåòñÿ ðåãóëÿðíîé ïðàâîëèíåéíîé.
 ÿçûêå äàííîé ãðàììàòèêè ñóùåñòâóåò äâà ñëîâà {aa, ab} è ïî îäíîìó âîçìîæíîìó âûâîäó äëÿ êàæäîãî, òàê êàê S1 , S2ðàñêðûâàþòñÿ òîëüêî â òåðìèíàëû. Òî åñòü ãðàììàòèêà îäíîçíà÷íà, òàê êàê äåðåâüÿ ðàçáîðà äëÿ êàæäîãî ñëîâà èç ãðàììàòèêè îäíîçíà÷íî îïðåäåëåíû. Îäíàêî àâòîìàò, ïîñòðîåííûé ïî äàííîé ãðàììàòèêå áóäåò ÿâëÿòüñÿ ÍÊÀ.  ñàìîì äåëå6aSS1aF1aS2bF2Çàäà÷à 5Íå âåðíî. ïóñòü Γ çàäàíà ñëåäóþùèì îáðàçîì:S → aSbS→ε(10)Äîêàæåì, ÷òî ÿçûê äàííîé ãðàììàòèêè ýòî L = {an bn |n > 0}.∀an bn , S ⇒ aSb ⇒ a2 Sbb ⇒∗ an Sbn ⇒ an bn ∈ L(Γ)Îáðàòíî, ïóñòü w âûâîäèìî ãðàììàòèêîé. Èíäóêöèÿ ïî äëèíå âûâîäà.• Áàçèñ.
Åñëè äëèíà âûâîäà ðàâíà åäèíèöå, òî âûâîä ìîæåò áûòü òîëüêî S ⇒ ε, ãäåïóñòîå ñëîâî ïðèíàäëåæèò ÿçûêó L.• Øàã. Ïóñòü âñå ñëîâà, âûâîäèìûå èç ãðàììàòèêè Γ è èìåþùèå äëèíó âûâîäà íåáîëåå ÷åì n − 1 ïðèíàäëåæàò L. Òîãäà ïåðâîé ïðîäóêöèåé ìîæåò áûòü ëèøü S ⇒ aSb,ãäå ïîääåðåâî íåòåðìèíàëà S â ïðàâîé ÷àñòè ïðîäóêöèè áóäåò èìåòü âûñîòó n − 1,òî åñòü âûâåäåííîå èç íåãî ñëîâî ïðèíàäëåæèò ÿçûêó ïî ïðåäïîëîæåíèþ èíäóêöèè.Ñëîâî âûâåäåííîå èç ïðàâîãî íåòåðìèíàëà áóäåò èìåòü âèä ak bk ∈ L, òîãäà a·ak bk ·b =ak+1 bk+1 ∈ L, òî åñòü ñëîâî, âûâåäåííîå èç ëåâîãî íåòåðìèíàëà òàêæå ïðèíàäëåæèòL.Ïðè ýòîì ÿçûê L íå ÿâëÿåòñÿ ðåãóëÿðíûì, ÷òî áûëî äîêàçàíî ðàíåå.Çàäà÷à 6Äëÿ êàæäîãî ðåãóëÿðíîãî ÿçûêà ñóùåñòâóåò ÄÊÀ, òîãäà ìû íåìíîãî ïðåîáðàçóåì åãî, ñäåëàâ âñå ïðèíèìàþùèå ñîñòîÿíèÿ íåïðèíèìàþùèìè, ñîçäàäèì ïðèíèìàþùåå ñîñòîÿíèÿ èñîçäàäèì òóäà ε-ïåðåõîäû èç áûâøèõ ïðèíèìàþùèõ ñîñòîÿíèé.
Ïîíÿòíî, ÷òî âñå ðàñïîçíàâàåìûå ñëîâà îñòàëèñü ðàñïîçíàâàåìûìè, à íåðàñïîçíàâàåìûå èìåþò òå æå êîíå÷íûåñîñòîÿíèÿ, òî åñòü òàêæå îñòàëèíü íåðàñïîçíàâàåìûìè. Ïóñòü {L, Lσ1 . . . Lσn } ⊂ REG. Ïîñòðîèì ÄÊÀ, ðàñïîçíàþùèé L è çàìåíÿåì êàæäûé σi -ïåðåõîä â àâòîìàòå L íà àâòîìàò Li á7ïðåîáðàçîâàííûé òàê, êàê óêàçàíî âûøå. Çàìåíà ïðîèñõîäèò òàêèì îáðàçîì, ÷òî âåðøèíà,îòêóäà ñîâåðøàåòñÿ ïåðåõîä ñîâïàäàåò ñ íà÷àëüíûì ñîñòîÿíèåì ïîäñòàâëÿåìîãî àâòîìàòà, à êîíå÷íàÿ âåðøèíà ñîâïàäàåò ñ åäèíñòâåííîé ïðèíèìàþùåé âåðøèíîé ïîäñòàâëÿåìîãîàâòîìàòà. Áûâøèé àâòîìàò îáîçíà÷èì A, ïðåîáðàçîâàííûé A0 .Ïóñòü w ∈ L, òîãäà ïîñëåäîâàòåëüíîñòü êîíôèãóðàöèé (q0 , w) ` (q1 , w[2, |w|) ` . .
. ` (qn , 0)Ãäå q0 . . . qn îáîçíà÷åíèÿ ñîñòîÿíèé, êîòîðûå ïðèíèìàåò àâòîìàò ðàñïîçíàâàÿ ñëîâî. Ïóñòüñîîòâåòñòâóþùèå âåðøèíû â íîâîì àâòîìàòå áóäóò òàêæå îáîçíà÷åíû, îñòàëüíûå ñîñòîÿíèÿ, âõîäÿùèå â ïîäàâòîìàòû ïîêà îáîçíà÷àòü íèêàê íå áóäåì.Ïîäñòàâèì âìåñòî êàæäîãî i-ãî ñèìâîëà â w ïðîèçâîëüíîå wi ∈ LΣi . w0 = w1 . .
. wn , òîãäà(w0 , q0 ) `∗ (w2 . . . wn , q1 )(11)òàê êàê ñëîâî w1 ïðèíèìàåòñÿ àâòîìàòîì ÿçûêà LΣ1 , òî åñòü ðàñïîçíàâàíèå çàêàí÷èâàåòñÿâ åäèíñòâåííîé ïðèíèìàþùåé âåðøèíå, êîòîðàÿ â ïðåîáðàçîâàííîì àâòîìàòå ñîâïàäàåò ñq1 . Íàõîäÿñü â ñîñòîÿíèè qi−1 ïîñëå ñ÷èòûâàíèÿ wi ∈ LΣi àâòîìàò ïðèìåò ñîñòîÿíèå qi ïîàíàëîãè÷íîé ïðè÷èíå. Ñëåäîâàòåëüíî,(w0 , q0 ) `∗ (w2 . . . wn , q1 ) `∗ . . . `∗ (ε, qn )(12)Òî åñòü w0 ïðèíèìàåòñÿ ïðåîáðàçîâàííûì àâòîìàòîì àâòîìàòîì.
Ïóñòü L0 ÿçûê, ðàñïîçíàâàåìûé ïðåîáðàçîâàííûì àâòîìàòîì. Òàê êàê w, w1 . . . wn âûáðàíû ïðîèçâîëüíî, òî ∀w ∈L, Lw[1] Lw[2]...Lw[|w|] ⊂L0 , òî åñòü äàííûé ÿçûê ÿâëÿåòñÿ ïîäñòàíîâêîé â L ÿçûêîâ LΣ1 . . . LΣn .Òàê àâòîìàò äëÿ ÿçûêà L0 ñóùåñòâóåò, òî L0 ðåãóëÿðåí, ÷òî è òðåáîâàëîñü äîêàçàòü.Çàäà÷à 7Ïðîåêöèÿ ÿçûêà íà, íàïðèìåð, Σ∗ ÿâëÿåòñÿ ìîðôèçìîì, òàê êàê (a, b) · (c, d) = (ac, bd) èf (a, b)·f (c, d) = ac = f (ac, bd), ãäå a, c ∈ Σ∗ , b, d ∈ Delta∗ , f - îòîáðàæåíèå. Ðåãóëÿðíûå ÿçûêè çàìêíóòû îòíîñèòåëüíî ìîðôèçìà, ñëåäñòâåííî, òàê êàê ïðîåêöèÿ ÿâëÿåòñÿ ìîðôèçìîì(äîêàçàíî â çàäàíèè 4), òî ðåãóëÿðíûå ÿçûêè çàìêíóòû îòíîñèòåëüíî ïðîåêöèé.Çàäà÷à 8Çàäà÷à 9Äîêàæåì ïî èíäóêöèè, ÷òî ëþáàÿ ïðàâèëüíàÿ ñêîáî÷íàÿ ïîñëåäîâàòåëüíîñòü âûâîäèìà.Ïðè äîêàçàòåëüñòâå ýòîãî ôàêòà áóäåì ïîëüçîâàòüñÿ î÷åâèäíûì ñâîéñòâîì ÷åòíîñòè êîëè÷åñòâà ñèìâîëîâ â ïðàâèëüíîé ñêîáî÷íîé ïîñëåäîâàòåëüíîñòè.
Ýòî ñëåäóåò èç òîãî, ÷òî ñ8êàæäûì íîâûì ñèìâîëîì ñêîáî÷íûé èòîã ìåíÿåò ÷åòíîñòü, ïðè ýòîì ñ ïîñëåäíèì ñèìâîëîì ñòàíîâèòñÿ íóëåì ÷åòíûì ÷èñëîì, òî åñòü îí ìåíÿë ÷åòíîñòü ÷åòíîå ÷èñëî ðàç, òîåñòü êîëè÷åñòâî ñèìâîëîâ ÷åòíîå.• Áàçèñ. Ïðàâèëüíûå ñêîáî÷íûå ïîñëåäîâàòåëüíîñòè äëèí 0 è 2 âûâîäèìû, òàê êàêS ∈ ε è S ∈ aSb ∈ ab. Áîëåå ïðàâèëüíûõ ñêîáî÷íûõ ïîñëåäîâàòåëüíîñòåé äëèíû 2íåò, òàê êàê â ïîñëåäîâàòåëüíîñòè äîëæíà áûòü îòêðûâàþùàÿ è çàêðûâàþùàÿ ñêîáêà,à ba íåïðàâèëüíàÿ ïîñëåäîâàòåëüíîñòü• Øàã.
Ïóñòü ïðàâèëüíûå ñêîáî÷íûå ïîñëåäîâààòåëüíîñòè äëèíû 2(n − 1) âûâîäèìû,òîãäà ðàññìîòðèì ÏÑÊ äëèíû 2n. Ïåðâûé ñèìâîë îòêðûâàþùàÿñÿ ñêîáêà, òîãäàïóñòü k - èíäåêñ ïåðâîãî ñèìâîëà ñî ñêîáî÷íûì èòîãîì 0. Åñëè k -é ñèìâîë ïîñëåäíèé, òî ðàññìîòðèì Q1 = w[2, k − 1], â ïðîòèâíîì ñëó÷àå ðàññìîòðèì Q2 = w[1, k] èQ3 = w[k + 1, |w|]. Âñå òðè ïîäïîñëåäîâàòåëüíîñòè ÿâëÿþòñÿ ïðàâèëüíûìè ñêîáî÷íûìè ïîñëåäîâàòåëüíîñòÿìè. Òàê êàê â ïåðâîì ñëó÷àå ñêîáî÷íûé èòîã íå îïóñêàåòñÿ äîïîñëåäíåãî ñèìâîëà íèæå åäèíèöû, à âî âòîðîì ñëó÷àå ñêîáî÷íûé èòîã íå îïóñêàåòñÿíèæå íóëÿ äëÿ ïåðâîãî è âòîðîãî ïîäñëîâ. Ïðè ýòîì, äëèíû ýòèõ ñëîâ ìåíåå 2n, òîåñòü íå áîëåå 2(n − 1), òî åñòü îíè âûâîäèìû â äàííîé ãðàììàòèêå. ñëó÷àå Q1 èìååì S ⇒ aQ1 b ⇒ aw[2, k − 1]b = w ñëó÷àå Q2 , Q3 èìååì S ⇒ Q2 Q3 ⇒ w[1, k]Q2 ⇒ w[1, k]w[k + 1, |w|] = wÒî åñòü ïðàâèëüíàÿ ñêîáî÷íàÿ ïîñëåäîâàòåëüíîñòü äëèíû 2n òàêæå âûâîäèìà.Òàêèì îáðàçîì ìû ïîëó÷èëè, ÷òî ñêîáî÷íàÿ ïîñëåäîâàòåëüíîñòü ïðîèçâîëüíîé äëèíû âûâîäèìà â ðàìêàõ ïðàâîé ãðàììàòèêè, ÷òî è òðåáîâàëîñü äîêàçàòü.Çàäà÷à 10Íå ÿâëÿþòñÿ, òàê êàê ñëîâî ab ìîæåò áûòü âûâåäåíî êàêS ⇒ SS ⇒ S ⇒ aSb ⇒ abèëè êàêS ⇒ aSb ⇒ abÎáà âûâîäà ÿâëÿþòñÿ ëåâûìè, òî åñòü ïî óòâåðæäåíèþ, äîêàçàííîìó â óïðàæíåíèè äâàäàííàÿ ãðàììàòèêà íå ÿâëÿåòñÿ îäíîçíà÷íîé.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
