1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 3
Текст из файла (страница 3)
Ê íàì îòíîñÿòñÿ â ïåðâóþî÷åðåäü ÿçûêè, èñïîëüçóåìûå ïðè ðàáîòå ñ êîìïüþòåðîì (â ÷àñòíîñòèÿçûêè ïðîãðàììèðîâàíèÿ) è ÿçûêè, èñïîëüçóåìûå â ìàòåìàòè÷åñêîé ëîãèêå. Ýòè ÿçûêè ïîääàþòñÿ èçó÷åíèþ ñòðîãèìè ìàòåìàòè÷åñêèìè ìåòîäàìè.Äëÿ òîãî ÷òîáû ãîâîðèòü î ÿçûêå â òî÷íûõ òåðìèíàõ, íåîáõîäèìîïðåæäå âñåãî çàôèêñèðîâàòü àëôàâèò êîíå÷íîå (îáû÷íî íåïóñòîå)ìíîæåñòâî ñèìâîëîâ A = {a0 , a1 , . . .
, an }. Ïðåäïîëîæèì, ÷òî ìû çàôèêñèðîâàëè íåêîòîðûé àëôàâèò A. Ïîä ñëîâîì â àëôàâèòå A ìû áóäåìïîíèìàòü ëþáóþ êîíå÷íóþ öåïî÷êó ñèìâîëîâ èç ýòîãî àëôàâèòà, âêëþ÷àÿ ïóñòîå ñëîâî, íå ñîäåðæàùåå ñèìâîëîâ, è îáîçíà÷àåìîå Λ. Óïîòðåáëÿåòñÿ òàêæå âûðàæåíèå ñëîâî íàä àëôàâèòîì A. Íàïðèìåð, a, abba, Λ ñëîâà â àëôàâèòå {a, b}, àíóáûâàþòæåòàêèåñòðàííûåñëîâà, àáðàêàäàáðà, áâãæþðñò ñëîâà â àëôàâèòå {à, á, â,. . . , ý, þ, ÿ}. Ïóñòü A∗ îáîçíà÷àåò ìíîæåñòâîâñåõ ñëîâ íàä àëôàâèòîì A, à A+ îáîçíà÷àåò ìíîæåñòâî âñåõ íåïóñòûõñëîâ íàä àëôàâèòîì A, ò.å., A+ = A∗ \ {Λ}. Áóäåì îáîçíà÷àòü äëèíóñëîâà α ÷åðåç |α| (ïðè ýòîì êîíå÷íî æå |Λ| = 0).Ëþáîå ìíîæåñòâî L ⊆ A∗ áóäåì íàçûâàòü ôîðìàëüíûì ÿçûêîì íàäàëôàâèòîì A.Îïðåäåëèì íåêîòîðûå îïåðàöèè íàä ñëîâàìè è ÿçûêàìè.Êîíêàòåíàöèÿ ñëîâ v è w ýòî áèíàðíàÿ îïåðàöèÿ íà ìíîæåñòâå ñëîâ(òî åñòü îòîáðàæåíèå èç (A∗ )2 â A∗ ), ðåçóëüòàòîì ïðèìåíåíèÿ êîòîðîé êñëîâàì v è w ÿâëÿåòñÿ ñëîâî, ïîëó÷àþùååñÿ ïðèïèñûâàíèåì ê v ñëîâà wñïðàâà, òî åñòü ñëîâî vw.
Èíîãäà èñïîëüçóåòñÿ òàêæå îáîçíà÷åíèå v ◦ w.Ïðèìåðû. Êîíêàòåíàöèÿ ñëîâ àáðà è êàäàáðà åñòü ñëîâî àáðàêàäàáðà.Îòìåòèì íåêîòîðûå äîñòàòî÷íî î÷åâèäíûå ñâîéñòâà êîíêàòåíàöèè:1.2. Àëôàâèòû è ÿçûêè17• êîíêàòåíàöèÿ ñ ïóñòûì ñëîâîì íå èçìåíÿåò ïåðâîíà÷àëüíîå ñëîâî:Λ ◦ v = v ◦ Λ = v.• êîíêàòåíàöèÿ àññîöèàòèâíà: äëÿ ëþáûõ ñëîâ u, v , w âûïîëíåíîðàâåíñòâî u(vw) = (uv)w.Îïåðàöèÿ êîíêàòåíàöèè åñòåñòâåííûì îáðàçîì ðàñøèðÿåòñÿ íà ÿçûêè. Êîíêàòåíàöèÿ ÿçûêîâ L0 è L1 îïðåäåëÿåòñÿ, êàêL0 L1 = {uv | u ∈ L0 , v ∈ L1 }.Ïîíÿòèå ïîäñëîâà. Ñëîâî β íàçûâàåòñÿ ïîäñëîâîì ñëîâà α, åñëè ñó-ùåñòâóþò ñëîâà γ0 è γ1 òàêèå, ÷òî α = γ0 βγ1 . Ïðè ýòîì âõîæäåíèåìïîäñëîâà β â ñëîâî α íàçîâ¼ì òðîéêó hγ0 , β, γ1 i.
Íàçîâ¼ì ñàìûì ëåâûìâõîæäåíèåì ïîäñëîâà β â ñëîâî α òàêóþ òðîéêó hγ0 , β, γ1 i ñ íàèìåíüøèìâîçìîæíûì çíà÷åíèåì äëèíû ñëîâà γ0 . Íàïðèìåð ñëîâî áàîáàá èìååò äâàðàçíûõ âõîæäåíèÿ ïîäñëîâà áà: Λ ◦ áà ◦ îáàá è áàî ◦ áà ◦ á. Ïåðâîå èçíèõ áóäåò ñàìûì ëåâûì âõîæäåíèåì.Ïî àíàëîãèè ñ óìíîæåíèåì ìîæíî îïðåäåëèòü ñòåïåíè ñ íàòóðàëüíûì ïîêàçàòåëåì è äëÿ ñëîâ, à èìåííî:w0 = Λ;wn+1 = wn w,Èëè ìåíåå ôîðìàëüíî: wn = w. . w}.| .{zn ðàçÎïåðàöèÿ çâåçäî÷êà Êëèíè (èëè ïðîñòî çâåçäî÷êà ).
Îíà îïðåäå-ëÿåòñÿ òàê:L∗ = {w|w = w1 w2 . . . wn , äëÿ íåêîòîðîãî n = 0, 1, 2, . . .è äëÿ íåêîòîðûõ w1 , . . . , wn ∈ L}. ÷àñòíîñòè, äëÿ ëþáîãî ÿçûêà L âûïîëíåíî Λ ∈ L∗ .Ìû áóäåì èñïîëüçîâàòü òàêæå îïåðàöèè îáúåäèíåíèÿ, ïåðåñå÷åíèÿè äîïîëíåíèÿ ÿçûêîâ. Ïîñêîëüêó â ýòèõ ñëó÷àÿõ ÿçûêè âûñòóïàþò êàêîáûêíîâåííûå ìíîæåñòâà, ñïåöèàëüíî îïðåäåëÿòü ýòè îïåðàöèè íåò ñìûñëà. Ñòîèò òîëüêî îòìåòèòü, ÷òî äîïîëíåíèå ÿçûêà L ⊆ A∗ îáû÷íî ïîíèìàåòñÿ êàê äîïîëíåíèå îòíîñèòåëüíî A∗ , òî åñòü êàê ìíîæåñòâî A∗ \ L.18Ãëàâà 1.
Ââåäåíèå1.3 Îáñóæäåíèå èíòóèòèâíûõ ñâîéñòâ àëãîðèòìîâÑ àëãîðèòìàìè ìû âñòðå÷àåìñÿ î÷åíü ðàíî, ïî êðàéíåé ìåðå âû âñòðå÷àëè èõ åùå â øêîëå, îòðàáàòûâàÿ íàâûêè ñëîæåíèÿ, âû÷èòàíèÿ, óìíîæåíèÿ è äåëåíèÿ â ñòîëáèê. Åñëè ó Âàñ åñòü äîñòóï ê êîìïüþòåðó,Âû ìîæåòå íàáëþäàòü ðàáîòó òàêèõ àëãîðèòìîâ, êàê ôîðìàòèðîâàíèåòåêñòà, ïðîâåðêà ïðàâîïèñàíèÿ è ìíîãèõ äðóãèõ. Êðîìå òîãî, ëþáàÿ ïðîãðàììà è äàæå ñàìà îïåðàöèîííàÿ ñèñòåìà âñåãî ëèøü äåéñòâóþùèåàëãîðèòìû.
Ñåãîäíÿ, ðàñïëà÷èâàÿñü â êàññå çà ïîêóïêó, ïîëó÷àÿ äåíüãè ïî êàðòî÷êå, ðàçãîâàðèâàÿ ïî ìîáèëüíîìó òåëåôîíó, ïåðåïèñûâàÿñüïî ýëåêòðîííîé ïî÷òå, ìû òàêæå çàñòàâëÿåì ðàáîòàòü íà íàñ íåêîòîðûå àëãîðèòìû. Ìíîãèå ïðîöåññû íà ïðîèçâîäñòâå, äâèæåíèå ïîåçäîâ èñàìîëåòîâ òîæå â çíà÷èòåëüíîé ñòåïåíè ðåãóëèðóåòñÿ àëãîðèòìàìè. Áåçïðåóâåëè÷åíèÿ ìîæíî ñêàçàòü, ÷òî àëãîðèòìû îêðóæàþò íàñ íà êàæäîìøàãó.Ðàññìîòðèì â êà÷åñòâå ïðèìåðà àëãîðèòì Åâêëèäà íàõîæäåíèÿ íàèáîëüøåãî îáùåãî äåëèòåëÿ äâóõ íàòóðàëüíûõ ÷èñåë a è b.Àëãîðèòì Åâêëèäà. Åñëè a = b = 0, òî âûäàéòå â êà÷åñòâåîòâåòà 0 è çàêîí÷èòå ðàáîòó.Åñëè òîëüêî îäíî èç ÷èñåë a, b ðàâíî 0, òî âûäàéòå â êà÷åñòâå îòâåòà òî èç íèõ, êîòîðîå íå ðàâíî 0 è çàêîí÷èòå ðàáîòó. îñòàëüíûõ ñëó÷àÿõ, ïîëîæèòå r0 = a, r1 = b è ðàçäåëèòår0 íà r1 ñ îñòàòêîìr0 = r1 q1 + r2 , 0 6 r2 < r1è ïðîäîëæàéòå ñåðèþ äåëåíèér1=r2 q2 + r3 , 0 6 r3 < r2r2=r3 q3 + r4 , 0 6 r4 < r3...äî òåõ ïîð, ïîêà íà íåêîòîðîì øàãå íå ïîëó÷èòñÿ ri+1 = 0.(Ýòî íåïðåìåííî ïðîèçîéäåò, ïîñêîëüêó îáðàçóþùèåñÿ â ðåçóëüòàòå îñòàòêè îáðàçóþò óáûâàþùóþ öåïî÷êó íàòóðàëüíûõ ÷èñåë r1 > r2 > r3 > .
. .) Òîãäà íàäî âûäàòü â êà÷åñòâåîòâåòà ri è çàêîí÷èòü ðàáîòó.1.3. Îáñóæäåíèå èíòóèòèâíûõ ñâîéñòâ àëãîðèòìîâ19(Ýòîò àëãîðèòì âûäàåò íàèáîëüøèé îáùèé äåëèòåëü a è b, ïîñêîëüêóèç ðàâåíñòâà âèäà rj = rj+1 qj+1 +rj+2 ñëåäóåò, ÷òî ëþáîé îáùèé äåëèòåëüäëÿ rj è rj+1 ÿâëÿåòñÿ îäíîâðåìåííî è îáùèì äåëèòåëåì äëÿ rj+1 è rj+2 .Îòñþäà ïîëó÷àåì, ÷òî äëÿ âñåõ j âûïîëíåíî ÍÎÄ(rj , rj+1 )=ÍÎÄ(rj+1 , rj+2 ).Òåïåðü, ðàññìàòðèâàÿ öåïî÷êó ðàâåíñòâ ÍÎÄ(a, b) = ÍÎÄ(r1 , r2 ) = ÍÎÄ(r2 , r3 )= . . . = ÍÎÄ(ri , 0), è çàìå÷àÿ, ÷òî ÍÎÄ(ri , 0) = ri , ïîëó÷àåì òðåáóåìîåÍÎÄ(a, b) = ri .)Ïðîàíàëèçèðîâàâ ýòîò, ïóñòü è íåáîëüøîé îïûò çíàêîìñòâà ñ àëãîðèòìàìè, ïîïûòàåìñÿ îïèñàòü íåêîòîðûå õàðàêòåðíûå ñâîéñòâà àëãîðèòìîâ.
Ðàçíûå àâòîðû âûäåëÿþò ðàçíûå èõ ñâîéñòâà è ïîðàçíîìó èõãðóïïèðóþò. Çäåñü ìû âûäåëèì ñëåäóþùèå ñâîéñòâà àëãîðèòìîâ:êîíå÷íîñòü îïèñàíèÿ Âñÿêèé àëãîðèòì çàïèñûâàåòñÿ íåêîòîðûì êî-íå÷íûì òåêñòîì â íåêîòîðîì ÿçûêå (åñòåñòâåííîì èëè àëãîðèòìè÷åñêîì)äèñêðåòíîñòü àëãîðèòìà Âñÿêèé àëãîðèòì èñïîëíÿåòñÿ ïî øàãàì, ïðîèñõîäÿùèì â äèñêðåòíîì âðåìåíè.
Èñïîëíåíèå øàãà àëãîðèòìà ñîñòîèò â òîì, ÷òî â õîäå åãî èñïîëíåíèÿ íåêîòîðîå êîíå÷íîå ñåìåéñòâî êîíå÷íûõ îáúåêòîâ ïðåîáðàçóåòñÿ â äðóãîå êîíå÷íîå ñåìåéñòâî îáúåêòîâ, çàòåì ïðîèñõîäèò ñëåäóþùèé øàã è ò.ä. Âîçìîæíîñòü èñïîëíåíèÿ ëþáîãî øàãà íå âûçûâàåò ñîìíåíèé ïðè óñëîâèè,÷òî ìû îáëàäàåì ñêîëü óãîäíî áîëüøèì òðóäîëþáèåì è òåðïåíèåì,à òàêæå ðàñïîëàãàåì ñêîëü óãîäíî áîëüøèì âðåìåíåì è äîñòàòî÷íûì çàïàñîì äðóãèõ ðåñóðñîâ (íàïðèìåð áóìàãè è êàðàíäàøåé).íàïðàâëåííîñòü àëãîðèòìà Ó àëãîðèòìà èìåþòñÿ âõîäíûå äàííûå,êîòîðûå ïåðåðàáàòûâàþòñÿ â âûõîäíûå äàííûå. Ïðè ýòîì â àëãîðèòìå óêàçûâàåòñÿ, êîãäà îñòàíîâèòü åãî ðàáîòó è ÷òî ñëåäóåòñ÷èòàòü ðåçóëüòàòîì åãî ðàáîòû.ìàññîâîñòü àëãîðèòìà Àëãîðèòì ïðèìåíÿåòñÿ äëÿ ðåøåíèÿ íåêîòî-ðîé çàäà÷è. Íà÷àëüíûå äàííûå äëÿ àëãîðèòìà âûáèðàþòñÿ èç íåêîòîðîãî, êàê ïðàâèëî, áåñêîíå÷íîãî ìíîæåñòâà, è îäèí è òîò æå àëãîðèòì ïðèìåíÿåòñÿ äëÿ îáðàáîòêè ëþáîãî èç ýòèõ äàííûõ.Äàëåå ìû áóäåì èçó÷àòü íåêîòîðûå èç ñóùåñòâóþùèõ íàèáîëåå âàæíûõ ïîäõîäîâ ê ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìà.Ìû íà÷íåì ñ êîíå÷íûõ àâòîìàòîâ, êîòîðûì ïîñâÿùåíà ñëåäóþùàÿãëàâà.20Ãëàâà 1.
ÂâåäåíèåÃëàâà 2Êîíå÷íûå àâòîìàòû èãðàììàòèêè2.1 Äåòåðìèíèðîâàííûå àâòîìàòûÊîíå÷íûå àâòîìàòû ýòî àáñòðàêòíûå âû÷èñëèòåëüíûå óñòðîéñòâà, ñïîìîùüþ êîòîðûõ ìîæíî ðåøàòü äîñòàòî÷íî øèðîêèé êëàññ àëãîðèòìè÷åñêèõ çàäà÷, íàïðèìåð çàäà÷ó êëàññèôèêàöèè ñëîâ â íåêîòîðûõ ôîðìàëüíûõ ÿçûêàõ. Âîçìîæíîñòåé êîíå÷íûõ àâòîìàòîâ, îäíàêî, íåäîñòàòî÷íî äëÿ òîãî, ÷òîáû ðåøàòü âîîáùå âñå çàäà÷è, ðåøàåìûå ñ ïîìîùüþàëãîðèòìîâ.Ñíà÷àëà ìû äàäèì íåôîðìàëüíîå îïèñàíèå êîíå÷íûõ àâòîìàòîâ.
Âêàæäûé ìîìåíò âðåìåíè êîíå÷íûé àâòîìàò íàõîäèòñÿ â íåêîòîðîì âíóòðåííåì ñîñòîÿíèè. ×èñëî òàêèõ âíóòðåííèõ ñîñòîÿíèé êîíå÷íî. Íà âõîäàâòîìàòà ïîäàþòñÿ îäèí çà äðóãèì ñèìâîëû èç íåêîòîðîãî çàðàíåå îïðåäåëåííîãî êîíå÷íîãî íàáîðà âõîäíûõ ñèìâîëîâ, êîòîðûé íàçûâàåòñÿ âõîäíûì àëôàâèòîì; ìîæíî ñ÷èòàòü, ÷òî àâòîìàò ñ÷èòûâàåò îäèí çà äðóãèì íåêîòîðûå ñèìâîëû ñ äâèæóùåéñÿ ëåíòû, ðàçáèòîé íà ÿ÷åéêè. Øàãðàáîòû àâòîìàòà ñîñòîèò â ñëåäóþùåì. Ïîñëå ñ÷èòûâàíèÿ î÷åðåäíîãîñèìâîëà, àâòîìàò ïåðåõîäèò â íîâîå ñîñòîÿíèå, îäíîçíà÷íî îïðåäåëÿåìîåïî òåêóùåìó ñîñòîÿíèþ è òîëüêî ÷òî ñ÷èòàííîìó ñèìâîëó ñ ïîìîùüþ çàðàíåå çàäàííîé ôóíêöèè ïåðåõîäà, ïîñëå ÷åãî àâòîìàò ïåðåõîäèò ê ñëåäóþùåìó øàãó, íà÷èíàþùåìóñÿ ñî ñ÷èòûâàíèÿ ñëåäóþùåãî ñèìâîëà èò.ä. Àâòîìàò âñåãäà íà÷èíàåò ñâîþ ðàáîòó â íåêîòîðîì ôèêñèðîâàííîìíà÷àëüíîì ñîñòîÿíèè.
Íàì ïîíàäîáèòñÿ òàêæå íåêîòîðîå ìíîæåñòâî âûäåëåííûõ ñîñòîÿíèé, íàçíà÷åíèå êîòîðûõ áóäåò îáúÿñíåíî ïîçæå.2122Ãëàâà 2. Êîíå÷íûå àâòîìàòû è ãðàììàòèêè' 0#þ-Iq0½ "!16& 1$?¾#û¾»q1½¼ ¼"!0%Ðèñ. 2.1: Ãðàôè÷åñêîå èçîáðàæåíèå êîíå÷íîãî àâòîìàòàÈòàê, êîíå÷íûé àâòîìàò ïîëíîñòüþ îïðåäåëÿåòñÿ ñâîèìè ñëåäóþùèìè àòðèáóòàìè:• àëôàâèòîì A = {a0 , . . . , an } êîíå÷íûì íàáîðîì ñèìâîëîâ, êîòîðûå ìîãóò ïîäàâàòüñÿ íà âõîä ýòîãî àâòîìàòà;• êîíå÷íûì íàáîðîì âíóòðåííèõ ñîñòîÿíèé Q = {q0 , . . . , qm };• ôóíêöèåé ïåðåõîäà δ : Q × A → Q, âûäàþùåé ïî òåêóùåìó ñîñòîÿíèþ q è ïðî÷èòàííîìó àâòîìàòîì ñèìâîëó a íîâîå ñîñòîÿíèå δ(q, a),â êîòîðîå ïåðåõîäèò àâòîìàò ïðè ïîëó÷åíèè äàííîãî ñèìâîëà;• íà÷àëüíûì ñîñòîÿíèåì q0 ∈ Q;• ìíîæåñòâîì âûäåëåííûõ ñîñòîÿíèé F ⊆ Q.Òàêèì îáðàçîì, êîíå÷íûé àâòîìàò ìîæíî ôîðìàëüíî îïðåäåëèòüêàê óïîðÿäî÷åííóþ ïÿòåðêó (Q, A, δ, q0 , F ), ñîñòîÿùóþ èç âûøåîïèñàííûõ îáúåêòîâ.Êîíå÷íûå àâòîìàòû ìîæíî èçîáðàæàòü ãðàôè÷åñêè êàê ýòî ñäåëàíîíà ðèñóíêå 2.1.
Íà ýòîì ðèñóíêå îêðóæíîñòè èçîáðàæàþò âíóòðåííèå ñîñòîÿíèÿ àâòîìàòà; íà÷àëüíîå ñîñòîÿíèå àâòîìàòà ïîìå÷åíî ÷åðíûì òðåóãîëüíèêîì I; êîíå÷íûå ñîñòîÿíèÿ àâòîìàòà (çäåñü èõ âñåãî îäíî) èçîáðàæåíû äâîéíîé îêðóæíîñòüþ. Ñòðåëêè, ïîìå÷åííûå ñèìâîëàìè àëôàâèòà {0, 1}, èçîáðàæàþò ïåðåõîäû àâòîìàòà â äðóãèå ñîñòîÿíèÿ ïðè ïîäà÷å íà âõîä ñèìâîëà, êîòîðûìè ïîìå÷åíû ýòè ñòðåëêè. Òàê èçîáðàæåííûé2.1. Äåòåðìèíèðîâàííûå àâòîìàòû23íà ýòîì ðèñóíêå àâòîìàò ïðè ïîäà÷å íà âõîä ñèìâîëà 0 ïåðåéäåò èç ñîñòîÿíèÿ q0 â ñîñòîÿíèå q1 , à ïðè ïîäà÷å ñèìâîëà 1 îñòàíåòñÿ â ñîñòîÿíèèq0 .Åñëè ìû áóäåì ïîäàâàòü íà âõîä àâòîìàòà îäèí çà äðóãèì öåïî÷êóñèìâîëîâ ñëîâà s = s0 s1 . .
. íàä àëôàâèòîì A, òî íàø àâòîìàò áóäåòïåðåõîäèòü ïîñëåäîâàòåëüíî èç ñîñòîÿíèÿ q0 â ñîñòîÿíèÿδ(q0 , s0 ), δ(δ(q0 , s0 ), s1 ), δ(δ(δ(q0 , s0 ), s1 ), s2 ), . . .Çàìåòèì, ÷òî ïðè ýòîì ñîñòîÿíèå, â êîòîðîì áóäåò íàõîäèòüñÿ àâòîìàòïîñëå ñ÷èòûâàíèÿ ïîñëåäíåãî ñèìâîëà â ñëîâå, îïðåäåëåíî îäíîçíà÷íî.Åñëè ýòî ñîñòîÿíèå ïðèíàäëåæèò ìíîæåñòâó âûäåëåííûõ ñîñòîÿíèé F ,òî ìû áóäåì ãîâîðèòü, ÷òî íàø àâòîìàò ðàñïîçíàåò (èëè ïðèíèìàåò)ñëîâî s.  ïðîòèâíîì ñëó÷àå áóäåì ãîâîðèòü, ÷òî îí íå ðàñïîçíàåò (èëèíå ïðèíèìàåò) ñëîâî s.Äàäèì òåïåðü áîëåå ôîðìàëüíîå îïðåäåëåíèå ýòîãî ïîíÿòèÿ.
Ðàñøèðèì ôóíêöèþ δ äî δ ∗ íà Q × A∗ ñëåäóþùèì îáðàçîì, ÷òîáû îíà îïðåäåëÿëà ñîñòîÿíèå àâòîìàòà δ ∗ (q, w) ïîñëå òîãî, êàê îí, íà÷àâ ñâîþ ðàáîòóâ ñîñòîÿíèè q ïðî÷òåò âñå ñèìâîëû ñëîâà w:δ ∗ (q, Λ) = q,δ ∗ (q, sa) = δ(δ ∗ (q, s), a),äëÿ ëþáûõ s ∈ A∗ , a ∈ A.Îïðåäåëåíèå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
