В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 4
Текст из файла (страница 4)
Êîíå÷íî, åñëè x íå ïðèíàäëåæèò L, ïðîöåäóðà íèêîãäà íå çàêîí÷èòñÿ.ßçûê, ïðåäëîæåíèÿ êîòîðîãî ìîãóò áûòü ñãåíåðèðîâàíû ïðîöåäóðîé, íàçûâàåòñÿ ðåêóðñèâíî ïåðå÷èñëèìûì.ßçûê ðåêóðñèâíî ïåðå÷èñëèì, åñëè èìååòñÿ ïðîöåäóðà, ðàñïîçíàþùàÿ ïðåäëîæåíèÿ ÿçûêà. Ãîâîðÿò, ÷òî ÿçûê ðåêóðñèâåí, åñëè ñóùåñòâóåò àëãîðèòì äëÿ ðàñïîçíàâàíèÿ ÿçûêà.Êëàññ ðåêóðñèâíûõ ÿçûêîâ ÿâëÿåòñÿ ñîáñòâåííûì ïîäìíîæåñòâîì êëàññà ðåêóðñèâíî ïåðå÷èñëèìûõ ÿçûêîâ.
Ìàëîòîãî, ñóùåñòâóþò ÿçûêè, íå ÿâëÿþùèåñÿ äàæå ðåêóðñèâíîïåðå÷èñëèìûìè.2.3. Ãðàììàòèêè2.3.1. Ôîðìàëüíîå îïðåäåëåíèå ãðàììàòèêèÄëÿ íàñ íàèáîëüøèé èíòåðåñ ïðåäñòàâëÿåò îäíà èç ñèñòåì ãåíåðàöèè ÿçûêîâ ãðàììàòèêè. Ïîíÿòèå ãðàììàòèêè èçíà÷àëüíî áûëî ôîðìàëèçîâàíî ëèíãâèñòàìè ïðè èçó÷åíèè åñòåñòâåííûõ ÿçûêîâ.
Ïðåäïîëàãàëîñü, ÷òî ýòî ìîæåò ïîìî÷ü ïðè èõ àâòîìàòè÷åñêîé òðàíñëÿöèè. Îäíàêî,íàèëó÷øèå ðåçóëüòàòû â ýòîì íàïðàâëåíèè äîñòèãíóòû ïðèîïèñàíèè íå åñòåñòâåííûõ ÿçûêîâ, à ÿçûêîâ ïðîãðàììèðîâàíèÿ. Ïðèìåðîì ìîæåò ñëóæèòü ñïîñîá îïèñàíèÿ ñèíòàêñèñà ÿçûêîâ ïðîãðàììèðîâàíèÿ ïðè ïîìîùè ÁÍÔ ôîðìûÁýêóñà-Íàóðà.Îïðåäåëåíèå. Ãðàììàòèêà(N ,T ,P ,S), ãäåýòî÷åòâ¼ðêàG=Ãðàììàòèêè21(1) N àëôàâèò íåòåðìèíàëüíûõ ñèìâîëîâ;(2) T àëôàâèò òåðìèíàëüíûõ ñèìâîëîâ, N ∩ T = ∅;(3) P êîíå÷íîå ìíîæåñòâî ïðàâèë âèäà α → β , ãäå α ∈(N ∪ T )∗ N (N ∪ T )∗ , β ∈ (N ∪ T )∗ ;(4) S ∈ N íà÷àëüíûé çíàê (èëè àêñèîìà) ãðàììàòèêè.Ìû áóäåì èñïîëüçîâàòü áîëüøèå ëàòèíñêèå áóêâû äëÿîáîçíà÷åíèÿ íåòåðìèíàëüíûõ ñèìâîëîâ, ìàëûå ëàòèíñêèåáóêâû èç íà÷àëà àëôàâèòà äëÿ îáîçíà÷åíèÿ òåðìèíàëüíûõñèìâîëîâ, ìàëûå ëàòèíñêèå áóêâû èç êîíöà àëôàâèòà äëÿîáîçíà÷åíèÿ öåïî÷åê èç T ∗ è, íàêîíåö, ìàëûå ãðå÷åñêèåáóêâû äëÿ îáîçíà÷åíèÿ öåïî÷åê èç (N ∪ T )∗ .Áóäåì èñïîëüçîâàòü òàêæå ñîêðàù¼ííóþ çàïèñü A →α1 |α2 | .
. . |αn äëÿ îáîçíà÷åíèÿ ãðóïïû ïðàâèë A → α1 , A →α2 , . . . , A → αn .Îïðåäåëèì íà ìíîæåñòâå (N ∪ T )∗ áèíàðíîå îòíîøåíèåâûâîäèìîñòè ⇒ ñëåäóþùèì îáðàçîì: åñëè δ → γ ∈ P , òîαδβ ⇒ αγβ äëÿ âñåõ α, β ∈ (N ∪ T )∗ . Åñëè α1 ⇒ α2 , òîãîâîðÿò, ÷òî öåïî÷êà α2 íåïîñðåäñòâåííî âûâîäèìà èç α1 .Ìûáóäåìèñïîëüçîâàòüòàêæåðåôëåêñèâíîòðàíçèòèâíîå è òðàíçèòèâíîå çàìûêàíèÿ îòíîøåíèÿ⇒, à òàêæå åãî ñòåïåíü k > 0 (îáîçíà÷àåìûå ñîîòâåòñòâåííî ⇒∗ , ⇒+ è ⇒k ). Åñëè α1 ⇒∗ α2 (α1 ⇒+ α2 , α1 ⇒k α2 ),òî ãîâîðÿò, ÷òî öåïî÷êà α2 âûâîäèìà (íåòðèâèàëüíîâûâîäèìà, âûâîäèìà çà k øàãîâ) èç α1 .Åñëè α ⇒k β (k > 0), òî ñóùåñòâóåò ïîñëåäîâàòåëüíîñòüøàãîâγ0 ⇒ γ1 ⇒ γ2 ⇒ .
. . ⇒ γk−1 ⇒ γkãäå α = γ0 è β = γk . Ïîñëåäîâàòåëüíîñòü öåïî÷åêγ0 , γ1 , γ2 , . . . , γk â ýòîì ñëó÷àå íàçûâàþò âûâîäîì β èç α.Ñåíòåíöèàëüíîé ôîðìîé ãðàììàòèêè G íàçûâàåòñÿ öåïî÷êà, âûâîäèìàÿ èç å¼ íà÷àëüíîãî ñèìâîëà.ßçûêîì, ïîðîæäàåìûì ãðàììàòèêîé G (îáîçíà÷àåòñÿL(G)), íàçûâàåòñÿ ìíîæåñòâî âñåõ å¼ òåðìèíàëüíûõ ñåíòåíöèàëüíûõ ôîðì, òî åñòüL(G) = {w|w ∈ T ∗ , S ⇒+ w}22Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèåÃðàììàòèêè G1 è G2 íàçûâàþòñÿ ýêâèâàëåíòíûìè, åñëè îíè ïîðîæäàþò îäèí è òîò æå ÿçûê, òî åñòü L(G1 ) =L(G2 ).Ïðèìåð 2.5. Ãðàììàòèêà G = ({S, B, C}, {a, b, c}, P, S),ãäå P = {S → aSBC , S → aBC , CB → BC , aB → ab, bB →bb, bC → bc, cC → cc}, ïîðîæäàåò ÿçûê L(G) = {an bn cn |n > 0}.Äåéñòâèòåëüíî, ïðèìåíÿåì n − 1 ðàç ïðàâèëî 1 è ïîëó÷àåìan−1 S(BC)n−1 , çàòåì îäèí ðàç ïðàâèëî 2 è ïîëó÷àåì an (BC)n ,çàòåì n(n − 1)/2 ðàç ïðàâèëî 3 è ïîëó÷àåì an B n C n .Çàòåì èñïîëüçóåì ïðàâèëî 4 è ïîëó÷àåì an bB n−1 C n .
Çàòåìïðèìåíÿåì n−1 ðàç ïðàâèëî 5 è ïîëó÷àåì an bn C n . Çàòåì ïðèìåíÿåì ïðàâèëî 6 è n − 1 ðàç ïðàâèëî 7 è ïîëó÷àåì an bn cn . Ìîæíîïîêàçàòü, ÷òî ÿçûê L(G) ñîñòîèò èç öåïî÷åê òîëüêî òàêîãî âèäà.Ïðèìåð 2.6. Ðàññìîòðèì ãðàììàòèêó G = ({S},{0, 1},{S → 0S1, S → 01}, S). Ëåãêî âèäåòü, ÷òî öåïî÷êà 000111 ∈L(G), òàê êàê ñóùåñòâóåò âûâîäS ⇒ 0S1 ⇒ 00S11 ⇒ 000111Íåòðóäíî ïîêàçàòü, ÷òî ãðàììàòèêà ïîðîæäàåò ÿçûê L(G) ={0n 1n |n > 0}.Ïðèìåð 2.7. Ðàññìîòðèì ãðàììàòèêó G = ({S, A},{0, 1},{S → 0S , S → 0A, A → 1A, A → 1}, S).
Íåòðóäíî ïîêàçàòü,÷òî ãðàììàòèêà ïîðîæäàåò ÿçûê L(G) = {0n 1m |n, m > 0}.2.3.2. Òèïû ãðàììàòèê è èõ ñâîéñòâàÐàññìîòðèì êëàññèôèêàöèþ ãðàììàòèê (ïðåäëîæåííóþÍ.Õîìñêèì), îñíîâàííóþ íà âèäå èõ ïðàâèë.Îïðåäåëåíèå. Ïóñòü äàíà ãðàììàòèêà G = (N, T, P, S).Òîãäà(1) åñëè ïðàâèëà ãðàììàòèêè íå óäîâëåòâîðÿþò íèêàêèìîãðàíè÷åíèÿì, òî å¼ íàçûâàþò ãðàììàòèêîé òèïà 0,èëè ãðàììàòèêîé áåç îãðàíè÷åíèé.(2) åñëèÃðàììàòèêè23à) êàæäîå ïðàâèëî ãðàììàòèêè, êðîìå S → e, èìååòâèä α → β , ãäå |α| 6 |β|, èá) â òîì ñëó÷àå, êîãäà S → e ∈ P , ñèìâîë S íåâñòðå÷àåòñÿ â ïðàâûõ ÷àñòÿõ ïðàâèë,òî ãðàììàòèêó íàçûâàþò ãðàììàòèêîé òèïà 1, èëèíåóêîðà÷èâàþùåé èëè êîíòåêñòíî-çàâèñèìîé (ÊÇãðàììàòèêîé) èëè êîíòåêñòíî - ÷óâñòâèòåëüíîé(Ê×-ãðàììàòèêîé).(3) åñëè êàæäîå ïðàâèëî ãðàììàòèêè èìååò âèä A →β , ãäå A ∈ N , β ∈ (N ∪ T )∗ , òî å¼ íàçûâàþòãðàììàòèêîé òèïà 2, èëè êîíòåêñòíî-ñâîáîäíîé (ÊÑãðàììàòèêîé).(4) åñëè êàæäîå ïðàâèëî ãðàììàòèêè èìååò âèä ëèáî A →xB , ëèáî A → x, ãäå A, B ∈ N , x ∈ T ∗ òî å¼ íàçûâàþòãðàììàòèêîé òèïà 3, èëè ïðàâîëèíåéíîé.Ëåãêî âèäåòü, ÷òî ãðàììàòèêà â ïðèìåðå 2.5 íåóêîðà÷èâàþùàÿ, â ïðèìåðå 2.6 êîíòåêñòíî-ñâîáîäíàÿ, â ïðèìåðå 2.7 ïðàâîëèíåéíàÿ.ßçûê, ïîðîæäàåìûé ãðàììàòèêîé òèïà i, íàçûâàþòÿçûêîì òèïà i.
ßçûê òèïà 0 íàçûâàþò òàêæå ÿçûêîì áåçîãðàíè÷åíèé, ÿçûê òèïà 1 êîíòåêñòíî-çàâèñèìûì (ÊÇ),ÿçûê òèïà 2 êîíòåêñòíî-ñâîáîäíûì (ÊÑ), ÿçûê òèïà 3 ïðàâîëèíåéíûì.Òåîðåìà 2.1. Êàæäûé êîíòåêñòíî-ñâîáîäíûé ÿçûêìîæåòáûòüïîðîæä¼ííåóêîðà÷èâàþùåéêîíòåêñòíî-ñâîáîäíîé ãðàììàòèêîé.Äîêàçàòåëüñòâî. Ïóñòü L êîíòåêñòíî-ñâîáîäíûé ÿçûê.Òîãäà ñóùåñòâóåò êîíòåêñòíî-ñâîáîäíàÿ ãðàììàòèêà G =(N, T, P, S), ïîðîæäàþùàÿ L.Ïîñòðîèì íîâóþ ãðàììàòèêó G0 = (N 0 , T, P 0 , S 0 ) ñëåäóþùèì îáðàçîì:1. Åñëè â P åñòü ïðàâèëî âèäà A → α0 B1 α1 . . . Bk αk , ãäåk > 0, Bi ⇒+ e äëÿ 1 6 i 6 k , è íè èç îäíîé öåïî÷êè αj24Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèå(0 6 j 6 k ) íå âûâîäèòñÿ e, òî âêëþ÷èòü â P 0 âñå ïðàâèëà(êðîìå A → e) âèäàA → α0 X1 α1 . .
. Xk αkãäå Xi ýòî ëèáî Bi , ëèáî e.2. Åñëè S ⇒+ e, òî âêëþ÷èòü â P 0 ïðàâèëà S 0 → S ,0S → e è ïîëîæèòü N 0 = N ∪ {S 0 }.  ïðîòèâíîì ñëó÷àåïîëîæèòü N 0 = N è S 0 = S .Ïîðîæäàåò ëè ãðàììàòèêà ïóñòóþ öåïî÷êó ìîæíî óñòàíîâèòü ñëåäóþùèì ïðîñòûì àëãîðèòìîì:Øàã 1. Ñòðîèì ìíîæåñòâî N0 = {N |N → e}Øàã 2. Ñòðîèì ìíîæåñòâî Ni = Ni−1 ∪ {N |N → α, α ∈{Ni−1 }∗ }Øàã 3.
Åñëè Ni = Ni−1 , ïåðåéòè ê øàãó 4, èíà÷å øàã 2.Øàã 4. Åñëè S ∈ Ni , çíà÷èò S →∗ e.Ëåãêî âèäåòü, ÷òî G0 íåóêîðà÷èâàþùàÿ ãðàììàòèêà.Ìîæíî ïîêàçàòü ïî èíäóêöèè, ÷òî L(G0 ) = L(G).Ïóñòü Ki êëàññ âñåõ ÿçûêîâ òèïà i. Äîêàçàíî, ÷òî ñïðàâåäëèâî ñëåäóþùåå (ñòðîãîå) âêëþ÷åíèå: K3 ⊂ K2 ⊂ K1 ⊂K0 .Çàìåòèì, ÷òî åñëè ÿçûê ïîðîæäàåòñÿ íåêîòîðîé ãðàììàòèêîé, ýòî íå îçíà÷àåò, ÷òî îí íå ìîæåò áûòü ïîðîæä¼íãðàììàòèêîé ñ áîëåå ñèëüíûìè îãðàíè÷åíèÿìè íà ïðàâèëà.Ïðèâîäèìûé íèæå ïðèìåð èëëþñòðèðóåò ýòîò ôàêò.Ïðèìåð 2.8.
Ðàññìîòðèì ãðàììàòèêó G = ({S, A, B},{0, 1}, {S → AB , A → 0A, A → 0, B → 1B , B → 1}, S).Ýòà ãðàììàòèêà ÿâëÿåòñÿ êîíòåêñòíî-ñâîáîäíîé. Ëåãêî ïîêàçàòü, ÷òî L(G) = {0n 1m |n, m > 0}. Îäíàêî, â ïðèìåðå 2.7 ïðèâåäåíà ïðàâîëèíåéíàÿ ãðàììàòèêà, ïîðîæäàþùàÿ òîò æå ÿçûê.Íèæå ïðèâîäÿòñÿ ïîäðîáíûå ïðèìåðû ðåøåíèÿ äâóõïðàêòè÷åñêè èíòåðåñíûõ áîëåå ñëîæíûõ çàäà÷ íà ïîñòðîåíèå ÊÑ- è ÍÑ-ãðàììàòèê.Ïðèìåð 2.9. Äàííûé ïðèìåð îòíîñèòñÿ ê íåñêîëüêî ïàðàäîêñàëüíîé äëÿ ãðàììàòèê ïîñòàíîâêå: ïîñòðîèòü ÊÑãðàììàòèêó, ïîðîæäàþùóþ ÿçûê:{{a, b}∗ \ an bm an bm | n, m > 1},Ãðàììàòèêè25ò.å. ïîñòðîèòü âñå öåïî÷êè êðîìå óêàçàííûõ (îáû÷íî-òî ãîâîðÿòî òîì, ÷òî íàäî ïîñòðîèòü). Íî, ìîæåò áûòü, â òàêîé ïîñòàíîâêåçàëîæåíà è ïîäñêàçêà ê ðåøåíèþ? Èçâåñòíî, ÷òî èíûå çàäà÷è ñïîäîáíûìè òðåáîâàíèÿìè òàê è ðåøàþòñÿ: íóæíî ñäåëàòü âñ¼,¾÷òî íå íàäî¿, à ïîòîì îòêëîíèòüñÿ îò ýòîãî ¾íå íàäî¿ âñåìèâîçìîæíûìè ñïîñîáàìè.Îäíàêî âîîäóøåâë¼ííûõ ïîñòðîåíèåì â ðàìêàõ ÊÑãðàììàòèêè öåïî÷åê âèäà {an bm an bm } (çäåñü è äàëåå â ýòîìïðèìåðå n, m, k, l, j > 1) æä¼ò íåêîòîðîå ðàçî÷àðîâàíèå.
Äåéñòâèòåëüíî, â îòëè÷èå îò òàêèõ ñëó÷àåâ, êàê {an bn am bm },{an bm am bn }, {an bm bn am } è ò.ï., îáå çàâèñèìîñòè (ïî n è ïî m)ïðèä¼òñÿ îòñëåæèâàòü îäíîâðåìåííî è èç äâóõ ðàçíûõ öåíòðîâïîðîæäåíèÿ, ê ÷åìó ÊÑ-ãðàììàòèêè ïî ñâîåé ïðèðîäå (âèäó ñâîèõ ïðàâèë) îêàçûâàþòñÿ íå ïðåäíàçíà÷åíû.Ïîïðîáóåì òîãäà ïåðåñêàçàòü óñëîâèå çàäà÷è â êîíñòðóêòèâíîì (ñîçèäàòåëüíîì) ïëàíå, ò.å. îáîçíà÷àÿ ëèøü òî, ÷òî íàìíóæíî ïîñòðîèòü, à íå íàîáîðîò.
Ïîíà÷àëó òàêîå ìíîæåñòâîöåïî÷åê êàæåòñÿ íåîáîçðèìûì. Íî ïîïðîáóåì, ¾Äîðîãó îñèëèòèäóùèé¿!Íà÷í¼ì ñ î÷åâèäíûõ ñëó÷àåâ:{an }, {bn }, {an bm }, {bn am }, {an bm ak }, {bn am bk }...Îäíàêî áåñêîíå÷íî ïðîäîëæàòü â äóõå {bn am bk al bj } óæå êàêòî ñêó÷íî. Çàìå÷àåì, ÷òî b{a, b}∗ âïîëíå êîíå÷íûì îáðàçîìîïðåäåëÿåò ïîëîâèíó èç óïîìÿíóòûõ áåñ÷èñëåííûõ îïèñàíèé,à â ñëåäóþùèé ìîìåíò ñèììåòðèÿ íàì ïîäñêàçûâàåò è ÿçûê{a, b}∗ a.Òàêèì îáðàçîì, âñå öåïî÷êè âûøåïåðå÷èñëåííûõ âèäîâóêëàäûâàþòñÿ â òðè ñëó÷àÿ:{an bm }, b{a, b}∗ , {a, b}∗ a.Äàëåå ðàññìîòðèì ñëó÷àé {an bm ak bl | n 6= k èëè m 6= l}.
Íî÷òî òàêîå, ê ïðèìåðó, n 6= k? Òî æå ñàìîå, ÷òî îáúåäèíåíèå óñëîâèé n > k è n < k ! È çäåñü ïåðåøëè ê êîíñòðóêòèâó, êîòîðûéíåñëîæíî ñòðîèòñÿ â ðàìêàõ ÊÑ-ãðàììàòèêè.Îñòà¼òñÿ åäèíñòâåííûé íåóïîìÿíóòûé ñëó÷àé:{an bm ak bl }a{a, b}∗ .Âñïîìèíàÿ, ÷òî îáúåäèíåíèå ÊÑ-ÿçûêîâ åñòü ÊÑ-ÿçûê, ïîëó÷àåì èñêîìîå ðåøåíèå çàäà÷è.26Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèåÒàê, åñëè ÿçûê {an bm } ìîæåò áûòü ïîðîæä¼í ãðàììàòèêîéS1 → ABA → aA | aB → bB | b,à ÿçûê b {a, b}∗ - ãðàììàòèêîéS2 → bCC → CC | a | b | ε,òî äëÿ îáúåäèíåíèÿ ýòèõ ÿçûêîâ (â îáùåì ñëó÷àå èñïîëüçóþùèõêàæäûé ñâîé íåïîâòîðèìûé íàáîð âñïîìîãàòåëüíûõ çíàêîâ) äîñòàòî÷íî äîáàâèòü ïðàâèëî çàïóñêà èç íîâîé îáùåé àêñèîìû:S → S1 | S2 .Ïðèìåð 2.10.
Ïîñòðîåíèå ÍÑ-ãðàììàòèêè.Ãðàììàòèêè íåïîñðåäñòâåííûõ ñîñòàâëÿþùèõ (èëè, êðàòêî,ÍÑ-ãðàììàòèêè) åñòü âèä ïðåäñòàâëåíèÿ êîíòåêñòíî-çàâèñèìûõãðàììàòèê, ò.å. îíè îáëàäàþò òåìè æå âûðàçèòåëüíûìè âîçìîæíîñòÿìè, ÷òî è ÊÇ-ãðàììàòèêè â öåëîì. Êàæäîå ïðàâèëî ÍÑãðàììàòèêè äîëæíî ñîîòâåòñòâîâàòü âèäó:ϕAψ → ϕηψ, (|η| > 1),òî åñòü ëåâîå è ïðàâîå îêðóæåíèå (êîíòåêñò) çàìåíÿåìîãî çíàêàA äîëæíû ñîõðàíèòüñÿ è âîêðóã íåïóñòîé çàìåíÿþùåé öåïî÷êèη (ãðå÷åñêàÿ áóêâà ¾ýòà¿).Òàêîå äîïîëíèòåëüíîå îãðàíè÷åíèå ïîçâîëÿåò óäîáíåå ïåðåõîäèòü îò ÊÇ-ãðàììàòèêè ê ñîîòâåòñòâóþùåìó ëèíåéíîîãðàíè÷åííîìó àâòîìàòó (ñì.
ï. 2.6).Ðàññìîòðèì ïîñòðîåíèå ÍÑ-ãðàììàòèêè äëÿ ÿçûêà{an | n > 0}, ïîðîæäàþùåãî ñëîâà âèäà ε, a, a4 , a9 , ...2Äëÿ áîëüøåé ÿñíîñòè ñïåðâà ïîñòðîèì äëÿ ýòîãî ÿçûêà ãðàììàòèêó îáùåãî âèäà, à ïîòîì ïåðåñòðîèì å¼ â ñîîòâåòñòâèè ñÍÑ-îãðàíè÷åíèÿìè.2Ñàì àëãîðèòì ïîðîæäåíèÿ an ìîæåò îñíîâûâàòüñÿ êàê íàèçâåñòíîì ñâîéñòâå êâàäðàòîâ ÷èñåë, ðàçíîñòü ìåæäó ñîñåäíèìè èç êîòîðûõ îáðàçóþò àðèôìåòè÷åñêóþ ïðîãðåññèþ, òàê è íàñîáñòâåííî ¾êâàäðàòíîñòè¿ èíòåðåñóþùèõ ÷èñåë, ò.å. òîãî, ÷òîêàæäîå êâàäðàòíîå ÷èñëî ïðåäñòàâèìî íàïîäîáèå ìàòðèöû èç nñòðîê è n ñòîëáöîâ åäèíè÷íûõ ñîñòàâëÿþùèõ (â ñâÿçè ñ ÷åì Ïèôàãîð è äàë íàçâàíèå ïîäîáíûì ÷èñëàì - êâàäðàòíûå, à ñðåäèÃðàììàòèêè27äðóãèõ ÷èñåë ïî òîìó æå ïðèíöèïó îòìåòèë òðåóãîëüíûå, êóáè÷åñêèå, ïèðàìèäàëüíûå è ò.ï.). Ïîñëåäíèé ïîäõîä ïðåäñòàâëÿåòñÿ áîëåå îáùèì, ïîñêîëüêó ïîäîáíûì îáðàçîì ìû ñìîæåìkïîñòðîèòü è {an | k > 2}.Èòàê, ïîðîæäàåì äâå ãðóïïû ïî n ýëåìåíòîâÏðàâèëàÂèä ïîëó÷àåìîé öåïî÷êèS → CSD | CDC n DnCD → DCAC n−1 DCA D n−1 (A çàäåðæèâàåò C )CA → AC(DAn )n C n (îòðàáîòàëè âñå C )(Dan )n C nA→an2Ïîëó÷èëè a , íî ÷òî äåëàòü ñ C è D? Ñäåëàâ ñâî¼ äåëî, îíèñòàëè ëèøíèìè. ãðàììàòèêå îáùåãî âèäà òàêèå çíàêè ñîêðàùàþò (¾óâîëüíÿþò¿), à â ÊÇ-ãðàììàòèêàõ ¾ïåðåâîäÿò íà äðóãóþ ðàáîòó¿ (âîñíîâíûå çíàêè).
Íî åñëè ìû ïðîñòî íàïèøåì C → ε, D → ε, âûâîä â ñëó÷àéíûé ìîìåíò âðåìåíè ìîæåò çàêîí÷èòüñÿ äîñðî÷íîè ñòàíåò âîçìîæíûì ïîðîæäåíèå ëèøíèõ öåïî÷åê.Ïîýòîìó â îáîèõ ñëó÷àÿõ íå îáîéòèñü áåç äàëüíåéøåãî óòî÷íåíèÿ ïðåäíàçíà÷åíèÿ (ìèññèé) è ñîñòàâà ¾äåéñòâóþùèõ ëèö¿.Îòìåòèì äëÿ ýòîãî ñàìûé ïåðâûé èç êîìàíäû çíàêîâ C (íàçîâ¼ì åãî B ) è ñàìûé ïîñëåäíèé èç D (îáîçíà÷èì åãî E ). ÊîãäàB è E âñòðåòÿòñÿ, ýòî è áóäåò ïðèçíàêîì ïîëíîãî çàâåðøåíèÿïðîöåññà ïîðîæäåíèÿ çíàêîâ a.Íà÷í¼ì âûâîä ñ íà÷àëà:ÏðàâèëàÂèä ïîëó÷àåìîé öåïî÷êèS → BS 0 EBS 0 ES 0 → CS 0 D | CDB C n Dn ECD → DCAB C n−1 (DA)n CE(C ïðîøëî ïåðâûé ðàç)CA → ACB (DAn )n C n E (ïðîøëè âñå C )BD → BBAn (DAn )n−1 C n EBA → ABAn∗n B C nE (óøëè âñå D)CE → EAn∗n BE (óøëè âñå C )BE → εAn∗n (óøëè B c E )A→aan∗nÐåçóëüòàò ïîëó÷èëè, íî êàêîé öåíîé (äëÿ B, C, D è E )?Ïðÿìî-òàêè ñòàëèíñêèå ìåòîäû.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
