Об отношении совместимости в исчислении Ламбека и в его варианте с операциями замещения (1104173), страница 15
Текст из файла (страница 15)
Àéäóêåâè÷åì âðàáîòå [3].  ðàáîòå [18] áûëî ââåäåíî ïîíÿòèå ãðàììàòèêè Ëàìáåêà,òî åñòü êàòåãîðèàëüíîé ãðàììàòèêè, îñíîâàííîé íà èñ÷èñëåíèè Ëàìáåêà L (äàëåå, L -ãðàììàòèêè). Èç ðåçóëüòàòîâ ðàáîòû [5] ñëåäóåò, ÷òîâñÿêèé êîíòåêñòíî-ñâîáîäíûé ÿçûê áåç ïóñòîãî ñëîâà ìîæåò áûòü ïîðîæä¼í íåêîòîðîé L-ãðàììàòèêîé. Îáðàòíûé ðåçóëüòàò, ïîêàçûâàþùèé,÷òî âñÿêèé ÿçûê, ïîðîæäàåìûé L-ãðàììàòèêîé, ÿâëÿåòñÿ êîíòåêñòíîñâîáîäíûì, áûë ïîëó÷åí Ì.
Ð. Ïåíòóñîì â [35], òàì æå äîêàçàí àíàëîãè÷íûé ðåçóëüòàò äëÿ èñ÷èñëåíèÿ L∗ . Îáðàòíîå âêëþ÷åíèå äëÿ èñ÷èñëåíèÿ L∗ ïîëó÷åíî C. Ë. Êóçíåöîâûì â ðàáîòå [17].  [17] òàêæå èññëåäîâàëèñü êëàññû ÿçûêîâ, ïîðîæäàåìûå ãðàììàòèêàìè, îñíîâàííûìè íàâàðèàíòàõ èñ÷èñëåíèÿ Ëàìáåêà. Íèæå ìû ïðèâåä¼ì îñíîâíûå îïðåäåëåíèÿ, ñâÿçàííûå ñ ïîíÿòèåì ãðàììàòèêè Ëàìáåêà.Îïðåäåëåíèå 6.3.Ãðàììàòèêîé Ëàìáåêà èëè L-ãðàììàòèêîé íàçû-âàåòñÿ òðîéêà G = hΣ, B, Hi, ãäå Σ êîíå÷íûé àëôàâèò, B êîíå÷íîåïîäìíîæåñòâî äåêàðòîâà ïðîèçâåäåíèÿ Σ × Tp, à H ∈ T p öåëåâîéòèï . ßçûê L(G), çàäàâàåìûé ãðàììàòèêîé G , îïðåäåëÿåòñÿ ðàâåíñòâîìL(G) = {a1 .
. . ar | ∃A1 , . . . Ar (∀j(aj B Aj ) ∧ L ` A1 . . . Ar → H)},91ãäå çàïèñü aj B Aj îçíà÷àåò (aj , Aj ) ∈ B. Åñëè çàìåíèòü â äàííîì îïðåäåëåíèè èñ÷èñëåíèå L íà L∗ , ïîëó÷èì îïðåäåëåíèå L∗ -ãðàììàòèêè.Ïðèìåð 6.7.L-ãðàììàòèêà G = hΣ, B, p/pi, ãäå B = {ha, (p/p)/pi,hb, pi} çàäà¼ò ÿçûê {w ∈ {a, b}+ | |w|a = |w|b , ∀u v w(|u|a > |u|b )},òî åñòü ÿçûê íåïóñòûõ ïðàâèëüíûõ ñêîáî÷íûõ ïîñëåäîâàòåëüíîñòåé ñîäíèì òèïîì ñêîáîê. Íàïðèìåð, ñëîâî aabb ïðèíàäëåæèò ýòîìó ÿçûêó,ïîñêîëüêó L ` ((p/p)/p)((p/p)/p)pp → p/p.Òåîðåìà 13(Í. Ãàéôìàí, 1960; Ì. Ð. Ïåíòóñ, 1995; C. Ë.
Êóçíåöîâ,2009).1. L -ãðàììàòèêàìè ïîðîæäàþòñÿ â òî÷íîñòè âñå êîíòåêñòíî-ñâîáîäíûå ÿçûêè, íå ñîäåðæàùèå ïóñòîãî ñëîâà.2. L∗ -ãðàììàòèêàìè ïîðîæäàþòñÿ â òî÷íîñòè âñå êîíòåêñòíî-ñâîáîäíûå ÿçûêè.Àíàëîãè÷íûì îáðàçîì ìîæíî ââåñòè ãðàììàòèêè, îñíîâàííûå íàèñ÷èñëåíèè Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ HDL.Îïðåäåëåíèå6.4.HDL-ãðàììàòèêîé íàçûâàåòñÿ òðîéêà G=hΣ, B, Hi, ãäå Σ êîíå÷íûé àëôàâèò, B êîíå÷íîå ïîäìíîæåñòâî äåêàðòîâà ïðîèçâåäåíèÿ Σ × Tp0D , íàçûâàåìîå ñëîâàð¼ì, à H ∈ Tp0D öåëåâîé òèï. ßçûê L(G), îïðåäåëÿåìûé ãðàììàòèêîé G , çàäà¼òñÿ ñîîòíîøåíèåìL(G) = {a1 .
. . ar | ∃A1 , . . . Ar ((∀j(aj B Aj )) ∧ HDL ` A1 · . . . · Ar → H)}.Âìåñòî èñ÷èñëåíèÿ HDL óäîáíî èñïîëüçîâàòü åãî ñåêâåíöèàëüíóþâåðñèþ DL. Ïîýòîìó äàëåå ìû áóäåì ðàññìàòðèâàòü ãðàììàòèêè, îñíîâàííûå íà èñ÷èñëåíèè Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ DL (ðàçðûâíûå ãðàììàòèêè Ëàìáåêà èëè DL -ãðàììàòèêè) è åãî ôðàãìåíòàõ DLk(DLk -ãðàììàòèêè). Äàííûå ãðàììàòèêè äåòàëüíî èçó÷àëèñü â ðàáîòàõ[23] è [24].
 ÷àñòíîñòè, [24] ñîäåðæèò ïðèìåðû àíàëèçà íåêîòîðûõ ñèíòàêñè÷åñêèõ ÿâëåíèé â åñòåñòâåííûõ ÿçûêàõ ñ ïîìîùüþ DL -ãðàììàòèê.92Âçàèìîñâÿçü ðàçðûâíûõ ãðàììàòèê Ëàìáåêà ñ äðóãèìè âàðèàíòàìè êàòåãîðèàëüíûõ ãðàììàòèê ðàññìàòðèâàåòñÿ â ìîíîãðàôèè [22].Îïðåäåëåíèå 6.5.Ðàçðûâíîé ãðàììàòèêîé Ëàìáåêà èëè DL -ãðàì-ìàòèêîé íàçûâàåòñÿ òðîéêà G = hΣ, B, Hi, ãäå Σ êîíå÷íûé àëôàâèò,B êîíå÷íîå ïîäìíîæåñòâî äåêàðòîâà ïðîèçâåäåíèÿ Σ × Tp0D , íàçûâàåìîå ñëîâàð¼ì, à H ∈ Tp0D öåëåâîé òèï. ßçûê L(G), çàäàâàåìûéãðàììàòèêîé G , îïðåäåëÿåòñÿ àíàëîãè÷íî ñëó÷àþ L -ãðàììàòèêè ñ çàìåíîé èñ÷èñëåíèÿ L íà DL, òî åñòüL(G) = {a1 . .
. ar | ∃A1 , . . . Ar (∀j(aj B Aj ) ∧ DL ` A1 . . . Ar → H)}.ÄàííîåîïðåäåëåíèåýêâèâàëåíòíîîïðåäåëåíèþHDL-ãðàììàòèêè. Åñëè â îïðåäåëåíèè 6.5 çàìåíèòü èñ÷èñëåíèå DL íàåãî ôðàãìåíò DLk äëÿ íåêîòîðîãî íàòóðàëüíîãî k , òî ìû ïîëó÷èìîïðåäåëåíèå DLk -ãðàììàòèêè. Çàìåòèì, ÷òî â ñèëó êîíå÷íîñòè ñëîâàðÿè ñâîéñòâà ïîäôîðìóëüíîñòè èñ÷èñëåíèÿ DL âñÿêàÿ DL -ãðàììàòèêàÿâëÿåòñÿ DLk -ãðàììàòèêîé äëÿ íåêîòîðîãî k .Ïðèìåðòèí,6.82011).Ïóñòü(Ã.Ìîððèëë,s(p1 )=Î.s(p2 )Âàëåí-=s(p3 )= 1, òîãäà DL1 -ãðàììàòèêà G = hΣ, B, p1 1 Ii ñî ñëîâàð¼ì a B p1 /p3 ,b B J \ p2 , b B J \(p1 ↓1 p2 ), c B p2 \ p3 ïîðîæäàåò ÿçûê {an bn cn | n > 0}.Ïðèâåä¼ííûé íèæå âûâîä ïîêàçûâàåò, ÷òî ñëîâî abc ïðèíàäëåæèò L(G).p2 → p2 [] → Jp3 → p3p1 → p 1[](J \ p2 ) → p2[](J \ p2 )(p2 \ p3 ) → p3(p1 /p3 )[](J \ p2 )(p2 \ p3 ) → p1(\ →)(\ →)(/ →)(p1 /p3 )(J \ p2 )(p2 \ p3 ) → p1 1 IΛ→I(→ )Ïîñêîëüêó âñå èñ÷èñëåíèÿ DLk ÿâëÿþòñÿ êîíñåðâàòèâíûìè ðàñøèðåíèÿìè èñ÷èñëåíèÿ L∗ , òî ïðè ëþáîì k âñÿêèé êîíòåêñòíî-ñâîáîäíûé ÿçûê ïîðîæäàåòñÿ íåêîòîðîé DLk -ãðàììàòèêîé.
Ïðèâåä¼ííûé âûøå ïðèìåð ïîêàçûâàåò, ÷òî óæå DL1 -ãðàììàòèêàìè ïîðîæäàþòñÿ íåêî93òîðûå ÿçûêè, íå ÿâëÿþùèåñÿ êîíòåêñòíî-ñâîáîäíûìè.  ðàáîòå [23] äîêàçàíî, ÷òî ñ ïîìîùüþ DL1 -ãðàììàòèê ïîðîæäàþòñÿ, â ÷àñòíîñòè, âñåÿçûêè, ïðåäñòàâèìûå â âèäå çàìûêàíèÿ àâòîìàòíîãî ÿçûêà îòíîñèòåëüíî ïåðåñòàíîâêè áóêâ â ñëîâàõ.6.3Êîíå÷íûå àâòîìàòû è çàäàâàåìûå èìè ÿçûêè ýòîì ðàçäåëå áóäóò ââåäåíû íåîáõîäèìûå îïðåäåëåíèÿ èç òåîðèè ôîðìàëüíûõ ÿçûêîâ, êàñàþùèåñÿ êîíå÷íûõ àâòîìàòîâ è çàäàâàåìîãî èìèêëàññà ôîðìàëüíûõ ÿçûêîâ.Îïðåäåëåíèå 6.6.Íåäåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì (äà-ëåå, êîíå÷íûì àâòîìàòîì ) íàçûâàåòñÿ êîðòåæ M = hΣ, Q, ∆, qs , F i,ãäå Σ êîíå÷íûé àëôàâèò, Q êîíå÷íîå ìíîæåñòâî ñîñòîÿíèé,∆ ⊆ Q × Σ∗ × Q êîíå÷íîå ìíîæåñòâî ïåðåõîäîâ âèäà (q1 , w) → q2 ,ãäå w íàçûâàåòñÿ ìåòêîé ïåðåõîäà, qs ∈ Q ñòàðòîâîå ñîñòîÿíèå, àF ⊆ Q ìíîæåñòâî çàâåðøàþùèõ ñîñòîÿíèé.Îïðåäåëåíèå 6.7.Êîíôèãóðàöèåé êîíå÷íîãî àâòîìàòà íàçûâàåòñÿ ïà-ðà hq, wi, q ∈ Q, w ∈ Σ∗ .
Ìíîæåñòâî êîíôèãóðàöèé àâòîìàòà M áóäåìîáîçíà÷àòü ÷åðåç CM . Îòíîøåíèåì äîñòèæèìîñòè â àâòîìàòå M íàçîâ¼ì íàèìåíüøåå ðåôëåêñèâíîå òðàíçèòèâíîå îòíîøåíèå →M ∈ CM × CM ,òàêîå ÷òî äëÿ êàæäîãî ïåðåõîäà (hq1 , ui → q2 ) ∈ ∆ è ïðîèçâîëüíîãî ñëîâà v ∈ Σ âûïîëíÿåòñÿ ñîîòíîøåíèå hq1 , uvi →M hq2 , vi. ßçûêL(M ), çàäàâàåìûé àâòîìàòîì, ñîñòîèò èç âñåõ ñëîâ w, òàêèõ ÷òî ñóùåñòâóåò çàâåðøàþùåå ñîñòîÿíèå q ∈ F , óäîâëåòâîðÿþùåå ñîîòíîøåíèþhqs , wi →M hq, εi.Îïðåäåëåíèå 6.8.Ïóñòü M = hΣ, Q, ∆, qs , F i êîíå÷íûé àâòîìàò,à w ∈ L(M ). Òîãäà ïîñëåäîâàòåëüíîñòü ñîñòîÿíèé qi0 = qs , qi1 , . .
. , qir ,ãäå qir ∈ F , íàçûâàåòñÿ ðàñïîçíàþùåé äëÿ ñëîâà w â àâòîìàòå M , åñëèñóùåñòâóåò ïðåäñòàâëåíèå w = wi1 . . . wir , òàêîå ÷òî äëÿ âñÿêîãî j 6 râûïîëíÿåòñÿ ñîîòíîøåíèå (hqij−1 , wij i → qij ) ∈ ∆.94Õîðîøî èçâåñòíî (ñì., íàïðèìåð, [2]), ÷òî åñëè ðàçðåøèòü â îïðåäåëåíèè àâòîìàòà òîëüêî îäíîáóêâåííûå ìåòêè ïåðåõîäîâ, òî êëàññ ðàñïîçíàâàåìûõ ÿçûêîâ íå èçìåíèòñÿ. Áîëåå òîãî, êàæäûé àâòîìàòíûéÿçûê, íå ñîäåðæàùèé ïóñòîãî ñëîâà, ìîæåò ðàñïîçíàâàòüñÿ êîíå÷íûìàâòîìàòîì ñ îäíîáóêâåííûìè ïåðåõîäàìè, èìåþùèì ðîâíî îäíî çàâåðøàþùåå ñîñòîÿíèå.
Çàìåòèì, ÷òî åñëè àâòîìàò M ñîäåðæèò òîëüêî îäíîáóêâåííûå ïåðåõîäû, òî âñÿêàÿ ðàñïîçíàþùàÿ ïîñëåäîâàòåëüíîñòü äëÿñëîâà w â àâòîìàòå M èìååò äëèíó |w| + 1.Êîíå÷íûå àâòîìàòû óäîáíî èçîáðàæàòü ãðàôè÷åñêè. Ñîñòîÿíèÿàâòîìàòà áóäåì îáîçíà÷àòü êðóæêàìè, ïðè ýòîì ñòàðòîâîå ñîñòîÿíèåáóäåì ïîìå÷àòü âõîäÿùåé â íåãî ñòðåëêîé, à çàâåðøàþùåå ñîñòîÿíèå äâîéíûì êðóæêîì. Ïåðåõîäû áóäåì èçîáðàæàòü ñòðåëêàìè, ñîåäèíÿþùèìè ñîñòîÿíèÿ, íà ñòðåëêå ïðè ýòîì íàïèñàíà ìåòêà ïåðåõîäà. Òàêèìîáðàçîì, êîíå÷íûé àâòîìàò ïðåäñòàâëÿåò ñîáîé ïîìå÷åííûé îðèåíòèðîâàííûé ãðàô, â êîòîðîì âûäåëåíû îòäåëüíûå âåðøèíû.Ïðèìåð 6.9.Ïðèâåä¼ííûé íà ðèñóíêå àâòîìàò ðàñïîçíà¼ò ÿçûê ñëîâäëèíû íå ìåíüøå 3, íà÷èíàþùèõñÿ ñ áóêâû a, â êîòîðûõ ïðåäïîñëåäíÿÿáóêâà ðàâíà b.a, bqsaq1bq2a, bq3Ïîñëåäîâàòåëüíîñòü ñîñòîÿíèé qs , q1 , q1 , q1 , q2 , q3 ÿâëÿåòñÿ ðàñïîçíàþùåéäëÿ ñëîâà ababa â äàííîì àâòîìàòå.6.4Ïåðåñå÷åíèå ñ àâòîìàòíûìè ÿçûêàìè: îïèñàíèåêîíñòðóêöèè ýòîé ãëàâå ìû äîêàæåì ñëåäóþùèé îñíîâíîé ðåçóëüòàò:95Òåîðåìà 14.Ìíîæåñòâî ÿçûêîâ, ðàñïîçíàâàåìûõ DL -ãðàììàòèêàìè,çàìêíóòî îòíîñèòåëüíî ïåðåñå÷åíèÿ ñ àâòîìàòíûìè ÿçûêàìè, íå ñîäåðæàùèìè ïóñòîãî ñëîâà.Äîêàçàòåëüñòâî çàìêíóòîñòè êëàññà ÿçûêîâ, ïîðîæäàåìûõ ãðàììàòèêàìè Ëàìáåêà, îòíîñèòåëüíî òåõ èëè èíûõ îïåðàöèé, ïðåäñòàâëÿåòçíà÷èòåëüíî áîëüøèå òðóäíîñòè â ñðàâíåíèè ñ àíàëîãè÷íîé çàäà÷åé äëÿêëàññîâ ÿçûêîâ, ïîðîæäàåìûõ òîé èëè èíîé ðàçíîâèäíîñòüþ ïîðîæäàþùèõ ãðàììàòèê.
Òàê, äëÿ ãðàììàòèê, îñíîâàííûõ íà èñ÷èñëåíèè L, âîñíîâíîì èñïîëüçóåòñÿ ýêâèâàëåíòíîñòü ìåæäó äàííûì êëàññîì ãðàììàòèê è êîíòåêñòíî-ñâîáîäíûìè ãðàììàòèêàìè. Îäíàêî ýòîò ìåòîä íåìîæåò áûòü ïðèìåí¼í â ñëó÷àå ãðàììàòèê, îñíîâàííûõ íà èñ÷èñëåíèèDL è åãî ôðàãìåíòàõ DLk , òàê êàê íà äàííûé ìîìåíò íåèçâåñòíî òî÷íîåîïèñàíèå êëàññà ÿçûêîâ, ïîðîæäàåìûõ DL -ãðàììàòèêàìè, â òåðìèíàõèåðàðõèè Õîìñêîãî.Ìû äîêàæåì, ÷òî êëàññ ÿçûêîâ, ïîðîæäàåìûõ DLk -ãðàììàòèêàìè, çàìêíóò îòíîñèòåëüíî ïåðåñå÷åíèÿ ñ àâòîìàòíûìè ÿçûêàìè, íåñîäåðæàùèìè ïóñòîãî ñëîâà.
Äëÿ ñëó÷àÿ k = 0 äàííûé ðåçóëüòàò ñëåäóåò èç ýêâèâàëåíòíîñòè L∗ -ãðàììàòèê è êîíòåêñòíî-ñâîáîäíûõ ãðàììàòèê(ñì. [35], [17]) è çàìêíóòîñòè êîíòåêñòíî-ñâîáîäíûõ ÿçûêîâ îòíîñèòåëüíî ïåðåñå÷åíèÿ ñ àâòîìàòíûìè ÿçûêàìè (ñì. [7]). Îäíàêî îïèñàííàÿ êîíñòðóêöèÿ èìååò ñóùåñòâåííûé íåäîñòàòîê, òàê êàê ïðåîáðàçîâàíèå ãðàììàòèêè Ëàìáåêà â ýêâèâàëåíòíóþ åé êîíòåêñòíî-ñâîáîäíóþ ãðàììàòèêóïðèâîäèò ê ýêñïîíåíöèàëüíîìó óâåëè÷åíèþ ðàçìåðà ãðàììàòèêè. Êàêñëåäñòâèå, êîíå÷íàÿ ãðàììàòèêà äëÿ ïåðåñå÷åíèÿ èñõîäíîãî ÿçûêà, çàäàâàåìîãî ãðàììàòèêîé Ëàìáåêà, ñ àâòîìàòíûì ÿçûêîì òàêæå èìååòýêñïîíåíöèàëüíûé ðàçìåð â ñðàâíåíèè ñ èñõîäíîé ãðàììàòèêîé.
 ñëó÷àå ïðèìåíåíèÿ íàøåé êîíñòðóêöèè èìååò ìåñòî ëèøü ïîëèíîìèàëüíîåóâåëè÷åíèå ðàçìåðà ãðàììàòèêè. Îñíîâíàÿ èäåÿ êîíñòðóêöèè çàèìñòâîâàíà èç äîêàçàòåëüñòâà çàìêíóòîñòè êîíòåêñòíî-ñâîáîäíûõ ÿçûêîâ îòíîñèòåëüíî ïåðåñå÷åíèÿ ñ àâòîìàòíûìè ÿçûêàìè â [7].96Ïóñòü ÿçûê L çàäà¼òñÿ íåêîòîðîé DL -ãðàììàòèêîé G = hΣ, B, Hi,à LR íåêîòîðûé àâòîìàòíûé ÿçûê, íå ñîäåðæàùèé ïóñòîãî ñëîâà.Ìîæíî ñ÷èòàòü, ÷òî LR çàäà¼òñÿ êîíå÷íûì àâòîìàòîì M = hΣ, Q,∆, qs , {qf }i ñ îäíèì çàâåðøàþùèì ñîñòîÿíèåì è îäíîáóêâåííûìè ïåðåõîäàìè.Ïîñòðîèì íîâóþ ãðàììàòèêó G 0 = hΣ, B0 , H 0 i, çàäàþùóþ ÿçûêL ∩ LR .
Áóäåì ñ÷èòàòü, ÷òî âñå ýëåìåíòû ìíîæåñòâà Q ïðèíàäëåæàòìíîæåñòâó Pr è èìåþò ñîðò 0, ïðè ýòîì îíè íå èñïîëüçóþòñÿ ïðè ïîñòðîåíèè òèïîâ ãðàììàòèêè G . Ïîëîæèì H 0 = (qs \ H) · qf . Ñëîâàðü B0îïðåäåëÿåòñÿ êàê B0 = {ha, (q1 \ A) · q2 i | a B A, (hq1 , ai → q2 ) ∈ ∆}. Âñëåäóþùåì ðàçäåëå ìû äîêàæåì, ÷òî äàííàÿ ãðàììàòèêà ïîðîæäàåò âòî÷íîñòè ÿçûê L ∩ LR .Ïðèìåð 6.10.Ðåãóëÿðíûé ÿçûê LR = {a2k+1 bl+1 cm | k, l, m ∈ N} ðàñ-ïîçíà¼òñÿ êîíå÷íûì àâòîìàòîì, èçîáðàæ¼ííûì íèæå.cbbaqsq1aq2Òîãäà ÿçûê {an bn cn | n ∈ N} ∩ LR = {a2k+1 b2k+1 c2k+1 | k ∈ N}ïîðîæäàåòñÿ ãðàììàòèêîé G 0 = h{a, b, c}, B0 , (qs \(AI))·q2 i, ãäå ñëîâàðüB0 ïðèâåä¼í íèæå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
