1610906281-d25a58898a45262b0b837c281ba962eb (824376), страница 8
Текст из файла (страница 8)
. . , βk òàêàÿ, ÷òîÎïðåäåëåíèå.∗Γβ0 = α, βk = β è èìååò ìåñòîβ0 −→ β1 −→ . . . −→ βk .ΓÖåïî÷êà (∗) íàçûâàåòñÿΓΓ(∗)âûâîäîì ñëîâà β èç ñëîâà α â ãðàììàòèêå Γ.Ïóñòü Γ = hV, T, P, Si ôîðìàëüíàÿ ãðàììàòèêà. ßçûê L(Γ) = {w ∈T | S −→ w} íàçûâàåòñÿΓ.Îïðåäåëåíèå.∗∗Γÿçûêîì, ïîðîæä¼ííûì ãðàììàòèêîéÂåðí¼ìñÿ ê ïðèìåðó ñ àëãîðèòìîì ïîðîæäåíèÿ ñáàëàíñèðîâàííûõ ñëîâ.Ñ ôîðìàëüíîé òî÷êè çðåíèÿ â äàííîé ãðàììàòèêå ìíîæåñòâî íåòåðìèíàëüíûõ ñèìâîëîâ èìååò âèä V = {S}, ìíîæåñòâîì òåðìèíàëüíûõ ñèìâîëîâ ÿâëÿåòñÿ T = {(, )}.Ìíîæåñòâî ïðîäóêöèé P = {S → (), S → (S), S → SS}.
Íà÷àëüíûé ñèìâîë ýòîñèìâîë S .Ïðèìåð.Ðàññìîòðèì òåïåðü ïðèìåð ôîðìàëüíîé ãðàììàòèêè, êîòîðàÿ ïîðîæäàåòÿçûê âñåõ äåñÿòè÷íûõ çàïèñåé íàòóðàëüíûõ ÷èñåë â àëôàâèòå èç äåñÿòè òåðìèíàëüíûõ öèôð T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Êàæäàÿ çàïèñü íàòóðàëüíîãî ÷èñëà åñòü ëèáî0, ëèáî ïîëó÷àåòñÿ ïðèïèñûâàíèåì íåíóëåâîé öèôðû ñëåâà ê íåêîòîðîé ïîñëåäîâàòåëüíîñòè öèôð.  ñâîþ î÷åðåäü êàæäàÿ ïîñëåäîâàòåëüíîñòü öèôð åñòü ëèáî ïóñòîåñëîâî Λ, ëèáî ïîëó÷àåòñÿ ïðèïèñûâàíèåì ëþáîé öèôðû (âêëþ÷àÿ 0) ñëåâà ê íåêîòîðîìó ñëîâó, ïðî êîòîðîå óæå èçâåñòíî, ÷òî îíî ÿâëÿåòñÿ ïîñëåäîâàòåëüíîñòüþ öèôð.Ýòè ðàññóæäåíèÿ ïîçâîëÿþò ôîðìàëüíî âûïèñàòü ìíîæåñòâî ïðîäóêöèé P :Ïðèìåð.S −→ 0S −→ 1AS −→ 2A···S −→ 9AA −→ ΛA −→ 0AA −→ 1A···A −→ 9AÒàêèì îáðàçîì, àëôàâèò íåòåðìèíàëüíûõ ñèìâîëîâ V = {S, A} ñîñòîèò èç äâóõ áóêâ.Ñèìâîë S íà÷àëüíûé, îí ñîîòâåòñòâóåò òåðìèíó ¾çàïèñü íàòóðàëüíîãî ÷èñëà¿.Ñèìâîë A ñîîòâåòñòâóåò òåðìèíó ¾ïîñëåäîâàòåëüíîñòü öèôð¿.Îïðåäåëåíèå.Ôîðìàëüíàÿ ãðàììàòèêà Γ = hV, T, P, Si íàçûâàåòñÿ:, åñëè âñå å¼ ïðîäóêöèè èìåþò âèä A −→ β , ãäå A ∈ V ,êîíòåêñòíî-ñâîáîäíîéðåãóëÿðíîéà)β ∈ (V ∪ T )∗ ;á), åñëè âñå å¼ ïðîäóêöèè èìåþò âèä A −→ aB èëè A −→ Λ, ãäåA, B ∈ V , a ∈ T . íåêîòîðûõ èñòî÷íèêàõ ðåãóëÿðíûìè íàçûâàþò ôîðìàëüíûå ãðàììàòèêè, â êîòîðûõ ïðîäóêöèè èìåþò âèä A −→ aB , A −→ a èëè A −→ Λ, ãäå A, B ∈ V ,a ∈ T .
Îäíàêî, òàêèå ãðàììàòèêè ëåãêî ñâîäÿòñÿ ê ðåãóëÿðíûì ãðàììàòèêàì èçîïðåäåëåíèÿ âûøå. Äëÿ ýòîãî äîñòàòî÷íî êàæäóþ ïðîäóêöèþ p = A −→ a çàìåíèòüÇàìå÷àíèå.31 9. Ôîðìàëüíûå ãðàììàòèêèíà ïàðó ïðîäóêöèé A −→ aAp è Ap −→ Λ, ãäå Ap íîâûé íåòåðìèíàëüíûé ñèìâîë.Íàïðèìåð, ðàññìîòðåííûé âûøå ÿçûê äåñÿòè÷íûõ çàïèñåé íàòóðàëüíûõ ÷èñåë ïîðîæäàåòñÿ ðåãóëÿðíîé ãðàììàòèêîé. ßñíî òàêæå, ÷òî ëþáàÿ ðåãóëÿðíàÿ ãðàììàòèêàÿâëÿåòñÿ êîíòåêñòíî-ñâîáîäíîé.ïðàâîëèíåéíûìèÐåãóëÿðíûå ãðàììàòèêè òàêæå èíîãäà íàçûâàþò, ïîñêîëüêó ïðèïîðîæäåíèè ñëîâ â òàêèõ ãðàììàòèêàõ êàæäûé íîâûé òåðìèíàëüíûé ñèìâîë ïîÿâëÿåòñÿ ñïðàâà îò ïðåäûäóùåãî. Ëþáîé âûâîä ñëîâà a1 a2 . . . ak ∈ T ∗ èç íà÷àëüíîãîñèìâîëà S â ðåãóëÿðíîé ãðàììàòèêå èìååò âèä:S −→ a1 A1 −→ a1 a2 A2 −→ .
. . −→ a1 a2 . . . ak Ak −→ a1 a2 . . . ak ,ΓΓΓΓΓãäå A1 , . . . , Ak íåòåðìèíàëüíûå ñèìâîëû, ïðè ýòîì ñíà÷àëà â âûâîäå ìíîãîêðàòíîèñïîëüçóþòñÿ ïðîäóêöèè âèäà A −→ aB è ëèøü â êîíöå ïðèìåíÿåòñÿ ïðîäóêöèÿâèäà A −→ Λ.Ìîæíî ñêàçàòü, ÷òî â ðåãóëÿðíûõ ãðàììàòèêàõ ñëîâà ïîðîæäàþòñÿ ñëåâà íàïðàâîáåç âîçìîæíîñòè âîçâðàòà â íà÷àëüíûå ñèìâîëû ñëîâà. Èíà÷å ãîâîðÿ, åñëè íà ïðîìåæóòî÷íîì øàãå áûëî âûâåäåíî ñëîâî a1 a2 . . . as As , òî íà âñåõ ïîñëåäóþùèõ øàãàõïðåôèêñ a1 a2 . . . as îñòàíåòñÿ íåèçìåííûì.
Ïîõîæèì ñâîéñòâîì îáëàäàþò êîíå÷íûåàâòîìàòû, â êîòîðûõ ñèìâîëû ñëîâ òàêæå ïðî÷èòûâàþòñÿ ñëåâà íàïðàâî. Ýòî íàáëþäåíèå ëåæèò â îñíîâå ñëåäóþùåé òåîðåìû.ßçûê L ïîðîæäàåòñÿ ðåãóëÿðíîé ãðàììàòèêîé òîãäà è òîëüêî òîãäà,êîãäà L àâòîìàòíûé.Äîêàçàòåëüñòâî. (=⇒) Ïóñòü ÿçûê L ïîðîæäàåòñÿ ðåãóëÿðíîé ãðàììàòèêîé Γ =Òåîðåìà 15.hV, T, P, Si. Îïðåäåëèì Λ-í.ê.à.
A ñëåäóþùèì îáðàçîì:à) Ìíîæåñòâîì ñîñòîÿíèé àâòîìàòà ÿâëÿåòñÿ ìíîæåñòâî V ∪ {q}, ãäå q íîâûéñèìâîë, ò. å. q ∈/ V.á) Âíåøíèì àëôàâèòîì àâòîìàòà áóäåò ìíîæåñòâî T .â) Íà÷àëüíûì ñîñòîÿíèåì ÿâëÿåòñÿ S .ã) Åäèíñòâåííûì âûäåëåííûì ñîñòîÿíèåì áóäåò q .ä) Ïåðåõîäû â àâòîìàòå A îïðåäåëÿþòñÿ ïî ñëåäóþùåìó ïðèíöèïó. Äëÿ êàæäîéaïðîäóêöèè âèäà A −→ aB äîáàâëÿåì äóãó −−−−→.
Äëÿ êàæäîé ïðîäóêöèèBAΛA −→ Λ äîáàâëÿåì äóãó −−−−→◦.qAÇàìåòèì, ÷òî ïî ïîñòðîåíèþ àâòîìàòà â í¼ì íåò äóã, âûõîäÿùèõ èç åäèíñòâåííîãîâûäåëåííîãî ñîñòîÿíèÿ q . Îòñþäà ñëåäóåò, ÷òî ëþáîé ïóòü â A, âäîëü êîòîðîãî ðàñïîçíà¼òñÿ íåêîòîðîå ñëîâî w ∈ T ∗ , äîëæåí çàêàí÷èâàòüñÿ Λ-ïåðåõîäîì, âõîäÿùèì âñîñòîÿíèå q , à âñå îñòàëüíûå ïåðåõîäû äàííîãî ïóòè ïîìå÷åíû íåïóñòûìè ñèìâîëàìèèç T .Ïîêàæåì, ÷òî L = L(A). Ïóñòü w = a1 a2 . . . ak ∈ T ∗ ïðîèçâîëüíîå ñëîâî (âîçìîæíî ïóñòîå).
Òîãäà èìååò ìåñòî ñëåäóþùàÿ öåïî÷êà ýêâèâàëåíòíûõ óòâåðæäåíèé:w ∈ L ⇐⇒ Ñóùåñòâóåò âûâîäS −→ a1 A1 −→ a1 a2 A2 −→ . . . −→ a1 a2 . . . ak Ak −→ a1 a2 . . . akΓΓΓΓΓ32Ãëàâà II. Êîíå÷íûå àâòîìàòû è ôîðìàëüíûå ãðàììàòèêèñëîâà w â ãðàììàòèêå Γ. ⇐⇒  ìíîæåñòâå P èìåþòñÿ ïðîäóêöèè âèäàS −→ a1 A1A1 −→ a2 A2... ... ...Ak−1 −→ ak AkAk −→ Λ⇐⇒  ïîñòðîåííîì àâòîìàòå A èìååòñÿ ïóòü âèäàH iSa1 - i a2 - i a3 - . . .A1A2ak−1- i ak - i Λ - idqAk−1Ak⇐⇒ w ∈ L(A). ×òî è òðåáîâàëîñü äîêàçàòü.(⇐=) Ïóñòü òåïåðü L àâòîìàòíûé.
Òîãäà ñóùåñòâóåò ä.ê.à. A = hQ, A, δ, q0 , F iòàêîé, ÷òî L = L(A). Îïðåäåëèì ðåãóëÿðíóþ ãðàììàòèêó Γ ñëåäóþùèì îáðàçîì:à) Ìíîæåñòâîì íåòåðìèíàëüíûõ ñèìâîëîâ ãðàììàòèêè ÿâëÿåòñÿ ìíîæåñòâî Q.á) Ìíîæåñòâîì òåðìèíàëüíûõ ñèìâîëîâ áóäåò ìíîæåñòâî A.â) Íà÷àëüíûì ñèìâîëîì ÿâëÿåòñÿ q0 .ã) Ìíîæåñòâî ïðîäóêöèé îïðåäåëÿåòñÿ ïî ñëåäóþùåìó ïðèíöèïó. Äëÿ êàæäîéaäóãè àâòîìàòà âèäà −−−−→ äîáàâëÿåì ïðîäóêöèþ q1 −→ aq2 . Êðîìå ýòîãî,q1q2äëÿ êàæäîãî âûäåëåííîãî ñîñòîÿíèÿ q ∈ F äîáàâëÿåì ïðîäóêöèþ q −→ Λ.Ïîêàæåì, ÷òî L = L(Γ).
Ïóñòü w = a1 a2 . . . ak ∈ A∗ ïðîèçâîëüíîå ñëîâî (âîçìîæíî ïóñòîå). Òîãäà èìååò ìåñòî ñëåäóþùàÿ öåïî÷êà ýêâèâàëåíòíûõ óòâåðæäåíèé:w ∈ L ⇐⇒  ä.ê.à. A ñóùåñòâóåò ïóòüH iq0a1 - i a2 - i a3 - . . .q1q2ak−1- i ak - idqk−1qkâäîëü êîòîðîãî ðàñïîçíàåòñÿ ñëîâî w. ⇐⇒  ïîñòðîåííîé ãðàììàòèêå Γ èìåþòñÿïðîäóêöèèq0 −→ a1 q1q1 −→ a2 q2... ... ...qk−2 −→ ak−1 qk−1qk−1 −→ ak qkqk −→ Λ⇐⇒ Ñóùåñòâóåò âûâîäq0 −→a1 q1 −→a1 a2 q2 −→ . .
. −→ a1 . . . ak−1 qk−1 −→a1 . . . ak−1 ak qk −→a1 . . . ak−1 akΓΓΓΓΓñëîâà w â ãðàììàòèêå Γ. ⇐⇒ w ∈ L(Γ). ×òî è òðåáîâàëîñü.Γ33 9. Ôîðìàëüíûå ãðàììàòèêèÍå ëþáîé ÿçûê, ïîðîæä¼ííûé êîíòåêñòíî-ñâîáîäíîé ãðàììàòèêîé, ìîæíî îïðåäåëèòü ðåãóëÿðíîé ãðàììàòèêîé. Òàê ãðàììàòèêà, ïîðîæäàþùàÿ ÿçûê Lâñåõ ñëîâ ñî ñáàëàíñèðîâàííûìè ñêîáêàìè (ñì. ïðèìåð âûøå), êîíòåêñòíî-ñâîáîäíà,íî äàííûé ÿçûê íå çàäà¼òñÿ íèêàêèì ðåãóëÿðíûì âûðàæåíèåì.Äåéñòâèòåëüíî, åñëè áû L áûë ðåãóëÿðíûì, òî ïî ëåììå î íàêà÷èâàíèè ñóùåñòâîâàë áû n > 1 òàêîé, ÷òî äëÿ ëþáîãî w ∈ L, |w| > 1, èìååòñÿ ïðåäñòàâëåíèå â âèäåw = xyz , ãäå |xy| 6 n, y 6= Λ è xy i z ∈ L äëÿ âñåõ i ∈ ω . Åñëè âçÿòü w = ((.
. . ( ) . . .)),| {z } | {z }Çàìå÷àíèå.nnòî â ñîîòâåòñòâóþùåì ïðåäñòàâëåíèè xyz äëÿ ñëîâà w ïîäñëîâî y îáÿçàíî èìåòüâèä y = ((. . . ( , ãäå 1 6 m 6 n. Òîãäà ñëîâî xz = ((. . . ( ) . . .)) ïðèíàäëåæèò L, íî| {z } | {z }| {z }mî÷åâèäíî íå ÿâëÿåòñÿ ñáàëàíñèðîâàííûì.n−mnÃëàâà IIIÔîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîéôóíêöèèÎñíîâíîé öåëüþ äàííîé ãëàâû ÿâëÿåòñÿ ôîðìàëèçàöèÿ ïîíÿòèÿ âû÷èñëèìîé ôóíêöèè, äåéñòâóþùåé íà íàòóðàëüíûõ ÷èñëàõ. Íàïîìíèì, ÷òî kω ìû íàçûâàåì ëþáóþ ôóíêöèþ âèäà f : X → ω , ãäå X ⊆ ω k , k ∈ ω .Ñóùåñòâóåò íåñêîëüêî ðàçëè÷íûõ ïîäõîäîâ, ïðèâîäÿùèõ ê òîìó èëè èíîìó îïðåäåëåíèþ ÷àñòè÷íîé âû÷èñëèìîé ôóíêöèè. Ìû ðàññìîòðèì äâà îñíîâíûõ ïîäõîäà èïîêàæåì, ÷òî îíè ýêâèâàëåíòíû.
Ïåðâàÿ èç ôîðìàëèçàöèé, ñ êîòîðîé ìû ïîçíàêîìèìñÿ â ñëåäóþùåì ïàðàãðàôå, ñâÿçàíà ñ ìàøèíàìè Òüþðèíãà [6], [7], [13].-ìåñòíîé ÷àñòè÷íîéôóíêöèåé íà 10.Îïðåäåëåíèå ìàøèíû ÒüþðèíãàÌàøèíû Òüþðèíãà ýòî îäèí èç ïîäõîäîâ ê ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîéôóíêöèè. Ìîäåëü äëÿ ìàøèíû Òüþðèíãà èìååò ìåõàíè÷åñêîå îïèñàíèå, õîòÿ îêîí÷àòåëüíàÿ èõ ôîðìàëèçàöèÿ ÿâëÿåòñÿ ñîâåðøåííî ìàòåìàòè÷åñêîé.Ïåðåéä¼ì ê íåôîðìàëüíîìó îïèñàíèþ ìàøèí Òüþðèíãà.Ïðîãðàììà :Êîìàíäà...... 1Êîìàíäà n:qqm 0 q1rq2q3Ìàøèíà Òüþðèíãà ñîñòîèò èç ëåíòû, ðàçáèòîé íà îäèíàêîâûå ÿ÷åéêè. ÿ÷åéêàõ ìîãóò ñîäåðæàòüñÿ ñèìâîëû èç âíåøíåãî àëôàâèòà A.
Ñîäåðæèìîå ÿ÷ååê ìîæåò ìåíÿòüñÿ. Ëåíòà ýòî ìåõàíèçì âõîäîâ è âûõîäîâ ìàøèíû. Ïåðåä çàïóñêîì ìàøèíû âõîäíûå äàííûå çàïèñûâàþòñÿ âêîíå÷íîì ó÷àñòêå ëåíòû, è â äàëüA íåéøåì íà êàæäîì øàãå âû÷èñëåíèé. . . a2 a0 a0 a1 a3 a1 a7 a5 a0 . . . èñïîëüçóåòñÿ òîëüêî êîíå÷íîå ìíîæåñòâî ÿ÷ååê. Îäíàêî â ïðîöåññå ðàáîòû ëåíòà ìîæåò äîñòðàèâàòüñÿíîâûìè ÿ÷åéêàìè êàê ñëåâà, òàê è ñïðàâà. Äðóãèìè ñëîâàìè, ëåíòà ÿâëÿåòñÿ ïîòåíöèàëüíî áåñêîíå÷íîé â îáå ñòîðîíû.Òàêæå ìàøèíà Òüþðèíãà îáëàäàåò, êîòîðàÿ â ïðîöåññåðàáîòû ìàøèíû ìîæåò îáîçðåâàòü òîëüêî îäíó ÿ÷åéêó è ðàñïîçíàâàòü ñîäåðæèìîåýòîé ÿ÷åéêè.  çàâèñèìîñòè îò èñïîëíÿåìîé êîìàíäû ãîëîâêà ñïîñîáíà èçìåíÿòü ñîäåðæèìîå îáîçðåâàåìîé ÿ÷åéêè è ñäâèãàòüñÿ çà îäèí øàã íà îäíó ÿ÷åéêó âëåâî èëèâïðàâî.
Òàêèì îáðàçîì, ìàøèíà Òüþðèíãà ýòî óñòðîéñòâî ñäîñòóïîì ê ïàìÿòè: ÷òîáû ïîëó÷èòü äîñòóï ê ñîäåðæàùåéñÿ â íåêîòîðîé ÿ÷åéêå èí-Ñîñòîÿíèåñ÷èòûâàþùåé ãîëîâêîéïîñëåäîâàòåëüíûì35 10. Îïðåäåëåíèå ìàøèíû Òüþðèíãàôîðìàöèè, ìàøèíå ïðèõîäèòñÿ ïåðåáèðàòü îäíó çà äðóãîé âñå ÿ÷åéêè ìåæäó òåêóùåéè òðåáóåìîé.Êàæäàÿ ìàøèíà Òüþðèíãà èìååò êîíå÷íîå ÷èñëîq0 , q1 , . . .
, qm , â êîòîðûõ îíà ìîæåò íàõîäèòüñÿ.  ïðîöåññå ðàáîòû ìàøèíà ìîæåò íåñêîëüêî ðàç âîçâðàùàòüñÿ â îäíî è òî æå ñîñòîÿíèå. Ðàáîòà âñåãäà íà÷èíàåòñÿ ñ âûäåëåííîãî. Êðîìå ýòîãî, åñòü âûäåëåííîå. Åñëè êîãäà-íèáóäüìàøèíà ïîïàäàåò â êîíå÷íîå ñîñòîÿíèå, òî îíà îñòàíàâëèâàåòñÿ, èíà÷å ðàáîòàåò áåñêîíå÷íî.Ëþáàÿ êîíêðåòíàÿ ìàøèíà Òüþðèíãà èìååò ñâîþ óíèêàëüíóþ ïðîãðàììó. ýòî êîíå÷íûé ñïèñîê êîìàíä, êàæäàÿ èç êîòîðûõ åñòü äèðåêòèâà âèäàqi aj → qk al S , ãäå qi , qk ñîñòîÿíèÿ, aj , al ñèìâîëû âíåøíåãî àëôàâèòà, S ∈{R, L, Λ}, ïðè÷åì äëÿ êàæäîãî íåêîíå÷íîãî ñîñòîÿíèÿ qi è ëþáîãî ñèìâîëà aj â ïðîãðàììå èìååòñÿ ðîâíî îäíà êîìàíäà, íà÷èíàþùàÿñÿ ñ ñèìâîëîâ qi aj → .
. . Åñëè æåqi êîíå÷íîå ñîñòîÿíèå, òî êîìàíäà âèäà qi aj → . . . îòñóòñòâóåò â ïðîãðàììå.Îïèøåì îäèí øàã ðàáîòû ìàøèíû Òüþðèíãà. Ïóñòü ìàøèíà íàõîäèòñÿ â íåêîòîðîì ñîñòîÿíèè qi , à ãîëîâêà â òåêóùèé ìîìåíò îáîçðåâàåò ÿ÷åéêó ñ ñèìâîëîì aj .Åñëè qi êîíå÷íîå ñîñòîÿíèå, òî ìàøèíà îñòàíàâëèâàåòñÿ.  ïðîòèâíîì ñëó÷àå âïðîãðàììå íàõîäèòñÿ åäèíñòâåííàÿ êîìàíäà âèäà qi aj → qk al S , êîòîðàÿ çàòåì èñïîëíÿåòñÿ ñëåäóþùèì îáðàçîì: â îáîçðåâàåìóþ ÿ÷åéêó çàïèñûâàåòñÿ ñèìâîë al , çàòåìãîëîâêà ñäâèãàåòñÿ ïî ëåíòå íà îäíó ÿ÷åéêó âïðàâî (åñëè S = R), èëè âëåâî (åñëèS = L), èëè âîîáùå íå äâèãàåòñÿ (åñëè S ïóñòîå ñëîâî), è çàòåì ìàøèíà ïåðåõîäèòâ ñîñòîÿíèå qk .Åñëè ïðè èñïîëíåíèè íåêîòîðîé êîìàíäû ãîëîâêå íåîáõîäèìî ñäâèíóòüñÿ çà ëåâûé êðàé ëåíòû, òî â ýòîò ìîìåíò ïðîèñõîäèò àâòîìàòè÷åñêîå äîñòðàèâàíèå íîâîéÿ÷åéêè ñëåâà, â íå¼ çàïèñûâàåòñÿ âûäåëåííûé ñèìâîë (êàê ïðàâèëî, ýòî ñèìâîë 0)è ãîëîâêà ïåðåäâèãàåòñÿ íà äîñòðîåííóþ ÿ÷åéêó.
Àíàëîãè÷íûì îáðàçîì ïðîèñõîäèòäîñòðàèâàíèå ÿ÷ååê ñïðàâà.Òåïåðü ìû ââåä¼ì ñòðîãèå, ôîðìàëüíûå îïðåäåëåíèÿ.ñîñòîÿíèéãî ñîñòîÿíèÿêîíå÷íîå ñîñòîÿíèåíà÷àëüíîÏðî-ãðàììàÌàøèíà Òüþðèíãà ýòî ïÿò¼ðêà T = hA, Q, P, q1, q0i, ãäå:à) A = {a0 , a1 , . . . , an } êîíå÷íûé âíåøíèé àëôàâèò (ìû áóäåì âñåãäà ïðåäïîëàãàòü, ÷òî n > 1 è a0 = 0, a1 = 1);á) Q = {q0 , q1 , . . . , qm } êîíå÷íûé àëôàâèò âíóòðåííèõ ñîñòîÿíèé, m > 1;â) P = {T (i, j) | 1 6 i 6 m, 0 6 j 6 n} ïðîãðàììà, ñîñòîÿùàÿ èç êîìàíä T (i, j),Îïðåäåëåíèå.êàæäàÿ èç êîòîðûõ åñòü ñëîâî âèäà: qi aj → qk al , èëè qi aj → qk al R, èëè qi aj → qk al L,ãäå 0 6 k 6 m, 0 6 l 6 n;ã) q1 ;ä) q0 .íà÷àëüíîå ñîñòîÿíèåêîíå÷íîå ñîñòîÿíèåÌàøèííûì ñëîâîì (êîíôèãóðàöèåé) íàçûâàåòñÿ ëþáîå ñëîâî âèäàÎïðåäåëåíèå.Aqi aj B , ãäå qi ∈ Q, aj ∈ A, A è B ñëîâà â àëôàâèòå A (âîçìîæíî, ïóñòûå).qiAAa3 a2 a0 a0 a1 aj a4 a0 a1 a2AB36Ãëàâà III.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
