1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 7
Текст из файла (страница 7)
÷èñëàixy(hàðèôì.âûðàæ-åi + hàðèôì.âûðàæ-åi)(hàðèôì.âûðàæ-åi − hàðèôì.âûðàæ-åi)(hàðèôì.âûðàæ-åi × hàðèôì.âûðàæ-åi)(hàðèôì.âûðàæ-åi / hàðèôì.âûðàæå-åi)(2.2)Ïîëüçóÿñü ïðîäóêöèÿìè (2.1) è (2.2), ìû ìîæåì ïîêàçàòü, ÷òî, íàïðèìåð, (x × (y + 20)) ÿâëÿåòñÿ àðèôìåòè÷åñêèì âûðàæåíèåì:hàðèôì.âûðàæåíèåi → (hàðèôì.âûðàæ-åi × hàðèôì.âûðàæ-åi) →→ (x × hàðèôì.âûðàæ-åi) →→ (x × (hàðèôì.âûðàæ-åi + hàðèôì.âûðàæ-åi)) →→ (x × (y + hàðèôì.âûðàæ-åi)) →→ (x × (y + hçàïèñü íàò. ÷èñëài)) →→ (x × (y + 2 hïîñë-òü íàò.÷èñåëi)) →→ (x × (y + 20 hïîñë-òü íàò.÷èñåëi))→ (x × (y + 20)) ( = (x × (y + 20Λ)) ).Çàìåòèì, ÷òî â äàííîì ñëó÷àå ìû, íà÷àâ ñ íåêîòîðîãî íà÷àëüíîãîñèìâîëà hàðèôì.âûðàæ-åi, êàæäûé ðàç âûáèðàåì íåêîòîðóþ ïðîäóêöèþñðåäè ñïèñêîâ (2.1) è (2.2) è çàìåíÿåì â òåêóùåì âûðàæåíèè òî, ÷òîíàõîäèòñÿ ó äàííîé ïðîäóêöèè ñëåâà íà òî, ÷òî íàõîäèòñÿ ó íåå ñïðàâà.Ìû äåëàåì ýòî äî òåõ ïîð, ïîêà íå ïîëó÷èì ñëîâî, â êîòîðîì çàìåíÿòüóæå íå÷åãî.Òåïåðü ïîñëå ðàññìîòðåíèÿ ïðèìåðîâ ìîæíî îïðåäåëèòü è îáùåå ïîíÿòèå ôîðìàëüíîé ãðàììàòèêè.Îïðåäåëåíèå.
Ôîðìàëüíàÿ ãðàììàòèêà ýòî óïîðÿäî÷åííàÿ ÷åòâåðêà Γ = (V, T, P, S), ãäå38Ãëàâà 2. Êîíå÷íûå àâòîìàòû è ãðàììàòèêè• V êîíå÷íîå ìíîæåñòâî òàê íàçûâàåìûõ âñïîìîãàòåëüíûõ ñèìâîëîâ (êîòîðûå ìîæíî ïîíèìàòü êàê ãðàììàòè÷åñêèå êàòåãîðèè);ýòè ñèìâîëû èíîãäà íàçûâàþòñÿ òàêæå íåòåðìèíàëüíûìè• T êîíå÷íîå ìíîæåñòâî òàê íàçûâàåìûõ òåðìèíàëüíûõ5 ñèìâîëîâ òàêîå, ÷òî V ∩ T = ∅;• P êîíå÷íîå ìíîæåñòâî ïðîäóêöèé öåïî÷åê âèäà α → β , ãäåα ∈ (V ∪ T )+ , β ∈ (V ∪ T )∗ è â α ñîäåðæèòñÿ õîòÿ áû îäèí ýëåìåíòèç V ;• S íà÷àëüíûé ñèìâîë, ïðèíàäëåæàùèé ìíîæåñòâó V . ðàññìîòðåííûõ âûøå ïðèìåðàõV = { hçàïèñü íàò.
÷èñëài , hïîñë-òü íàò.÷èñåëi , hàðèôì. âûðàæåíèåi } ,S = hàðèôì.âûðàæåíèåièT = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, (, ), +, −, ×, / } .Çàôèêñèðóåì íåêîòîðóþ ôîðìàëüíóþ ãðàììàòèêó Γ = (V, T, P, S).Ïóñòü α è β ñëîâà â àëôàâèòå (V ∪ T )∗ . Ìû áóäåì ãîâîðèòü, ÷òî âãðàììàòèêå Γ ñëîâî β íåïîñðåäñòâåííî ïîëó÷àåòñÿ èç α (îáîçíà÷àåòñÿ α → β ) åñëè ñóùåñòâóþò ñëîâà α0 , α1 , γ , δ òàêèå ÷òî α = α0 γα1 ,Γβ = α0 δα1 è (γ → δ) ∈ P (òî åñòü åñëè ÷àñòü ñëîâà α, ñîâïàäàþùàÿ ñγ , çàìåíÿåòñÿ íà δ â ñîîòâåòñòâèè ñ îäíîé èç ïðîäóêöèé ãðàììàòèêè Γ).Ìû áóäåì ãîâîðèòü, ÷òî ñëîâî β âûâîäèìî (óïîòðåáëÿþòñÿ òàêæå ñëîâà âûâîäèòñÿ èëè ïîëó÷àåòñÿ ) èç α â ãðàììàòèêå Γ åñëè ñóùåñòâóåòíàòóðàëüíîå ÷èñëî k è êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü β0 , . .
. , βk−1 òàêàÿ,÷òîα → β0 → β1 → . . . → βk−1 → β;ΓΓΓΓΓ(2.3)∗ìû îáîçíà÷àåì ýòîò ôàêò ÷åðåç α → β . Öåïî÷êó 2.3 ìû íàçûâàåì âûâîΓ∗äîì β èç α èëè ïðîñòî âûâîäîì. Çàìåòèì, ÷òî èç α → β ñëåäóåò α → β .Γ5îò àíãëèéñêîãî terminate - çàêàí÷èâàòüñÿ, çàâåðøàòüñÿΓ2.5. Òèïû ãðàììàòèê39Òåïåðü íàêîíåö ìîæíî îïðåäåëèòü ÿçûê, ïîðîæäàåìûé ãðàììàòèêîé Γ = (V, T, P, S):¯()¯∗¯L(Γ) =β ∈ T∗ ¯ S → β.¯ΓÈíà÷å ãîâîðÿ, ÿçûê L(Γ) ãðàììàòèêè Γ ñîñòîèò èç âñåõ ñëîâ, â çàïèñè êîòîðûõ ó÷àñòâóþò òîëüêî òåðìèíàëüíûå ñèìâîëû, è êîòîðûåâûâîäÿòñÿ â íåé èç íà÷àëüíîãî ñèìâîëà S .2.5 Òèïû ãðàììàòèêÂûäåëÿþò íåêîòîðûå ñïåöèàëüíûå òèïû ôîðìàëüíûõ ãðàììàòèê. Ìûïðèâåäåì èç íèõ òðè íàèáîëåå óïîòðåáèòåëüíûõ.
Ãðàììàòèêà íàçûâàåòñÿ• íåóêîðà÷èâàþùåé, åñëè äëÿ ëþáîé åå ïðîäóêöèè α → β âûïîëíåíî|α| ≤ |β|;• êîíòåêñòíîñâîáîäíîé åñëè âñå åå ïðîäóêöèè èìåþò âèä A → β ,ãäå A ïåðåìåííàÿ èç V ;• ðåãóëÿðíîé 6 åñëè âñå åå ïðîäóêöèè èìåþò îäèí èç ñëåäóþùèõ äâóõâèäîâ: A → aB , A → a, ãäå A, B ∈ V , a ∈ T .ßçûêè, ïîðîæäàåìûå êîíòåêñòíîñâîáîäíûìè ãðàììàòèêàìè íàçûâàþòñÿ êîíòåêñòíîñâîáîäíûìè.2.6 Íåêîòîðûå ñâîéñòâà ãðàììàòèê2.6.1ßçûêè ðåãóëÿðíûõ ãðàììàòèê è àâòîìàòíûå ÿçûêèÎêàçûâàåòñÿ, êëàññû ÿçûêîâ, çàäàâàåìûå ðåãóëÿðíûìè ãðàììàòèêàìè èêëàññ àâòîìàòíûõ ÿçûêîâ ïî÷òè íå îòëè÷àþòñÿ, î ÷åì ãîâîðèò ñëåäóþùàÿ òåîðåìà:6Èíîãäà â ëèòåðàòóðå äàåòñÿ íåìíîãî äðóãîå îïðåäåëåíèå ðåãóëÿðíûõ ãðàììàòèê,â êîòîðîì äîïóñêàåòñÿ âîçìîæíîñòü âûâîäà ïóñòîãî ñëîâà Λ.
Ýòî äåëàåòñÿ äëÿ òîãî,÷òîáû êëàññ ÿçûêîâ, çàäàâàåìûõ ðåãóëÿðíûìè ãðàììàòèêàìè, ñîâïàäàë ñ êëàññîìðåãóëÿðíûõ ÿçûêîâ. Èç äàëüíåéøåãî áóäåò âèäíî, ÷òî ïðè íàøåì îïðåäåëåíèè ýòèÿçûêè áóäóò îòëè÷àòüñÿ îò ðåãóëÿðíûõ ÿçûêîâ ëèøü íà ïóñòîå ñëîâî Λ.40Ãëàâà 2. Êîíå÷íûå àâòîìàòû è ãðàììàòèêèÒåîðåìà 2.6.11. Ëþáîé ÿçûê, çàäàâàåìûé ðåãóëÿðíîé ãðàììàòèêîé, ÿâëÿåòñÿ àâòîìàòíûì.2. Äëÿ ëþáîãî êîíå÷íîãî àâòîìàòà A ÿçûê T (A)\{Λ} çàäàåòñÿ íåêîòîðîé ðåãóëÿðíîé ãðàììàòèêîé.Äîêàçàòåëüñòâî. Äîêàæåì (1).
Ïóñòü ÿçûê L çàäàåòñÿ íåêîòîðîé ðå-ãóëÿðíîé ãðàììàòèêîé Γ = (V, T, P, S). Îïðåäåëèì íåêîòîðûé (âîîáùåãîâîðÿ íåäåòåðìèíèðîâàííûé) àâòîìàò AΓ ñëåäóþùèì îáðàçîì: ïóñòüñîñòîÿíèÿìè ýòîãî àâòîìàòà áóäóò ýëåìåíòû ìíîæåñòâà V ïëþñ åùåîäíî íîâîå ñîñòîÿíèå Q, êîòîðîå áóäåò åãî åäèíñòâåííûì âûäåëåííûìñîñòîÿíèåì. Ñîñòîÿíèå S áóäåò íà÷àëüíûì ñîñòîÿíèåì ýòîãî àâòîìàòà.Îïðåäåëèì òåïåðü â ýòîì àâòîìàòå âîçìîæíûå ïåðåõîäû èç îäíîãî ñîñòîÿíèÿ â äðóãîå.
Êàê îáû÷íî, ìû ïðåäñòàâëÿåì êîíå÷íûé àâòîìàò êàêñîâîêóïíîñòü ñîñòîÿíèé, ñîåäèíåííûõ äóãàìè, ïîìå÷åííûìè ñèìâîëàìèèç ìíîæåñòâà T ;  îïðåäåëÿåìîì íàìè àâòîìàòå AΓ ñóùåñòâóåò äóãà,ïîìå÷åííàÿ ñèìâîëîì a, âåäóùàÿ èç ñîñòîÿíèÿ A ∈ V â ñîñòîÿíèå B ∈ Vòîãäà è òîëüêî òîãäà êîãäà â P èìååòñÿ ïðîäóêöèÿ A → aB , è ñóùåñòâóåòäóãà, ïîìå÷åííàÿ ñèìâîëîì a, âåäóùàÿ èç ñîñòîÿíèÿ A ∈ V â ñîñòîÿíèåQ òîëüêî òîãäà êîãäà â P èìååòñÿ ïðîäóêöèÿ A → a.Ïîêàæåì, ÷òî L(Γ) = T (AΓ ). Èìååì: w = a0 a1 . . .
as ∈ L(Γ) ýêâèâàëåíòíî òîìó, ÷òî ñóùåñòâóåò âûâîäS → a0 A0 → a0 a1 A1 → . . . → a0 a1 . . . as−1 As−1 → a0 a1 . . . as−1 as = w.ΓΓΓΓΓÝòî â ñâîþ î÷åðåäü ýêâèâàëåíòíî òîìó, ÷òî â P èìåþòñÿ ñëåäóþùèåïðîäóêöèè:S→ a0 A0A0→ a1 A1...As−2→ as−1 As−1As−1→ as .Ýòî óñëîâèå ýêâèâàëåíòíî òîìó, ÷òî â àâòîìàòå AΓ èìååòñÿ ñëåäóþùàÿöåïî÷êà ïåðåõîäîâ èç îäíîãî ñîñòîÿíèÿ â äðóãîå, íà÷èíàþùàÿñÿ â íà÷àëüíîì ñîñòîÿíèè S è çàêàí÷èâàþùàÿñÿ â âûäåëåííîì ñîñòîÿíèè Q:aaaa012sS −→A0 −→A1 −→. .
. As−1 −→Q.2.6. Íåêîòîðûå ñâîéñòâà ãðàììàòèê41Ýòî, â ñâîþ î÷åðåäü ýêâèâàëåíòíî w = a0 a1 . . . as ∈ T (AΓ ). Èòàê, äëÿïðîèçâîëüíîãî ñëîâà w âûïîëíåíî w ∈ L(Γ) ⇔ w ∈ T (AΓ ), òî åñòü L(Γ) =T (AΓ ).Äîêàæåì (2). Ïóñòü A êîíå÷íûé àâòîìàò. Ïîñòðîèì ðåãóëÿðíóþãðàììàòèêó Γ, äëÿ êîòîðîé L(Γ) = T (A) \ {Λ}. Ñíà÷àëà ïðåîáðàçóåìàâòîìàò A ñîãëàñíî ëåììå î âàõòåðå è ïîòîì ñäåëàåì íà÷àëüíîå ñîñòîÿíèå ïîëó÷åííîãî àâòîìàòà íåâûäåëåííûì, åñëè îíî îêàçàëîñü âûäåëåííûì. Ïîëó÷åííûé àâòîìàò îáîçíà÷èì ÷åðåç A0 . Ëåãêî ïðîâåðèòü, ÷òîT (A0 ) = T (A) \ {Λ}. Ïîñòðîèì ãðàììàòèêó Γ = (V, T, S, P ) ñëåäóþùèìîáðàçîì: ïóñòü V áóäåò ìíîæåñòâîì ñîñòîÿíèé àâòîìàòà A0 , ïðè ýòîìïóñòü S áóäåò åãî íà÷àëüíûì ñîñòîÿíèåì; ïðîäóêöèÿ A → aB áóäåò ïðèíàäëåæàòü P òîãäà è òîëüêî òîãäà êîãäà â A0 èìååòñÿ ñòðåëêà èç A â B ,ïîìå÷åííàÿ ñèìâîëîì a; êðîìå òîãî ïðîäóêöèÿ A → a áóäåò ïðèíàäëåæàòü P òîãäà è òîëüêî òîãäà êîãäà â A0 èìååòñÿ ñòðåëêà èç A â íåêîòîðîåâûäåëåííîå ñîñòîÿíèå B , ïîìå÷åííàÿ ñèìâîëîì a.Ïðîâåðèì, ÷òî L(Γ) = T (A0 ).
Âîçüìåì ïðîèçâîëüíîå ñëîâî w = a1 . . . ak ∈L(Γ). Äëÿ íåãî ñóùåñòâóåò âûâîäS → a1 A1 → a1 a2 A2 → . . . → a1 . . . ak−1 Ak−1 → a1 . . . ak = w.ΓΓΓΓΓ ñâîþ î÷åðåäü, ýòî ýêâèâàëåíòíî òîìó, ÷òî Γ ñîäåðæèò ïðîäóêöèèS→ a1 A1A1→ a2 A2...Ak−2→ ak−1 Ak−1Ak−1→ ak .Ýòî âûïîëíåíî òîãäà è òîëüêî òîãäà, êîãäà â àâòîìàòå A0 èìåþòñÿ ñëåäóþùèé ïóòü èç ñîñòîÿíèÿ S â íåêîòîðîå âûäåëåííîå ñîñòîÿíèå Ak :aaaak−1a123kS −→A1 −→A2 −→. . . Ak−2 −→ Ak−1 −→Ak ,÷òî, â ñâîþ î÷åðåäü, ýêâèâàëåíòíî w ∈ T (A0 ). Òàêèì îáðàçîì, äëÿ ëþáîãîw âûïîëíåíî w ∈ L(Γ) ⇔ w ∈ T (A0 ), ÷òî îçíà÷àåò L(Γ) = T (A0 ).
¤42Ãëàâà 2. Êîíå÷íûå àâòîìàòû è ãðàììàòèêè2.6.2 Ðàçðåøèìîñòü íåóêîðà÷èâàþùèõ ãðàììàòèêÓ íåóêîðà÷èâàþùèõ ãðàììàòèê åñòü çàìå÷àòåëüíîå ñâîéñòâî: äëÿ íèõ∗ìîæíî óêàçàòü ïðîöåäóðó ïðîâåðêè èñòèííîñòè ñâîéñòâà α → β ïî ïðîΓèçâîëüíûì ñëîâàì α è β . Ìû ïîëó÷èì ýòî ñâîéñòâî èç ñëåäóþùåãî óòâåðæäåíèÿ:Ïðåäëîæåíèå 2.6.2 Ïóñòü Γ = (V, T, P, S) íåóêîðà÷èâàþùàÿ ãðàì∗ìàòèêà.
Òîãäà åñëè α → β, òî â Γ ñóùåñòâóåò âûâîäΓα → . . . → β,ΓΓñîäåðæàùèé íå áîëåå, ÷åì (|β| + 1) · |V ∪ T ||β| ñëîâ7 . (Çäåñü ÷åðåç |X|îáîçíà÷åíî ÷èñëî ýëåìåíòîâ â êîíå÷íîì ìíîæåñòâå X .)Ïðåäïîëîæèì, ÷òî â ãðàììàòèêå Γ ñóùåñòâóåò âûâîäα = α0 → α1 → . . . → αn = β.ΓΓΓ(2.4)Ïîñêîëüêó ãðàììàòèêà Γ íåóêîðà÷èâàþùàÿ, äëÿ äëèí ñëîâ âûïîëíÿåòñÿòàêæå|α0 | ≤ |α1 | ≤ . . . ≤ |αn | . ñèëó ýòîãî âûâîä (2.4) åñòåñòâåííûì îáðàçîì ðàçáèâàåòñÿ íà ñëåäóþùèå äðóã çà äðóãîì (âîçìîæíî ïóñòûå) ó÷àñòêè ñ ïîñòîÿííîé äëèíîéñëîâ: ñíà÷àëà ñëåäóþò ñëîâà äëèíû |α0 |, ïîòîì ñëîâà äëèíû |α0 | + 1,äëèíû |α0 | + 2 è ò. ä. Ðàññìîòðèì òàêîé ó÷àñòîê âûâîäà (2.4), ñîñòîÿùèé èç âñåõ ñëîâ äëèíû m. Êîëè÷åñòâî ñëîâ äëèíû m íàä àëôàâèòîìV ∪ T ðàâíî |V ∪ T |m . Ïîýòîìó åñëè ó÷àñòîê âûâîäà (2.4), ñîñòîÿùèé èçâñåõ ñëîâ äëèíû m, ñîäåðæèò áîëåå ÷åì |V ∪ T |m ýëåìåíòîâ, òî ñðåäèíèõ íàéäóòñÿ äâà îäèíàêîâûõ ñëîâà, ñêàæåì αi = αj , i < j , è ïîýòîìóöåïî÷êó ìîæíî óêîðîòèòü, âûðåçàâ èç íåå âñå ýëåìåíòû, íà÷èíàÿ ñ αiè äî αj−1 âêëþ÷èòåëüíî.
Ïîñëå ýòîãî âûâîä îñòàåòñÿ âûâîäîì. Óäàëèâèç âûâîäà (2.4) âñå òàêèå ó÷àñòêè, ìîæíî ïðèâåñòè ýòîò âûâîä ê òàêîìóâèäó, ÷òî ëþáîé åãî ó÷àñòîê, ñîñòîÿùèé èç âñåõ ñëîâ äëèíû m, ñîäåðæèò íå áîëåå, ÷åì |V ∪ T |m ñëîâ. Òàêîé âûâîä ñîäåðæèò íå áîëåå ÷åì7Êîíêðåòíûé âèä ýòîé ôóíêöèè íå ïðåäñòàâëÿåò èíòåðåñà. Çäåñü âàæíî ñóùåñòâîâàíèå õîòü êàêîé-òî îãðàíè÷èâàþùåé ôóíêöèè, çàïèñûâàåìîé íåñëîæíîé ôîðìóëîé.2.6. Íåêîòîðûå ñâîéñòâà ãðàììàòèê43|V ∪ T ||α0 | + |V ∪ T ||α0 |+1 + . . . |V ∪ T ||αn | ñëîâ. Îöåíèâàÿ ñâåðõó êàæäîåèç ñëàãàåìûõ âûðàæåíèåì |V ∪ T ||αn | , è äîáàâëÿÿ â íåå åñëè ïîòðåáóåòñÿ íîâûå ïîëîæèòåëüíûå ñëàãàåìûå, ìû ïîëó÷èì, ÷òî ýòó ñóììó ìîæíî îöåíèòü ñâåðõó âûðàæåíèåì (|αn | + 1) · |V ∪ T ||αn | . Ââèäó òîãî, ÷òî|αn | = |β|, ýòî äîêàçûâàåò óòâåðæäåíèå.¤∗Óêàæåì òåïåðü ñïîñîá ïðîâåðêè ñâîéñòâà α → β äëÿ íåóêîðà÷èâàþΓùèõ ãðàììàòèê.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
