1610906281-ae38486ec859a3a9dcd398b8f34f26aa (824377), страница 6
Текст из файла (страница 6)
Ïîðîæäåíèå àâòîìàòíûõ ÿçûêîâ: ðåãóëÿðíûå âûðàæåíèÿ(2) ⇒ (1).Òåïåðü äîêàæåì èìïëèêàöèþíå÷íûé àâòîìàòA.37Ïóñòü çàäàí íåêîòîðûé êî-Áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî åãî1, 2, . . . , n, è ÷òî ñîñòîÿíèå 1 ÿâëÿåòñÿ íà÷àëüíûì.F . Äîêàæåì,÷òî ðàñïîçíàâàåìûé èì ÿçûê ìîæíî ïðåäñòàâèòü â âèäå L(α), ãäå α íåêîòîðîå ðåãóëÿðíîå âûðàæåíèå. Äëÿ ýòîãî äëÿ ëþáûõ i, j ∈ {1, . .
. , n},k ∈ {0, . . . , n} îïðåäåëèì ìíîæåñòâî ñëîâ R(i, j, k) ñëåäóþùèì îáðàçîì:ñîñòîÿíèÿìè ÿâëÿþòñÿÎáîçíà÷èì ìíîæåñòâî åãî çàêëþ÷èòåëüíûõ ñîñòîÿíèé ÷åðåçR(i, j, k) åñòü ìíîæåñòâî âñåõ ñëîâ, ïðî÷èòûâàåìûõ âäîëü ïóòåé èç ñîñòîÿíèÿ i â ñîñòîÿíèå j , âñå îñòàëüíûå ïðîìåæóòî÷íûå ñîñòîÿíèÿ êîòîðûõ ñîäåðæàòñÿ â ñïèñêå 1, . . . , k .Ëåììà 2.5.1ëÿðíû.Âñå ÿçûêè R(i, j, k), i, j ∈ {1, . . . , n}, k ∈ {0, . .
. , n} ðåãó-Åñëè ìû äîêàæåì, ÷òî âñå ýòè ÿçûêè ðåãóëÿðíû, òî âñå îíè áóäóòèìåòü âèäR(i, j, k) = L(αi,j,k ).Îòñþäà ìû ïîëó÷èì, ÷òî!L(A) =[R(1, i, n) =i∈Fò.å.,L(A)[L(α1,i,n ) = Li∈FXα1,i,n,i∈Fîêàæåòñÿ ðåãóëÿðíûì ÿçûêîì, è òåîðåìà áóäåò äîêàçàíà.Ïðèñòóïèì ê äîêàçàòåëüñòâó ëåììû. Ñíà÷àëà çàìåòèì, ÷òî êàæäûéR(i, j, 0) ýòî ìíîæåñòâî ñëîâ, ïðî÷èòûâàåìûõ âäîëü âñåõ ïóòåé èç ñîñòîÿíèÿ i â ñîñòîÿíèå j , íå çàõîäÿùèõ íè â îäíî ïðîìåæóòî÷íîåÿçûê âèäàñîñòîÿíèå, è ïîýòîìó ìîæåò èìåòü òîëüêî îäèí èç ñëåäóþùèõ âèäîâ:• ∅•êîíå÷íîå ìíîæåñòâî îäíîáóêâåííûõ ñëîâ (êîãäà•ìíîæåñòâîíûõ ñëîâi 6= j ),{Λ} â îáúåäèíåíèè ñ êîíå÷íûì ìíîæåñòâîì îäíîáóêâåí(êîãäà i = j ).Âñå òàêèå ÿçûêè, î÷åâèäíî, ÿâëÿþòñÿ êîíå÷íûìè îáúåäèíåíèÿìè ÿçûêîâ∗∗âèäà ∅, {Λ} è {a}, a ∈ A.
Ó÷èòûâàÿ, ÷òî {Λ} = ∅ = L(∅ ), ðåãóëÿðíîñòüýòèõ ÿçûêîâ ëåãêî äîêàçûâàåòñÿ. Ìû îñòàâëÿåì äîêàçàòåëüñòâî ýòîãî âêà÷åñòâå óïðàæíåíèÿ.Ïðåäïîëîæèì, ÷òî âñå ÿçûêèÿçûêR(i, j, m)ðåãóëÿðíû. Ïîêàæåì, ÷òî èR(i, j, m + 1) òàêæå ðåãóëÿðåí. Ïðîèçâîëüíûé ïóòü èç ñîñòîÿíèÿ i âÃëàâà 2. Àâòîìàòíûå ÿçûêè381, .
. . , m + 1 ìîæåò íåñêîëüêî ðàç (â òîì ÷èñëåè íè ðàçó) çàõîäèòü â ñîñòîÿíèå m + 1, à â ïðîìåæóòêàõ îí áóäåò ïðîõîäèòü òîëüêî ÷åðåç ñîñòîÿíèÿ èç ñïèñêà 1, . . . , m. Îòñþäà ëåãêî óñìîòðåòüñîñòîÿíèåjïî ñîñòîÿíèÿìñïðàâåäëèâîñòü ðàâåíñòâà:R(i, j, m + 1) = R(i, j, m) ∪ R(i, m + 1, m)R(m + 1, m + 1, m)∗ R(m + 1, j, m).Òåïåðü, â ñèëó ðåãóëÿðíîñòè ÿçûêîâ âèäàðåãóëÿðíûå âûðàæåíèåαp,q,mòàêèå, ÷òîR(p, q, m), äëÿ íèõ ñóùåñòâóþòR(p, q, m) = L(αp,q,m ) Îòñþäàèìååì:R(i, j, m + 1) = L(αi,j,m ) ∪ L(αi,m+1,m )L(αm+1,m+1,m )∗ L(αm+1,j,m ) =∗= L(αi,j,m + αi,m+1,m αm+1,m+1,mαm+1,j,m ),ò.å., ÿçûêR(i, j, m + 1)òàêæå ðåãóëÿðåí, ÷òî è äîêàçûâàåò íàøå óòâåð-æäåíèå.Çàìå÷àíèå. Èç äîêàçàòåëüñòâà òåîðåìû èçâëåêàþòñÿ àëãîðèòìû, ïîç-A ýôôåêòèâíî ñòðîèòü ðåãóëÿðíîå âûðàæåíèå α ñî ñâîéñòâîì L(A) = L(α) è, íàîáîðîò, ïî ëþáîìóðåãóëÿðíîìó âûðàæåíèþ α ñòðîèòü êîíå÷íûé àâòîìàò A ñ ýòèì æå ñâîé-âîëÿþùèå ïî ëþáîìó êîíå÷íîìó àâòîìàòóñòâîì.Çàìå÷àíèå. ñîâðåìåííîé ëèòåðàòóðå ñèìâîëâìåñòî, íàïðèìåð, ¾ÿçûêLíå èñïîëüçóåòñÿ, èL(a+b)¿ èñïîëüçóåòñÿ ïðîñòî âûðàæåíèå ¾ÿçûêa + b¿.2.6Àëãîðèòìè÷åñêàÿ ðàçðåøèìîñòü íåêîòîðûõ ñâîéñòâÇäåñü áóäåò ïîêàçàíî, ÷òî äëÿ îòâåòîâ íà ðÿä åñòåñòâåííûõ âîïðîñîâî êîíå÷íûõ àâòîìàòàõ è àâòîìàòíûõ ÿçûêàõ ìîãóò áûòü èñïîëüçîâàíûàëãîðèòìû.
Ïðè ýòîì ìû íå áóäåì ñòàâèòü öåëüþ óêàçàíèå íàèëó÷øèõàëãîðèòìîâ, à ïðîñòî íà èíòóèòèâíîì óðîâíå äîêàæåì ñóùåñòâîâàíèåõîòü êàêèõòî àëãîðèòìîâ.Êîíå÷íûé àâòîìàò çàäà¼ò íåïóñòîé ÿçûê, òîãäà è òîëüêî òîãäà, êîãäà îí ïðèíèìàåò íåêîòîðîå ñëîâî äëèíû, ìåíüøåé, ÷åì÷èñëî åãî ñîñòîÿíèé.Òåîðåìà 2.6.12.6. Àëãîðèòìè÷åñêàÿ ðàçðåøèìîñòü íåêîòîðûõ ñâîéñòâ39Äîêàçàòåëüñòâî òåîðåìû.
Äåéñòâèòåëüíî, åñëè àâòîìàò ïðèíèìàåòíåêîòîðîå ñëîâî, òî ýòî ñëîâî ïðî÷èòûâàåòñÿ âäîëü íåêîòîðîãî ïóòè èçíà÷àëüíîãî ñîñòîÿíèÿ â âûäåëåííîå ñîñòîÿíèå. Åñëè äëèíà ýòîãî ïóòèáîëüøå ÷èñëà ëèáî ðàâíà ÷èñëó ñîñòîÿíèé àâòîìàòà, òî çäåñü âîçìîæíû äâà ñëó÷àÿ: íà÷àëüíîå ñîñòîÿíèå ýòîãî ïóòè ñîâïàäàåò ñ ïîñëåäíèìñîñòîÿíèåì ýòîãî ïóòè è ñëó÷àé, êîãäà ýòî íå âûïîëíåíî.  ïåðâîì ñëó÷àå íà÷àëüíîå ñîñòîÿíèå ÿâëÿåòñÿ âûäåëåííûì, è àâòîìàò ïðèíèìàåòïóñòîå ñëîâî, äëèíà êîòîðîãî (0) ìåíüøå, ÷åì ÷èñëî ñîñòîÿíèé, è, òåîðåìà, òàêèì îáðàçîì, ñïðàâåäëèâà.
Ðàññìîòðèì âòîðîé ñëó÷àé. Åñëè íàýòîì ïóòè åñòü ¾öèêëû¿ íåòðèâèàëüíûå ó÷àñòêè, íà÷èíàþùèåñÿ è çàêàí÷èâàþùèåñÿ â îäíîì è òîì æå ñîñòîÿíèè òî òàêîé ó÷àñòîê ìîæíîóäàëèòü èç äàííîãî ïóòè, è ñëîâî, ïðî÷èòûâàåìîå âäîëü âíîâü ïîëó÷åííîãî ïóòè, ñíîâà áóäåò ñëîâîì, ðàñïîçíàâàåìûì òåì æå àâòîìàòîì, íîóæå ñëîâîì ñòðîãî ìåíüøåé äëèíû.
Îñóùåñòâèì ýòîò ïðîöåññ äî òåõïîð, ïîêà ¾öèêëîâ¿ ñîâñåì íå îñòàíåòñÿ. Êîãäàëèáî ýòî ïðîèçîéä¼ò. Âðåçóëüòàòå ìû ïîëó÷èì ñëîâî, ïðî÷èòûâàåìîå íà ïóòè èç íà÷àëüíîãîñîñòîÿíèÿ â êîíå÷íîå, âñå ñîñòîÿíèÿ êîòîðîãî ðàçëè÷íû ìåæäó ñîáîé.Äëèíà åãî, î÷åâèäíî, áóäåò ñòðîãî ìåíüøå ÷èñëà ñîñòîÿíèé àâòîìàòà.Îáðàòíîå óòâåðæäåíèå î÷åâèäíî: åñëè àâòîìàò ïðèíèìàåò ñëîâî íåêîòîðîé äëèíû, òî óæå â ñèëó ýòîãî ÿçûê ýòîãî àâòîìàòà íåïóñò.Èç ýòîé òåîðåìû ìû ïîëó÷èì àëãîðèòì, ïîçâîëÿþùèé âûÿñíÿòü ïîëþáîìó êîíå÷íîìó àâòîìàòó, çàäà¼ò ëè îí íåïóñòîé ÿçûê èëè íåò: äîñòàòî÷íî âûïèñàòü âñå ñëîâà ñîîòâåòñòâóþùèõ äëèí è ïðîâåðèòü, ïðèíèìàåòëè àâòîìàò õîòü îäíî èç ýòèõ ñëîâ.ßçûê, ðàñïîçíàâàåìûé êîíå÷íûì àâòîìàòîì ñ n ñîñòîÿíèÿìè, áåñêîíå÷åí òîãäà è òîëüêî òîãäà, êîãäà àâòîìàò ðàñïîçíà¼òíåêîòîðîå ñëîâî äëèíû l, óäîâëåòâîðÿþùåé íåðàâåíñòâó n 6 l < 2n.Òåîðåìà 2.6.2Äîêàçàòåëüñòâî òåîðåìû.
Ïóñòü àâòîìàò ðàñïîçíà¼ò ñëîâî, äëèíà êîòîðîãî óäîâëåòâîðÿåò óñëîâèÿì òåîðåìû. Òîãäà â ïóòè èç íà÷àëüíîãîñîñòîÿíèÿ â âûäåëåííîå, âäîëü êîòîðîãî ïðî÷èòûâàåòñÿ ýòî ñëîâî, êàêìèíèìóì îäíî ñîñòîÿíèå âñòðå÷àåòñÿ äâàæäû, ò.å., â ýòîì ñëîâå èìååòñÿ¾ïåòëÿ¿, êîòîðóþ íà ýòîì ïóòè ìîæíî ïðîéòè ñêîëü óãîäíî ðàç, è ïðèýòîì êàæäûé ðàç áóäóò ïîëó÷àòüñÿ ñëîâà, ðàñïîçíàâàåìûå ýòèì àâòîìàòîì, è âñå îíè áóäóò èìåòü ðàçíûå äëèíû. Òàêèì îáðàçîì, ÿçûê äàííîãîàâòîìàòà áóäåò áåñêîíå÷íûì.Ãëàâà 2.
Àâòîìàòíûå ÿçûêè40Ïðåäïîëîæèì òåïåðü, ÷òî àâòîìàò ðàñïîçíà¼ò áåñêîíå÷íûé ÿçûê. Çíà÷èò â íåêîòîðîì ïóòè ïî ýòîìó àâòîìàòó, âûõîäÿùåìó èç íà÷àëüíîãîñîñòîÿíèÿ è çàêàí÷èâàþùåìñÿ â âûäåëåííîì ñîñòîÿíèè, îäíî è òî æå ñîñòîÿíèå âñòðå÷àåòñÿ äâàæäû. Íà÷í¼ì â ýòîì ïóòè çàìåíÿòü ôðàãìåíòûâèäàs0 s1 . . .
sk−1 sk = s0 , (si s0 , s1 , . . . , sk−1è âñå ñîñòîÿíèÿñîñòîÿíèÿ) â êîòîðûõïîïàðíî ðàçëè÷íû, íàs0 ∈/ {s1 , . . . , sk−1 },s0 . Ïîñëå êàæäîéòàêîé çàìåíû ìû ñíîâà áóäåì ïîëó÷àòü ïóòü èç íà÷àëüíîãî ñîñòîÿíèÿ ââûäåëåííîå, íî óæå ìåíüøåé äëèíû. Êîãäàíèáóäü ýòîò ïðîöåññ çàêîí÷èòñÿ, è ìû ïîëó÷èì ïóòü, äëèíà êîòîðîãî l0 ñòðîãî ìåíüøån. Âåðí¼ìñÿâ ýòîì ïðîöåññå íà îäèí øàã íàçàä.  ýòîò ìîìåíò íàø ïóòü èìåë âèäs0 · · · s · · · s · · · sm ,ïðè÷¼ì âñå ñîñòîÿíèÿ, íàõîäÿùèåñÿ ìåæäó äâóìÿ îòìå÷åííûìè çäåñüñîñòîÿíèÿìès,ïîïàðíî ðàçëè÷íû è îòëè÷íû îòîòðåçîê ïóòè ìåæäó ýòèìè ñîñòîÿíèÿìèl1 6 n.ss.Ýòî îçíà÷àåò, ÷òîèìååò ïîëîæèòåëüíóþ äëèíó¾Íàêà÷èâàÿ¿ ó÷àñòîê ìåæäó ýòèìè ñîñòîÿíèÿìèïóòè, äëèíû êîòîðûõ ðàâíû l0+ kl1 , k = 0, 1, . . .s,ìû ïîëó÷èìÓ÷èòûâàÿ èìåþùèåñÿíåðàâåíñòâà, ìû ïîëó÷àåì, ÷òî õîòÿ áû îäíî èç ýòèõ ÷èñåëðÿåò íåðàâåíñòâólóäîâëåòâî-n 6 l < 2n.Êàê è â ïðåäûäóùåì ñëó÷àå, îòñþäà ìû ìîæåì ïîëó÷èòü àëãîðèòì,ïîçâîëÿþùèé ïî êîíå÷íîìó àâòîìàòó îïðåäåëèòü, çàäà¼ò îí áåñêîíå÷íûé ÿçûê èëè íåò.
Äåéñòâèòåëüíî, äëÿ ïðîûåðêè äîñòàòî÷íî âûïèñàòüâñå ñëîâà äëèíûl n 6 l < 2n,ãäån ÷èñëî ñîñòîÿíèé, è ïðîâåðèòü,ðàñïîçíà¼ò íàø àâòîìàò õîòÿ áû îäíî èç ýòèõ ñëîâ èëè íåò.Ñóùåñòâóþò àëãîðèòìû, ïîçâîëÿþùèå ïî ëþáûì äâóìêîíå÷íûì àâòîìàòàì A è B ýôôåêòèâíî âûÿñíÿòü èñòèííîñòü óòâåðæäåíèé L(A) ⊆ L(B) è L(A) = L(B).Òåîðåìà 2.6.3Äîêàçàòåëüñòâî òåîðåìû.  ñèëó òåîðåòèêîìíîæåñòâåííîé ýêâèâàëåíòíîñòèL(A) = L(B) ⇔ L(A) ⊆ L(B) ∧ L(B) ⊆ L(A),äîñòàòî÷íî óêàçàòü àëãîðèòì äëÿ ïðîâåðêè âêëþ÷åíèÿ ÿçûêîâ. Ïî òåîðåìå 2.4.1, àâòîìàò äëÿ ðàñïîçíàâàíèÿ ÿçûêàL(A) ∩ L(B)ñòðîèòñÿ ðàâ-A è B. Ïî òåîðåìå 2.6.1 è ñëåäóþùåìó çà íåé êîìL(A) ∩ L(B) = ∅, ýêâèâàëåíòíîå âêëþ÷åíèþ L(A) ⊆B, óñòàíàâëèâàåòñÿ ïî ïîëó÷åííîìó àâòîìàòó íåêîòîðûì àëãîðèòìîì.
íîìåðíî ïî àâòîìàòàììåíòàðèþ, óñëîâèå2.7. Ïîðîæäåíèå àâòîìàòíûõ ÿçûêîâ ñ ïîìîùüþ ôîðìàëüíûõ ãðàììàòèê41Ïîñêîëüêó, êàê óæå îòìå÷àëîñü, ðåãóëÿðíûå âûðàæåíèÿ ìîæíî ðàâíîìåðíî ïðåîáðàçîâûâàòü â àâòîìàòû, çàäàþùèå ÿçûêè ýòèõ ðåãóëÿðíûõâûðàæåíèé, è íàîáîðîò, àíàëîãè÷íîå óòâåðæäåíèå âåðíî è äëÿ ðåãóëÿðíûõ âûðàæåíèé:Ñóùåñòâóþò àëãîðèòìû, ïîçâîëÿþùèå ïî ëþáûì äâóìðåãóëÿðíûì âûðàæåíèÿì α è β ýôôåêòèâíî ïðîâåðÿòü èñòèííîñòüóòâåðæäåíèé L(α) ⊆ L(β) è L(α) = L(β).Òåîðåìà 2.6.42.7Ïîðîæäåíèå àâòîìàòíûõ ÿçûêîâ ñ ïîìîùüþ ôîðìàëüíûõ ãðàììàòèêÏðåæäå, ÷åì äàâàòü ôîðìàëüíûå îïðåäåëåíèÿ, äàâàéòå ïîïûòàåìñÿ îïðåäåëèòü, ÷òî ìû ïîíèìàåì, íàïðèìåð, ïîä äåñÿòè÷íîé çàïèñüþ íàòóðàëüíûõ ÷èñåë.
Ìû îáû÷íî ñ÷èòàåì, ÷òî òàêàÿ çàïèñü ýòî ïðîñòî ïîñëåäîâàòåëüíîñòü èç öèôð0, . . . , 9,êîòîðàÿ ìîæåò íà÷èíàòüñÿ ñ ñèìâîëà0âîäíîì è òîëüêî â îäíîì ñëó÷àå: êîãäà ýòà çàïèñü ñîñòîèò èç åäèíñòâåííî-0. Èòàê, ìîæíî ñêàçàòü, ÷òî äåñÿòè÷íàÿ çàïèñü íàòóðàëüíîãî÷èñëà ýòî ëèáî 0 ëèáî îäíà èç öèôð 1, . . . , 9, ïîñëå êîòîðîé ìîæåò èäòè ëþáàÿ êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü èç ñèìâîëîâ 0, .
. . , 9. Òàê 0, 231è 6745 ÿâëÿþòñÿ çàïèñÿìè íàòóðàëüíûõ ÷èñåë, à çàïèñè âèäà 00, 015,0007 è ò.ï. òàêîâûìè íå ÿâëÿþòñÿ. Èç ýòèõ ðàññìîòðåíèé âèäíî, ÷òî äëÿîïðåäåëåíèÿ äåñÿòè÷íîé çàïèñè (îáîçíà÷èì ýòî ïîíÿòèå ñèìâîëîì Nat)ãî ñèìâîëàíàì ïîíàäîáÿòñÿ òàêæå ïîíÿòèå ïîñëåäîâàòåëüíîñòè öèôð (êîòîðîå ìûîáîçíà÷èì ñèìâîëîìSeq). Áîëåå ôîðìàëüíî, ìû ìîæåì îáúÿâèòü, ÷òîSeq åñòü ëèáî ïóñòîå ñëîâî ëèáî îäíà èç öèôðïîñëåäîâàòåëüíîñòü öèôð0, . .
. , 9, ïîñëå êîòîðîé ñíîâà èä¼ò íåêîòîðàÿ ïîñëåäîâàòåëüíîñòü öèôð,à Nat åñòü îäíà èç öèôð 1, . . . , 9, ïîñëå êîòîðîé âûïèñàíà ïîñëåäîâàòåëüíîñòü öèôð (ò.å., íå÷òî, îáîçíà÷àåìîå Seq). Òåïåðü, åñëè â îáùåìñëó÷àå ïîíèìàòü ïîä çàïèñüþ A → B óòâåðæäåíèå ¾ïîíÿòèå B ÷àñòíûé ñëó÷àé ïîíÿòèÿ A¿, òî ìû ìîæåì çàïèñàòü ýòî îïðåäåëåíèå â âèäåñëåäóþùåãî ñïèñêà ïðàâèë:Seq → Λ,Seq → 0 Seq,Seq → 1 Seq,...Ãëàâà 2. Àâòîìàòíûå ÿçûêè42SeqNatNatNat→→→→···Nat →Íàïðèìåð, óòâåðæäåíèå î òîì, ÷òî9 Seq,0,1 Seq,2 Seq,9 Seq.123 çàïèñü íàòóðàëüíîãî ÷èñëà,ìîæíî ôîðìàëüíî ïîëó÷èòü ñëåäóþùåé öåïî÷êîé ïðèìåíåíèÿ ýòèõ ïðàâèë:Nat → 1 Seq → 12 Seq → 123.NatNat → 1 Seq), ïîòîì âòîì, ÷òî ïîëó÷èëîñü, Seq çàìåíÿåòñÿ íà 2 Seq (ïî ïðàâèëó Seq → 2 Seq),ïîòîì â òîì, ÷òî ïîëó÷èëîñü, Seq çàìåíÿåòñÿ íà 3 Seq (ïî ïðàâèëó Seq →3 Seq). Íàêîíåö, Seq çàìåíÿåòñÿ íà Λ ïî ïðàâèëó Seq → Λ.
Ïîñëå ýòîãîÇäåñüçàìåíÿåòñÿ íà 1 Seq (ïî ïðàâèëóâ ïîëó÷åííîé ïîñëåäîâàòåëüíîñòè ñèìâîëîâ çàìåíÿòü óæå íå÷åãî.ÇäåñüNat íåêîòîðîå ïîíÿòèå, äëÿ îïðåäåëåíèÿ êîòîðîãî, ñîáñòâåí-íî, è ñëóæèò ïðèâåä¼ííûé âûøå ñïèñîê ïðàâèë.Òåïåðü, ðàññìîòðåâ äàííûé ïðèìåð êàê ÷àñòíûé ñëó÷àé, ìû ìîæåìäàòü îïðåäåëåíèå òàê íàçûâàåìûõôîðìàëüíûõ ãðàììàòèê.Ôîðìàëüíîé ãðàììàòèêîé íàçûâàåòñÿ óïîðÿäî÷åííàÿ ÷åòâ¼ðêà G = hV, T, P, τ i, â êîòîðîéÎïðåäåëåíèå 2.7.1V íåêîòîðîå êîíå÷íîå ìíîæåñòâî ñèìâîëîâ (íàçûâàåìûõ íåòåðìèíàëüíûììè ñèìâîëàìè),T íåêîòîðîå êîíå÷íîå ìíîæåñòâî ñèìâîëîâ (íàçûâàåìûõ òåðìèíàëüíûììè ñèìâîëàìè), ïðè÷¼ì V ∩ T = ∅,P íåêîòîðîå êîíå÷íîå ìíîæåñòâî òàê íàçûâàåìûõ ïðîäóêöèé âûðàæåíèé âèäà A → B , A, B ∈ (V ∪ T )∗ , â êîòîðûõ A ñîäåðæèòõîòÿ áû îäèí íåòåðìèíàëüíûé ñèìâîë,τ íà÷àëüíûé ñèìâîë, τ ∈ V .2.7. Ïîðîæäåíèå àâòîìàòíûõ ÿçûêîâ ñ ïîìîùüþ ôîðìàëüíûõ ãðàììàòèê43V = {Nat, Seq}, T = {0, 1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
