Kailangan ng isang non-deterministic na makina ng estado M = (Q, T, D, q 0 , F) bumuo ng isang deterministikong may hangganan na makina ng estado M = (Q", T, D", q" 0 , F"). Ang paunang estado para sa automat na nasa ilalim ng konstruksiyon ay ang ε-pagsasara ng paunang estado ng paunang automat. ε-closure - isang set ng mga estado na maaabot mula sa isang ibinigay na isa sa pamamagitan ng mga transition kasama ang ε. Dagdag pa, habang may mga estado kung saan ang mga transition ay hindi pa nagagawa (ang mga transition ay ginawa sa pamamagitan ng mga simbolo, ang mga transition na kung saan ay nasa orihinal na automat), para sa bawat simbolo, ang ε-pagsasara ng hanay ng mga estado na maaabot mula sa itinuturing na estado sa pamamagitan ng paglipat sa pamamagitan ng itinuturing na simbolo ay kinakalkula. Kung ang estado na tumutugma sa nahanap na hanay ay umiiral na, pagkatapos ay isang paglipat ay idinagdag doon. Kung hindi, idaragdag ang bagong natanggap na estado.

Halimbawa

Pagsisimula

Ang mga estado na naaayon sa ε-pagsasara ng paunang estado ay minarkahan. Ang mga estadong ito ay tumutugma sa estado A hinaharap DKA.

Unang pag-ulit

May mga transition mula sa ε-closure hanggang sa NCA states 3 at 10 (ayon sa a at c, ayon sa pagkakabanggit). Para sa state 3, ang ε-closure ay ang set ng states (3, 4, 6), para sa state 10 - (10). Italaga natin ang mga bagong estado ng DFA na naaayon sa mga set na ito bilang B at C.

estado ng DKA	Set ng mga estado ng NFA
		a	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	-	-
C	{10}	-	-	-

Pangalawang pag-ulit

Mula sa hanay ng mga estado ng NFA (3, 4, 6) na tumutugma sa estado ng DFA B mayroong dalawang paglipat - sa estado 5 (sa pamamagitan ng b) at 7 (ni c). Ang kanilang ε-closures ay nagsalubong, ngunit ang mga set mismo ay naiiba, kaya sila ay itinalaga ng dalawang bagong DFA states - D at E. Mula sa mga estado ng NFA na naaayon sa estado ng DFA C, walang mga transition.

estado ng DKA	Set ng mga estado ng NFA	Jumpable na mga character
		a	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	-	-	-
E	{2, 7, 8, 9}	-	-	-

Pangatlong pag-ulit

Mula sa mga hanay ng mga estado ng NFA na naaayon sa mga estado ng DFA D at E ginagawa ang mga paglipat sa mga hanay ng mga estado na naaayon sa mga umiiral na estado (mula sa hanay (2, 5, 8, 9) na tumutugma sa estado D, sa a paglipat sa estado 3 na kabilang sa set (3, 4, 6) na tumutugma sa estado ng DFA B, sa c- paglipat sa estado 10 na naaayon sa estado C; katulad din para sa set na tumutugma sa estado ng DFA E). Ang proseso ng pagbuo ng talahanayan ng mga estado at mga paglipat ng DFA ay nakumpleto.

estado ng DKA	Set ng mga estado ng NFA	Jumpable na mga character
		a	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	B	-	C
E	{2, 7, 8, 9}	B	-	C

Resulta:

Pagbuo ng isang right-linear na grammar mula sa isang may hangganan na automat

Ang bawat estado ay nauugnay sa isang hindi terminal. Kung mayroong paglipat ng estado X sa isang estado Y sa a, idagdag ang panuntunan X → aY. Para sa mga huling estado, magdagdag ng mga panuntunan X→ e. Para sa ε-transition - X → Y.

Halimbawa 1 (deterministic state machine)

• A → a b | c C
• B → b D | c E
• C → e
• D → a b | c C
• E → a b | c C

Halimbawa 2 (non-deterministic state machine)

• 1 → 2 | 9
• 2 → a 3
• 3 → 4 | 6
• 4 → b 5
• 5 → 8
• 6 → c 7
• 7 → 8
• 8 → 2 | 9
• 9 → c 10
• 10 → ε

Konstruksyon ng DFA sa pamamagitan ng RV

Magkaroon tayo ng isang regular na expression r. Batay sa regular na expression na ito, kinakailangan na bumuo ng isang deterministikong finite automat D ganyan L(D) = L(r).

Regular na pagbabago sa expression

Magdagdag tayo ng simbolo dito, ibig sabihin ang dulo ng RV - "#". Bilang resulta, nakakakuha kami ng isang regular na expression ( r)#.

Paggawa ng puno

Isipin natin ang isang regular na expression bilang isang puno, ang mga dahon nito ay ang mga terminal na character, at ang mga panloob na node ay ang mga operasyon ng concatenation ".", unyon "∪" at pag-ulit "*". Nagtatalaga kami ng natatanging numero sa bawat dahon ng puno (maliban sa ε-dahon) at tinutukoy ito, sa isang banda, bilang posisyon sa puno at, sa kabilang banda, bilang posisyon ng simbolo na tumutugma sa dahon.

Pagkalkula ng mga function na nullable, firstpos, lastpos

Ngayon, binabagtas ang puno T mula sa ibaba hanggang sa itaas mula kaliwa hanggang kanan, kinakalkula namin ang tatlong function: nullable, firstpos, at lastpos. Mga pag-andar nullable, firstpos at lastpos tinukoy sa mga node ng puno. Ang halaga ng lahat ng mga function maliban nullable, ay ang hanay ng mga posisyon. Function firstpos(n) para sa bawat node n ng regex syntax tree ay nagbibigay ng hanay ng mga posisyon na tumutugma sa mga unang character sa mga substring na nabuo ng subexpression na nagtatapos sa n. Gayundin, lastpos(n) ay nagbibigay ng hanay ng mga posisyon na tumutugma sa mga huling character sa mga substring na nabuo ng mga subexpression na may tuktok n. Para sa mga node n, na ang mga subtree (iyon ay, isang puno na ang node n ay isang ugat) ay maaaring makabuo ng isang walang laman na salita, tinutukoy namin nullable(n) = totoo, at para sa iba pang mga node mali. Talahanayan upang kalkulahin nullable, firstpos, lastpos:

buhol n	nullable(n)	firstpos(n)	lastpos(n)
ε	totoo	∅	∅
i ≠ ε	mali	{i}	{i}
ikaw ∪ v	nullable(u) o nullable(v)	firstpos(u) ∪ firstpos(v)	lastpos(u) ∪ lastpos(v)
ikaw . v	nullable(u) at nullable(v)	kung nullable(u) pagkatapos firstpos(u) ∪ firstpos(v) iba pa firstpos(u)	kung nullable(v) pagkatapos lastpos(u) ∪ lastpos(v) iba pa lastpos(v)
v*	totoo	firstpos(v)	lastpos(v)

Mga followpos ng gusali

Function followpos kinakalkula sa pamamagitan ng nullable, firstpos at lastpos. Function followpos tinukoy sa maraming posisyon. Ibig sabihin followpos ay isang hanay ng mga posisyon. Kung ang i- posisyon, pagkatapos followpos(i) maraming posisyon j parang may string... cd... kasama sa wikang inilarawan ng RW, tulad na i tumutugma sa entry na ito c, a j- pagpasok d. Function followpos ay maaari ding kalkulahin sa isang traversal ng puno ayon sa sumusunod na dalawang panuntunan

1. Hayaan n- panloob na node na may "." (pagsasama-sama); a, b- kanyang mga inapo. Pagkatapos para sa bawat posisyon i kasama sa lastpos(a followpos(i) isang grupo ng firstpos(b).
2. Hayaan n- panloob na node na may "*" na operasyon (iteration), a- ang kanyang inapo. Pagkatapos para sa bawat posisyon i kasama sa lastpos(a), idagdag sa hanay ng mga halaga followpos(i) isang grupo ng firstpos(a).

Halimbawa

I-compute ang halaga ng function followpos para sa regular na pagpapahayag ( a(b|c))*c.

Posisyon	Ibig sabihin followpos
1: (a (b|c))*c	{2, 3}
2: (a(b |c))*c	{1, 4}
3: (a(b|c ))*c	{1, 4}
4: (a(b|c))*c	{5}

Pagbuo ng isang DFA

Ang DFA ay isang set ng mga estado at isang set ng mga transition sa pagitan nila. Ang estado ng DFA ay isang hanay ng mga posisyon. Ang pagtatayo ng isang DFA ay binubuo sa unti-unting pagdaragdag ng mga kinakailangang estado dito at ang pagtatayo ng mga paglipat para sa kanila. Sa una, mayroong isang estado firstpos(ugat) (ugat- ang ugat ng puno), na walang mga transition. Ang paglipat ay isinasagawa ng mga character mula sa regular na expression. Ang bawat karakter ay tumutugma sa isang hanay ng mga posisyon ( p i). Pinagkakaisa ang lahat followpos(x) ay ang estado kung saan kinakailangang puntahan, kung saan ang x ay isang posisyon na naroroon kapwa sa mga posisyon ng estado at kabilang sa mga posisyon ng simbolo mula sa RE, kung saan ginawa ang paglipat. Kung walang ganoong estado, dapat itong idagdag. Dapat na ulitin ang proseso hanggang sa mabuo ang lahat ng transition para sa lahat ng estado. Ang lahat ng estado na naglalaman ng posisyon ng # simbolo na idinagdag sa dulo ng RE ay idineklara na pinal.

DFA na nakuha mula sa RV ( a(b|c))*c

Halimbawa

Bumuo ng DFA sa pamamagitan ng regular na expression ( a(b|c))*c.

estado ng DKA	Simbolo
	a(1)	b(2)	c(3, 4)
A(1, 4)	B(2, 3)	-	C(5)
B(2, 3)	-	A(1, 4)	A(1, 4)
C(5)	-	-	-

Pagbuo ng isang DFA na may pinakamababang bilang ng mga estado

Ang isang DFA na may pinakamababang bilang ng mga estado ay binuo para sa isang tinukoy na DFA sa lahat ng dako, ibig sabihin. ganyan . Para sa anumang DFA, mayroong isang katumbas na DFA na tinukoy sa lahat ng dako.

Pagbuo ng isang DFA na tinukoy sa lahat ng dako

Magpakilala ng bagong estado at tumukoy ng bagong hanay ng mga estado .

Tukuyin natin ang isang bagong function ng transition tulad nito:

Pagbuo ng partition (pormal)

Buuin natin ang paunang partisyon P hanay ng mga estado sa dalawang pangkat: mga huling estado F at iba pa S/F, ibig sabihin. P = {F, Q\F}.

Ilapat sa bawat pangkat G ∈ P sumusunod na pamamaraan. basagin G sa mga subgroup upang ang mga estado s at t mula sa G napunta sa parehong grupo kung at kung para lamang sa bawat input na simbolo a estado s at t may mga transition a sa mga estado mula sa parehong grupo sa P.

Ang mga resultang subgroup ay idinagdag sa bagong partition P bago.

Tanggapin P = P bago at ulitin ang pagtatayo ng partisyon hanggang sa pag-stabilize, ibig sabihin, hanggang sa tumigil ang pagbabago ng partisyon.

Pagbuo ng partition (algorithm)

Upang makabuo ng isang partisyon, mayroong sumusunod na algorithm. Bumubuo kami ng isang talahanayan ng paglipat para sa orihinal na automat, bumuo ng isang paunang partisyon.

Nagtatalaga kami ng identifier sa bawat grupo mula sa partition (para sa unang partition, halimbawa, 0 at 1).

Ang bawat estado (bawat hilera ng talahanayan) ay itinalaga ng isang string ng form na "a.bcd...xyz", kung saan ang identifier ng pangkat kung saan ang estado ay kabilang sa [unang column (kung saan tayo nagmula), ang pangalawa. column (kung saan tayo pupunta sa pamamagitan ng unang character), ..., ang huling column (kung saan tayo pupunta sa huling character)].

Bumubuo kami ng mga bagong grupo ayon sa pagkakaisa ng mga string, ibig sabihin, upang ang mga estado na may parehong nakatalagang mga string ay mahulog sa isang grupo.

Pagkatapos, isang bagong pag-ulit. Nagtatalaga kami ng mga bagong identifier sa mga resultang grupo, halimbawa (0, 1, ..., n). At inuulit namin ang pagtatayo ng partisyon hanggang sa pag-stabilize.

Tandaan na kapag may isang estado na natitira sa grupo, sa mga susunod na yugto ng pagbuo ng partition, hindi mo na maisusulat ang string ng mga identifier para sa estado na ito, dahil ang string na ito ay magiging kakaiba sa anumang kaso dahil sa unang character ng string. Sa madaling salita, kapag naghahati, walang mangyayari sa isang grupo mula sa isang estado - ito ay ililipat sa isang bagong hati.

Konstruksyon ng pinababang automat

Ang bawat isa sa mga resultang grupo ay nagiging estado ng isang bagong DFA. Kung ang pangkat ay naglalaman ng paunang (panghuling) estado ng orihinal na automat, ang pangkat na ito ay magiging paunang (ayon sa pagkakabanggit pangwakas) na estado ng bagong DFA. Ang mga paglipat ay binuo sa isang malinaw na paraan: ang isang paglipat sa isang estado mula sa isang pangkat ay itinuturing na isang paglipat sa isang pangkat.

Dala namin ang makina. Inalis muna namin ang hindi bumubuo (sterile, "patay"), pagkatapos hindi maabot na mga estado (ibinigay ang mga kahulugan para sa mga simbolo, ngunit sa isang malinaw na paraan ay inililipat sila sa mga estado ng automat).

Sa pangkalahatan, ang pag-alis ng mga patay na estado ay gagawing NFA ang isang DFA, dahil sa isang DFA ang lahat ng mga transition ay dapat tukuyin. Gayunpaman, sa Dragon Book, ang naturang paglihis mula sa pormal na kahulugan ay itinuturing pa ring katanggap-tanggap.

Halimbawa

Upang bumuo ng isang DFA na may pinakamababang bilang ng mga estado para sa isang DFA ng sumusunod na form:

• Paunang hati: (C) ( pangwakas na estado), (A, B, D, E) ( lahat ng iba pang estado).
• (C)( walang pagbabago), (A, D, E), (B), ( dahil dumadaan kami mula sa A, D, E kasama ang a, c hanggang B at C, ayon sa pagkakabanggit).
• Wala na tayong magagawa pa.

Hayaang tumutugma ang pangkat (C) sa estado C, pangkat (A, D, E) sa estado A, at pangkat (B) sa estado B. Pagkatapos ay kumuha kami ng DFA na may pinakamababang bilang ng mga estado:

Halimbawa (algorithm para sa pagbuo ng partition)

Isang talahanayan ng paglipat para sa isang tinukoy sa lahat ng dako (idinagdag ang estado Z) DFA na tumutugma sa RV (ab|ε)a*|abb|b*a. Mula sa mga tanong sa pagsusulit noong 2012.

	a	b	ako 0	ako 1
→A*	B	C	0.01	0.12
B*	D	E	0.00	1.01
C	F	C	1.01
D*	D	Z	0.01	0.04
E*	D	Z	0.00	1.03
F*	Z	Z	0.11
Z	Z	Z	1.11

Mga Pag-ulit:

• I 0: ABCDEF(0), CZ(1).
• I 1: AD(0), BE(1), C(2), F(3), Z(4).
• I 2: A, B, C, D, E, F, Z.

Resulta: ang makina ay mayroon nang pinakamababang bilang ng mga estado :-)

DFA na nagpapahintulot sa pagkumpleto ng wika

Ang algorithm para sa pagbuo ng isang DFA na tumatanggap ng pandagdag ng wikang L (L̅) ay binubuo ng dalawang hakbang:

• Pagbuo ng kumpletong DFA
• Konstruksyon ng nais na automat mula dito

Sa katunayan, walang ganap na DFA. Sa ilalim ng buong DKA ilang naiintindihan ng mga guro ang automat, sa talahanayan ng paglipat kung saan walang mga walang laman na cell. Gayunpaman, ayon sa kahulugan ng DFA - δ: Q × Σ → Q - hindi maaaring magkaroon ng walang laman na mga cell sa anumang kaso. Ang automat "na may mga walang laman na cell", gayunpaman, ay nakakatugon sa kahulugan ng NFA. Sa kurso ng paglutas, hindi karaniwan na makakuha lamang ng ganoong NFA, na kulang lamang sa mga transition bago ang DFA.

Upang mapunan ito, sapat na upang magdagdag ng isang bagong estado X, at "sa halip na" hindi umiiral na mga transition ay nagdaragdag ng mga transition sa bagong estadong ito. Huwag kalimutang magdagdag ng mga transition mula sa X sa X. Madaling makita na kung saan ang orihinal na automat ay hindi tumanggap ng ilang kadena dahil sa kawalan ng isang paglipat, ang bagong automat ay mapupunta sa estado X at mabitin dito. Dahil ang bagong estado ay hindi isang accepting (final) na estado, hindi rin tatanggapin ng bagong automat ang chain na ito.

Ngayon, upang mabuo ang nais na automat, kinakailangan lamang na baguhin ang mga tungkulin ng pagtanggap at hindi pagtanggap na mga estado. Sa madaling salita, F" = Q \ F.

Pagbuo ng LL(k) analyzer

Pagbabago ng gramatika

Hindi lahat ng grammar ay LL(k)-parsable. Ang isang grammar na walang konteksto ay kabilang sa klase ng LL(1) kung wala itong FIRST-FIRST na mga salungatan (ang kaliwang recursion ay isang espesyal na kaso ng naturang salungatan) at FIRST-FOLLOW.

Minsan posibleng ibahin ang anyo ng mga di-LL(1) na gramatika upang maging LL(1) ang mga ito. Ang ilan (mas tiyak, ang mga isinasaalang-alang sa kurso) mga pagbabago ay ibinigay sa ibaba.

Pag-alis ng kaliwang recursion

Ipagpalagay na mayroon kaming isang tuntunin ng form (simula dito sa seksyong ito, malalaking titik - mga simbolo na hindi terminal, maliit na titik - chain ng anumang mga character):

• A→A a| A b| … | A k | m | n | … | z

Hindi ito pumapayag sa hindi malabo na pagsusuri, kaya dapat itong i-convert.

Madaling ipakita na ang panuntunang ito ay katumbas ng sumusunod na pares ng mga panuntunan:

• A → m b | n b | … | z B
• B → a b | b b | … | k b | ε

Kaliwang factorization

Ang kakanyahan ng pamamaraang ito ay ang pag-aalis ng kalabuan sa pagpili ng mga patakaran para sa kaliwang karakter. Upang gawin ito, ang isang karaniwang kaliwang prefix ay matatagpuan at kung ano ang maaaring sumunod dito ay kinuha sa isang bagong panuntunan (maliit na titik - chain ng anumang mga character)

Halimbawa

• A → a c | a df | a dg | b

Pinalitan sa

• A → a b | b
• B → c | d f | d g

na nagiging

• A → a b | b
• B → c | d Sa
• C → f | g

Halimbawa ng Grammar Conversion

G= ((S, A, B), (a, b, c), P, S)

• S→SAbB | a
• A→ab | aa | ε
• B → c | ε

Pag-alis ng kaliwang recursion para sa S:

• S → aS 1
• S 1 → AbBS 1 | ε

Kaliwang factorization para sa A:

• A → aA 1 | ε
• A 1 → b | a

Panghuling gramatika:

• S → aS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

Building MUNA at SUNDIN

FIRST(α), kung saan ang α ∈ (N ∪ T)* ay ang set ng mga terminal kung saan maaaring magsimula ang α. Kung α ⇒ ε, pagkatapos ay ε ∈ FIRST(α). Alinsunod dito, ang halaga ng FOLLOW( A) para sa hindi terminal A- maraming mga terminal na maaaring lumitaw kaagad pagkatapos A sa ilang sentimental na anyo. Kung ang A maaaring ang pinaka-rightmost character sa ilang sentential form, kung gayon ang huling $ token ay kabilang din sa FOLLOW( A)

UNANG pagkalkula

Para sa mga terminal

• Para sa anumang terminal x, x ∈ T, UNA( x) = {x}

Para sa mga hindi terminal

• Kung ang X ay isang non-terminal, pagkatapos ay inilalagay namin ang FIRST( X) = {∅}
• Kung may tuntunin ang gramatika X→ ε, pagkatapos ay idagdag ang ε sa FIRST( X)
• Para sa bawat hindi terminal X at para sa bawat tuntunin ng hinuha X → Y 1 …Y k idagdag sa FIRST( X) ang nakatakdang UNA sa lahat ng mga simbolo sa kanang bahagi ng panuntunan hanggang sa una kung saan hindi nagmula ang ε, kasama ang

Para sa mga kadena

• Para sa string ng character X 1 …X k FIRST ay ang unyon ng UNANG mga character na kasama sa string hanggang sa una, na mayroong ε ∉ FIRST, kasama ito.

Halimbawa

• S → aS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

UNANG hindi terminal sa pagkakasunud-sunod ng paglutas ng dependency:

• UNANG(S) = (a)
• UNANG(A) = (a, ε)
• UNANG(A 1) = (b, a)
• UNANG(B) = (c, ε)
• UNANG(S 1) = (a, b, ε)

UNANG para sa mga panuntunan sa hinuha:

• UNANG(aS 1) = (a)
• UNANG(AbBS 1) = (a, b)
• UNANG(ε) = (ε)
• UNANG(aA 1) = (a)
• UNANG(a) = (a)
• UNANG(b) = (b)
• UNANG(c) = (c)

SUNDIN ang pagkalkula

Pag-compute ng FOLLOW function para sa character X:

• Hayaan ang SUNOD(X) = (∅)
• Kung ang X ay isang grammar axiom, pagkatapos ay idagdag ang marker na $ sa SUNDIN
• Para sa lahat ng panuntunan ng form A → αXβ idagdag ang FIRST(β)\(ε) sa FOLLOW(X) (X ay maaaring sundan ng mga character na nagsisimula sa β)
• Para sa lahat ng panuntunan ng form A → αX at A → αXβ, ε ∈ FIRST(β), idagdag ang FOLLOW(A) sa FOLLOW(X) (iyon ay, X ay maaaring sundan ng lahat ng character na maaaring sumunod sa A, kung nasa ang inference rule, ang X ay maaaring nasa dulong kanan)
• Ulitin ang nakaraang dalawang talata hangga't posible na magdagdag ng mga character sa set

Halimbawa

• S → aS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

Resulta:

• SUNDIN (S) = ($)
• SUNDIN(S 1) = ($) (S 1 ay ang pinakakanang karakter sa panuntunan S → aS 1)
• SUNDIN(A) = (b) (A sa panuntunan S 1 → AbBS 1 ay sinusundan ng b)
• FOLLOW(A 1) = (b) (Ang A 1 ay ang pinakakanang character sa panuntunan A → aA 1 , kaya idinaragdag ang FOLLOW(A) sa FOLLOW(A 1))
• FOLLOW(B) = (a, b, $) (idagdag ang FIRST(S 1)\(ε) (sumusunod mula sa rule S 1 → AbBS 1), FOLLOW(S 1) (dahil mayroong S 1 → ε))

Pag-compile ng table

mesa M para sa isang non-terminal-terminal na pares (sa cell M[A, a]) ay tumutukoy sa panuntunan kung saan dapat bawasan ang input na salita. Ang talahanayan ay pinupunan bilang mga sumusunod: para sa bawat panuntunan ng inference ng isang ibinigay na grammar A → α (kung saan ang α ay nauunawaan bilang isang chain sa kanang bahagi ng panuntunan), ang mga sumusunod na aksyon ay isinasagawa:

1. Para sa bawat terminal a∈ FIRST(α) magdagdag ng panuntunan A → α sa M[A, a]
2. Kung ε ∈ FIRST(α), para sa bawat isa b∈ SUNDIN( A) idagdag A → α sa M[A, b]
3. ε ∈ FIRST(α) at ​​$ ∈ FOLLOW( A), idagdag A → α sa M[A, $]
4. Ang lahat ng mga walang laman na cell ay isang error sa input na salita

Halimbawa

Bumuo ng talahanayan para sa gramatika

• S → aS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

Resulta:

	a	b	c	$
S	S → aS 1 (Unang tuntunin, hinuha S → aS 1 , a ∈ UNANG(aS 1))	pagkakamali (Ikaapat na panuntunan)	pagkakamali (Ikaapat na panuntunan)	pagkakamali (Ikaapat na panuntunan)
S1	S 1 → AbBS 1 (Unang panuntunan, output S 1 → AbBS 1 , a ∈ FIRST(AbBS 1))	S 1 → AbBS 1 (Unang panuntunan, output S 1 → AbBS 1 , b ∈ FIRST(AbBS 1))	pagkakamali (Ikaapat na panuntunan)	S 1 → ε (Ikatlong tuntunin, hinuha S 1 → ε, ε ∈ UNA(ε), $ ∈ SUNDIN(S 1))
A	A → aA 1 (Unang tuntunin, output A → aA 1 , a ∈ FIRST(aA 1))	A→ε (Ikalawang tuntunin, output A 1 → ε, b ∈ SUNDIN(A 1))	pagkakamali (Ikaapat na panuntunan)	pagkakamali (Ikaapat na panuntunan)
A 1	A 1 → a (Unang tuntunin, output A 1 → a, a ∈ FIRST(a))	A 1 → b (Unang panuntunan, output A 1 → b, b ∈ UNANG(b))	pagkakamali (Ikaapat na panuntunan)	pagkakamali (Ikaapat na panuntunan)
B	B→e	B→e (Ikalawang tuntunin, hinuha B → ε, a ∈ SUNDIN(B))	B → c (Unang panuntunan, output B → c, c ∈ FIRST(c))	B→e (Ikatlong panuntunan, hinuha B → ε, $ ∈ SUNDIN(B))

Pag-parse ng string

Ang proseso ng pag-parse ng isang string ay medyo simple. Ang kakanyahan nito ay ang mga sumusunod: sa bawat hakbang, binabasa ang tuktok na simbolo v c input chain.

• Kung ang v- simbolo ng terminal
  • Kung ang v sumasabay sa kasama, tapos pareho silang nawasak, may shift
  • Kung ang v hindi tumutugma sa kasama, pagkatapos ay may senyales na error sa pag-parse
• Kung ang v- simbolo na hindi terminal, c babalik sa simula ng linya sa halip na v ang kanang bahagi ng panuntunan, na kinuha mula sa cell ng talahanayan, ay ibinalik sa stack M[v, c]

Ang proseso ay nagtatapos kapag ang string at ang stack ay umabot na sa dulong marker (#).

Halimbawa

I-parse natin ang string na "aabbaabcb":

salansan	linya	aksyon
S#	a abbaabcb$	S → aS 1
a S1#	a abbaabcb$	shift
S1#	a bbaabcb$	S 1 → AbBS 1
A bbs 1#	a bbaabcb$	A → aA 1
a A 1 bBS 1 #	a bbaabcb$	shift
A 1 bbs 1#	b baabcb$	A 1 → b
b bbs 1#	b baabcb$	shift
b B.S. 1#	b aabcb$	shift
B S1#	a abcb$	B→e
S1#	a abcb$	S 1 → AbBS 1
A bbs 1#	a abcb$	A → aA 1
A bbs 1#	a abcb$	A → aA 1
a A 1 bBS 1 #	a abcb$	shift
A 1 bbs 1#	a bcb$	A 1 → a
a bbs 1#	a bcb$	shift
b B.S. 1#	b cb$	shift
B S1#	c b$	B → c
c S1#	c b$	shift
S1#	b$	S 1 → AbBS 1
A bbs 1#	b$	A→ε
b B.S. 1#	b$	shift
B S1#	$	B→e
S1#	$	S 1 → ε
#	$	handa na

Pagbuo ng LR(k) analyzer

Pag-compute ng k sa LR(k)

Walang algorithm na magpapahintulot, sa pangkalahatang kaso, na kalkulahin ang k para sa isang arbitraryong gramatika. Karaniwang sulit na subukang bumuo ng LR(1) parser. Kung mayroon itong hindi hihigit sa isang operasyon bawat set (Shift, Bawasan, o Tanggapin), kung gayon ang grammar ay LR(0). Kung, gayunpaman, ang isang salungatan at banggaan ay naganap sa pagbuo ng isang LR(1) parser, kung gayon ang grammar na ito ay hindi LR(1) at ito ay nagkakahalaga ng pagsubok na bumuo ng LR(2). Kung nabigo itong itayo, pagkatapos ay LR(3) at iba pa.

Pagkumpleto ng gramatika

Magdagdag tayo ng bagong panuntunan S" → S, at gawin ang S" na axiom ng grammar. Ang karagdagang panuntunang ito ay kinakailangan upang matukoy kung kailan magwawakas ang analyzer at pinapayagan ang input chain. Ang pagpasok ay nagaganap kung at kung posible lamang na magsagawa ng convolution ayon sa panuntunan S → S".

Pagbuo ng isang kanonikal na sistema ng mga hanay ng mga tinatanggap na LR(1)-mga sitwasyon

Sa simula, mayroong isang set I 0 na may pagsasaayos ng analyzer S" → .S, $. Pagkatapos, ang pagsasara ng operasyon ay inilapat sa pagsasaayos na ito hanggang, bilang resulta ng aplikasyon nito, walang mga bagong pagsasaayos na idinagdag. Susunod , ang mga transition sa mga bagong set ay ginagawa sa pamamagitan ng paglilipat ng punto ng isang character pakanan (ang mga paglukso ay ginawa ng character na pagkatapos ng tuldok bago ang pagtalon at bago ito pagkatapos ng pagtalon), at ang mga pagsasaayos na nakuha mula sa mga umiiral na. sa ganitong paraan ay idinaragdag sa mga set na ito. Ang pagsasara ng operasyon ay inilalapat din sa mga ito, at ang buong proseso ay paulit-ulit hanggang sa wala nang mga bagong hanay na lilitaw.

Halimbawa

Bumuo ng isang kanonikal na sistema ng mga hanay ng mga tinatanggap na LR(1)-mga sitwasyon para sa tinukoy na grammar:

• S" → S
• S → ABA
• A → Aa | ε
• B → cBc | d

Desisyon:

• Bumuo kami ng pagsasara para sa configuration S" → .S, $:
  • S → .ABA,$
• Para sa mga resultang configuration (S → .ABA, $) bumuo din kami ng pagsasara:
  • A → .Aa, c
  • A → .Aa, d
  • A → .,c
  • A → ., d
• Para sa mga resultang pagsasaayos (A → .Aa, c; A → .Aa, d) gumagawa din kami ng pagsasara:
  • A → .Aa, a
  • A → ., a
• Wala nang mga pagsasaayos sa I 0 na estado ang maaaring itayo - ang pagsasara ay binuo

• Mula sa I 0, maaari kang gumawa ng mga paglipat sa kahabaan ng S at A at makakuha ng isang hanay ng mga pagsasaayos I 1 at I 2, na binubuo ng mga sumusunod na elemento:
  • I 1 = (S" → S., $)
  • I 2 = (S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, a)
• I 1 ay hindi nangangailangan ng pagsasara
• Buuin natin ang pagsasara I 2:
  • B → .cBc, a
  • B → .cBc, $
  • B → .d, a
  • B → .d, $
• Ang lahat ng iba pang mga set ay itinayo nang katulad.

Pagbuo ng parser table

Ang huling hakbang sa pagbuo ng LR(1) parser ay pagbuo ng mga talahanayan aksyon at pumunta sa. mesa aksyon binuo para sa mga character ng input string, ibig sabihin, para sa mga terminal at end-of-line marker $, table pumunta sa ay binuo para sa mga simbolo ng grammar, ibig sabihin, para sa mga terminal at hindi terminal.

Pagbuo ng Goto Table

Ipinapakita ng talahanayan ng Goto kung aling estado ang pupuntahan kapag nakatagpo ang susunod na simbolo ng grammar. Samakatuwid, kung sa canonical system ng mga hanay mayroong isang paglipat mula sa ako i sa Ij sa pamamagitan ng simbolo A, pagkatapos ay sa Goto( ako i, A) inilalagay namin ang estado ako j. Matapos punan ang talahanayan, ipinapalagay namin na sa lahat ng walang laman na mga cell Goto( ako i, A) = Error

Pagbuo ng talahanayan ng Mga Pagkilos

• Kung mayroong paglipat sa terminal a mula sa estado I i patungo sa estado I j , pagkatapos ay Aksyon(I i , a) = Shift(I j)
• Kung A ≠ S" at mayroong configuration A → α., a, pagkatapos Action(I i , a) = Reduce(A → α)
• Para sa isang estado I i na may configuration S" → S., $, Action(I i , $) = Tanggapin
• Para sa lahat ng walang laman na mga cell Action(I i , a) = Error

Halimbawa

Bumuo ng Action at Goto na mga talahanayan para sa grammar

• S" → S
• S → ABA
• A → Aa | ε
• B → cBc | d

Desisyon:

	aksyon				pumunta sa
	a	c	d	$	S	S"	A	B	a	c	d
ako 0	Bawasan(A → ε)	Bawasan(A → ε)	Bawasan(A → ε)		ako 1		ako 2
ako 1				Tanggapin
ako 2	Shift(I 6)	Shift(I 4)	Shift(I 5)					ako 3	ako 6	ako 4	ako 5
ako 3	Bawasan(A → ε)			Bawasan(A → ε)			ako 13
ako 4		Shift(I 8)	Shift(I 9)					ako 7		ako 8	ako 9
ako 5	Bawasan(B → d)			Bawasan(B → d)
ako 6	Bawasan(A → Aa)	Bawasan(A → Aa)	Bawasan(A → Aa)
ako 7		Shift(I 10)								ako 10
ako 8		Shift(I 8)	Shift(I 9)					ako 11		ako 8	ako 9
ako 9		Bawasan(B → d)
ako 10	Bawasan(B → cBc)			Bawasan(B → cBc)
ako 11		Shift(I 12)								ako 12
ako 12		Bawasan(B → cBc)
ako 13	Shift(I 14)			Bawasan(S → ABA)					ako 14
ako 14	Bawasan(A → Aa)			Bawasan(A → Aa)

Pag-parse ng chain

Sa bawat hakbang, binabasa ang nangungunang karakter v mula sa stack ng analyzer at kunin ang huling character c input chain.

Kung nasa talahanayan ng mga aksyon sa intersection v at c matatagpuan:

• shift( ako k), pagkatapos ay ilagay sa stack kasama at pagkatapos ako k. Kung saan c tinanggal mula sa string.
• Bawasan( A → u), pagkatapos ay ang lahat ng terminal at non-terminal na simbolo na bumubuo sa chain ay iki-clear mula sa tuktok ng stack u, pagkatapos ay tumingin ang estado ako m natitira sa tuktok. Ayon sa transition table sa intersection ako m at A hanapin ang susunod na estado ako s. Pagkatapos ay itinulak ang A sa stack, at pagkatapos ako s. Ang linya ay nananatiling hindi nagbabago.
• Tanggapin, pagkatapos ay kumpleto na ang pag-parse
• ang kawalan ng laman ay isang pagkakamali

Halimbawa

Buuin natin ang pag-parse ng string aaaccdcc:

salansan	Linya	Aksyon
ako 0	a aaccdcc$	Bawasan(A → ε), pumunta sa I 2
ako 0 A ako 2	a aaccdcc$	Shift(I 6)
I 0 A I 2 a ako 6	a accdcc$	Bawasan(A → Aa), pumunta sa I 2
ako 0 A ako 2	a accdcc$	Shift(I 6)
I 0 A I 2 a ako 6	a ccdcc$	Bawasan(A → Aa), pumunta sa I 2
ako 0 A ako 2	a ccdcc$	Shift(I 6)
I 0 A I 2 a ako 6	c cdcc$	Bawasan(A → Aa), pumunta sa I 2
ako 0 A ako 2	c cdcc$	Shift(I 4)
I 0 A I 2 s ako 4	c dcc$	Shift(I 8)
I 0 A I 2 c I 4 c ako 8	d cc$	Shift(I 9)
I 0 A I 2 c I 4 c I 8 d ako 9	c c$	Bawasan(B → d), pumunta sa I 11
I 0 A I 2 c I 4 c I 8 B ako 11	c c$	Shift(I 12)
I 0 A I 2 c I 4 c I 8 B I 11 c ako 12	c$	Bawasan(B → cBc), pumunta sa I 7
I 0 A I 2 c I 4 B ako 7	c$	Shift(I 10)
I 0 A I 2 c I 4 B I 7 c ako 10	$	Bawasan(B → cBc), pumunta sa I 3
I 0 A I 2 B ako 3	$	Bawasan(A → ε), pumunta sa I 13
I 0 A I 2 B I 3 A ako 13	$	Bawasan(S → ABA), pumunta sa I 1
ako 0 S ako 1	$	Tanggapin

Pagsasalin ng mga arithmetic expression (Seti-Ullman algorithm)

Tandaan. Ang code ay nabuo ng doggy style na mala- Motorola, i.e.

Op Arg1, Arg2

ibig sabihin

Arg2 = Arg1 Op Arg2

Paggawa ng puno

Ang puno ay itinayo gaya ng dati para sa isang aritmetika na expression: Sa ugat, ang operasyon na may pinakamababang priyoridad, na sinusundan ng mga pagpapatakbo na may bahagyang mas mataas na priyoridad, at iba pa. Ang mga panaklong ay may pinakamataas na precedence. Kung mayroong ilang mga operasyon na may parehong priyoridad - a op b op c, pagkatapos ay ang puno ay binuo bilang para sa expression (a op b) op c.

Halimbawa

Bumuo ng isang puno para sa expression na a + b / (d + a − b × c / d − e) + c × d

Desisyon: Sinusulat namin ang expression sa form

((a) + ((b) / ((((d) + (a)) − ((b) × (c)) / (d)) − (e)))) + ((c) × ( d))

Pagkatapos sa ugat ng bawat subtree ay magkakaroon ng operasyon, at ang mga expression sa mga bracket sa kaliwa at kanan nito ay ang mga subtree nito. Halimbawa, para sa subexpression ((b) × (c)) / (d), ang ugat ng kaukulang subtree ay ang operasyong "/", at ang mga subtree nito ay ang mga subexpression ((b) × (c)) at (d).

Layout ng puno (pagkalkula ng bilang ng mga rehistro)

• Kung ang vertex ay ang kaliwang dahon (iyon ay, isang variable), pagkatapos ay markahan namin ito ng zero.
• Kung ang tuktok ay ang tamang dahon, pagkatapos ay markahan namin ito ng isa
• Kung markahan namin ang parehong mga subtree nito para sa ilang vertex, markahan namin ito bilang mga sumusunod:
  • Kung ang kaliwa at kanang subtree ay may label na magkakaibang numero, piliin ang pinakamalaki sa kanila
  • Kung ang kaliwa at kanang mga subtree ay may label na may parehong mga numero, ang subtree na ito ay bibigyan ng isang numero na mas malaki kaysa sa isa na may label sa mga subtree.

mga marka ng dahon	Layout ng puno na may magkaparehong mga subtree	Ang kaliwang subtree ay may label na may malaking numero	Ang kanang subtree ay may label na may malaking numero

tama - pareho parang ninuno.

Kung ang label umalis inapo higit pa mga label tama, pagkatapos tama bata ay itinalagang rehistro isa pa kaysa sa ninuno, at umalis - pareho parang ninuno.

Ang code ay nabuo sa pamamagitan ng pagtawid sa puno mula sa ibaba hanggang sa itaas tulad ng sumusunod:

1. Walang nabuong code para sa vertex na may label na 0

2. Kung ang itaas ay sheet X na may label na 1 at irehistro ang R i, pagkatapos ay ang code

MOVE X, Ri

3. Kung ang tuktok ay panloob na may register R i at ang kaliwang anak nito ay sheet X na may label na 0, pagkatapos ay tumutugma ito sa code

<Код правого поддерева>OpX, Ri

4. Kung ang mga subtrees ng isang vertex na may register R i- hindi dahon at ang label ng kanang vertex ay mas malaki kaysa o katumbas ng label ng kaliwa (na may rehistrong Rj, j = i + 1), pagkatapos ay tumutugma ang code sa vertex

<Код tama subtree><Код umalis mga subtree > Op Rj, Ri

5. Kung ang mga subtrees ng vertex na may register R i- hindi mga dahon at ang label ng kanang vertex (kung saan ang rehistro ng Rj, j = i + 1) ay mas mababa sa label ng kaliwa, pagkatapos ay tumutugma ang code sa vertex

Ang pamamahagi ng rehistro ay ipinapakita sa graph sa kanan. Binuo na code:

ILIPAT ang d, R0 ;R0 = d ILIPAT c, R1 ;R1 = c MUL b, R1 ;R1 = (b × c) DIV R1, R0 ;R0 = (b × c) / d IGALAW a, R1 ;R1 = a ADD d, R1 ;R1 = a + d SUB R1, R0 ;R0 = (a + d) − ((b × c) / d) MOVE e, R1 ;R1 = e SUB R0, R1 ;R1 = ((a + d) − ((b × c) / d)) − e MOVE R1, R0;R0 = ((a + d) − ((b × c) / d)) − e DIV b, R0 ;R0 = b / (((a + d) − ((b × c) / d)) − e) ADD a, R0 ;R0 = a + (b / (((a + d) − ((b × c) / d )) − e)) MOVE d, R1 ;R1 = d MUL c, R1 ;R1 = c × d ADD R0, R1 ;R1 = (a + (b / (((a + d)) − ((b × c) ) / d)) − e))) + (c × d) MOVE R1, R0;R0 = (a + (b / (((a + d)) − ((b × c) / d)) − e) )) + (c × d)

Pagsasalin ng mga lohikal na expression

Ipinapakita ng seksyong ito kung paano bumuo ng code para sa tamad na pagsusuri ng mga boolean na expression. Bilang resulta ng algorithm, ang isang piraso ng code ay nakuha, na, gamit ang TST, BNE, BEQ operations, kinakalkula ang isang lohikal na expression sa pamamagitan ng paglipat sa isa sa mga label: TRUELAB o FALSELAB.

Paggawa ng puno

Ang puno ng isang lohikal na expression ay sumasalamin sa pagkakasunud-sunod kung saan ito sinusuri ayon sa nangunguna sa mga operasyon, iyon ay, upang suriin ang halaga ng isang tree node (na kung saan ay ang pagpapatakbo ng dalawang operand na mga subtree ng node), kailangan nating unang kalkulahin ang mga halaga ng mga subtree nito.

Priyoridad ng Operasyon: Ang NOT operator ang may pinakamataas na precedence, na sinusundan ng AND at pagkatapos ay OR. Kung ang iba pang mga lohikal na operasyon ay ginagamit sa expression, kung gayon ang mga ito ay dapat na ipahayag sa pamamagitan ng tatlong ito sa isang tiyak na paraan (kadalasan, walang iba pang mga operasyon at expression ng conversion ay hindi kinakailangan). Ang pagkakaugnay para sa mga operasyon ng parehong priyoridad ay mula kaliwa hanggang kanan, ibig sabihin, ang A at B at C ay itinuturing bilang (A at B) at C

Halimbawa

Bumuo ng isang puno para sa lohikal na expression na hindi A o B at C at (B o hindi C).

Desisyon: tingnan ang diagram sa kanan.

Para sa bawat tuktok ng puno, 4 na katangian ang kinakalkula:

• Numero ng node
• Ang label na dadaanan kung mali ang expression sa node (false label, fl)
• Ang label na tatahakin kung totoo ang expression sa node (true label, tl)
• Label-sign (sign) (para sa higit pang mga detalye, tingnan sa ibaba)

Ang mga vertice ay binibilang sa random na pagkakasunud-sunod, ang tanging kundisyon ay ang pagiging natatangi ng mga numero ng node.

Ang layout ng puno ay ginagawa tulad ng sumusunod:

• Tinutukoy ng fl ang bilang ng vertex kung saan ginawa ang transition o falselab kung false ang vertex na ito
• Ipinapahiwatig ng tl ang bilang ng vertex kung saan ginawa ang transition o truelab kung totoo ang vertex na ito

Tinutukoy ng sign kung saan maaaring wakasan ang pagsusuri ng kasalukuyang subtree.

Para sa ugat ng puno, fl=falselab, tl=truelab, sign=false.

kaya:

Halimbawa

Markahan ang puno na binuo para sa lohikal na expression na hindi A o B at C at (B o hindi C).

Pagbuo ng code

Mga utos ng makina na ginamit sa nabuong code:

• TST - pagsuri sa argumento para sa katotohanan at pagtatakda ng bandila kung mali ang argumento
• BNE - tumalon sa label kung ang bandila ay hindi nakatakda, ibig sabihin, ang kundisyon ay nasuri sa TST totoo
• BEQ - tumalon sa label kung ang bandila ay nakatakda, ibig sabihin, ang kundisyon ay nasuri sa TST mali

Ang code ay binuo tulad ng sumusunod:

• ang puno ay tinatahak mula sa ugat, para sa AT at O, ang kaliwang subtree ay unang tinatahak, pagkatapos ay ang kanan
• para sa bawat vertex na dumaan, ang numero nito (label) ay naka-print
• para sa sheet A(number, tl, fl, sign) TST A ay naka-print
  • kung sign == true, naka-print ang BNE tl
  • kung sign == false, ang BEQ fl ay naka-print

Halimbawa

Para sa expression sa itaas, ang sumusunod na code ay bubuo:

1:2:4: TST A BEQ TRUELAB 3:5:7: TST B BEQ FALSELAB 8: TST C BEQ FALSELAB 6:9: TST B BNE TRUELAB 10:11: TST C BNE FALSELAB TRUELAB: FALSELAB:

Sample na paraan ng pagtutugma

Ang ideya ng pamamaraan ay para sa parehong seksyon ng programa, ang code ay maaaring mabuo sa iba't ibang paraan, at, bilang isang resulta, ang pag-optimize ay maaaring makamit para sa isa o ibang parameter.

Pagbubuo ng problema

Mayroong maraming mga sample, ang bawat isa ay tinukoy ng isang piraso ng intermediate na representasyon kung saan ito naaangkop, ang timbang at ang nabuong code. Mayroong isang intermediate representation tree, na isang fragment ng programa kung saan kinakailangan upang makabuo ng code. Ang layunin ay bumuo ng gayong takip ng intermediate representation tree na may mga sample upang ang kabuuang bigat ng mga sample ay minimal.

Ang mga pattern ay mga tagubilin sa pagpupulong at ang mga puno ng parse na tumutugma sa kanila. Para sa bawat sample, ang oras ng pagpapatupad nito (sa mga cycle) ay kilala. Sa kanilang tulong, bubuo kami ng pinakamainam (sa mga tuntunin ng oras ng pagpapatupad) na code.

Mga halimbawang halimbawa

Pagbuo ng isang intermediate na representasyon

Una, bumuo kami ng parse tree para sa buong expression.

Pagbuo ng coverage

Ngayon para sa bawat vertex (dumaan namin ang mga ito sa pagkakasunud-sunod mula sa mga dahon hanggang sa ugat), bubuo kami ng pinakamainam na code para sa subtree nito. Upang gawin ito, dumaan lang kami sa lahat ng mga sample na naaangkop sa isang naibigay na vertex. Ang oras ng pagpapatupad kapag gumagamit ng isang partikular na pattern ay ang kabuuan ng oras na kinakailangan upang suriin ang mga argumento nito (at alam na natin ang pinakamainam na code para sa pag-compute ng mga ito salamat sa tree traversal order) at ang oras ng pagpapatupad ng pattern mismo. Sa lahat ng mga opsyon na nakuha, pipiliin namin ang pinakamahusay - ito ang magiging pinakamainam na code para sa subtree ng vertex na ito. Sa ugat ng puno, nakukuha namin ang pinakamainam na code para sa buong expression.

Pagbuo ng code

Hindi kinakailangang isulat ang code para sa lahat ng vertices - sapat na upang isulat ang minimum na kinakailangang oras at ang sample na kailangan mong gamitin. Ang lahat ng iba pa mula dito ay madaling naibalik.

Mayroon kaming walang katapusang bilang ng mga rehistro sa mga problemang ito, kaya sa bawat oras na maaari kang gumamit ng bago.

Konstruksyon ng RV ayon sa DKA

Konstruksyon ng NFA ayon sa right-linear grammar

Grammar Casting

Upang ma-convert ang isang arbitrary na COP-grammar sa pinababang anyo, dapat mong gawin ang mga sumusunod na hakbang:

• alisin ang lahat ng baog na mga character;
• alisin ang lahat ng hindi maabot na mga character;

Pag-alis ng mga walang kwentang character

pasukan: COP-grammar G = (T, N, P, S).

Output: Isang COP-grammar G' = (T, N', P', S) na walang mga baog na simbolo, kung saan L(G) = L(G').

Paraan:

Recursively build sets N 0 , N 1 , ...

1. N 0 = ∅, i = 1.
2. N i = (A | (A → α) ∈ P at α ∈ (N i - 1 ∪ T)*) ∪ N i-1 .
3. Kung N i ≠ N i - 1, pagkatapos ay i = i + 1 at pumunta sa hakbang 2, kung hindi N’ = N i ; Ang P' ay binubuo ng mga panuntunan ng set P na naglalaman lamang ng mga simbolo mula sa N' ∪ T; G' = (T, N', P', S).

Kahulugan: ang isang simbolong x ∈ (T ∪ N) ay sinasabing hindi maabot sa isang gramatika G = (T, N, P, S) kung ito ay hindi lilitaw sa anumang pangungusap na anyo ng gramatika na ito.

Halimbawa

Alisin ang mga walang kwentang character mula sa grammar G((A, B, C, D, E, F, S), (a, b, c, d, e, f, g), P, S)

• S → AcDe | CaDbCe | Saca | aCb | dFg
• A → SeAd | cSA
• B → CaBd | aDBc | BSC | bfg
• C→Ebd | Seb | aAc | cfF
• D→fCE | ac | dEdAS | ε
• E→ESacD | aec | eFF

Desisyon

• N 0 = ∅
• N 1 = (B (B → bfg) , D (D → ac) , E (E → aec) )
• N 2 = (B, D, E, C (C → Ebd) )
• N 3 = (B, D, E, C, S (S → aCb) )
• N 4 \u003d (B, D, E, C, S) \u003d N 3

G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | Saca | aCb
• B → CaBd | aDBc | BSC | bfg
• C→Ebd | Si Seb
• D→fCE | ac | ε
• E→ESacD | aec

Pag-alis ng mga hindi maabot na character

pasukan: COP grammar G = (T, N, P, S)

Output: Isang COP-grammar G' = (T', N', P', S) na naglalaman ng walang hindi maabot na mga simbolo, kung saan L(G) = L(G').

Paraan:

1. V 0 = (S); ako = 1.
2. V i = (x | x ∈ (T ∪ N), (A → αxβ) ∈ P at A ∈ V i - 1 ) ∪ V i-1 .
3. Kung V i ≠ V i - 1 , pagkatapos ay i = i + 1 at pumunta sa hakbang 2, kung hindi N’ = V i ∩ N; T' = V i ∩ T; Ang P' ay binubuo ng mga tuntunin ng set P na naglalaman lamang ng mga simbolo mula sa V i ; G' = (T', N', P', S).

Kahulugan: Ang isang COP-grammar G ay sinasabing mababawasan kung hindi ito naglalaman ng mga hindi matamo at sterile na mga simbolo.

Halimbawa

Alisin ang mga hindi maabot na character mula sa grammar G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | Saca | aCb
• B → CaBd | aDBc | BSC | bfg
• C→Ebd | Si Seb
• D→fCE | ac | ε
• E→ESacD | aec

Desisyon

• V 0 = (S)
• V 1 = (S, C (S → CaDbCe) , D (S → CaDbCe) , a (S → CaDbCe) , b (S → CaDbCe) , e (S → CaDbCe) )
• V 2 = (S, C, D, a, b, e, E (C → Ebd) , d (C → Ebd) , f (D → fCE) )
• V 3 = (S, C, D, E, a, b, d, e, f, c (E → ESacD) )
• V 4 \u003d (S, C, D, E, a, b, d, e, f, c) \u003d V 3

G""((C, D, E, S), (a, b, c, d, e, f), P"", S)

• S → CaDbCe | Saca | aCb
• C→Ebd | Si Seb
• D→fCE | ac | ε
• E→ESacD | aec

Mas madaling ilarawan ang bokabularyo ng isang wika sa anyo ng mga regular na expression, at kilalanin ang isang wika sa tulong ng KA. Samakatuwid, mahalagang ma-convert ang mga kahulugan ng wika sa anyo ng mga regular na expression sa isang kahulugan sa anyo ng isang FA. Ang ganitong pagbabago ay iminungkahi ni Kennet Thompson.

Ang makina ng estado ay isang limang (S, S, d, S 0 , F)

Ang S ay isang may hangganan na hanay ng mga estado.

Ang S ay isang may hangganan na hanay ng mga wastong input signal.

d - function ng paglipat. Sinasalamin nito ang set na Sx(SÈ(e)) sa hanay ng mga estado ng isang non-deterministic finite automaton. Para sa isang deterministikong automat, ang transition function ay sumasalamin sa set SxS sa hanay ng mga estado ng automat. Sa madaling salita, depende sa estado at sa simbolo ng input, d tinutukoy ang bagong estado ng automat.

S 0 - paunang estado ng finite automat, S 0 О S.

Ang F ay ang hanay ng mga huling estado ng automat, F О S.

Ang pagpapatakbo ng isang makina ng estado ay isang pagkakasunud-sunod ng mga hakbang. Ang hakbang ay tinutukoy ng estado ng automat at ang input na simbolo. Ang hakbang mismo ay binubuo sa pagbabago ng estado ng automat at pagbabasa ng susunod na simbolo ng pagkakasunud-sunod ng pag-input.

Mayroong mga sumusunod na panuntunan para sa pag-convert ng mga regular na expression sa isang state machine.

1 Ang regular na expression na "e" ay binago sa isang automat ng dalawang estado at isang e-transition sa pagitan ng mga ito (Larawan 1).

Figure 1. - Automaton para sa e-transition

2 Ang isang regular na expression mula sa isang character na "a" ay na-convert sa isang may hangganan na makina ng estado mula sa dalawang estado at isang paglipat sa pagitan ng mga ito ayon sa input signal a (Figure 2).

Figure 2. - Automaton para sa paglukso sa pamamagitan ng simbolo a

3 Hayaang magkaroon ng regular na expression na rs at finite automata para sa expression na r at ang expression na s ay naitayo na. Pagkatapos ang dalawang automata ay konektado sa serye. Ipinapakita ng Figure 3 ang paunang automata para sa mga wika r at s. Ang figure ay nagpapakita ng isang automat para sa pagkilala sa pagsasama-sama ng mga wikang ito.

Awtomatiko para sa r Awtomatiko para sa s

Figure 3. - Paunang automata

Figure 4. - Machine para sa concatenating mga wika

4 Hayaang magkaroon ng isang regular na expression r | s at finite automata ay naitayo na para sa expression na r at sa expression na s (Larawan 3). Pagkatapos ay sa resultang automat ay dapat mayroong isang alternatibo ng pagpapatupad ng isa sa dalawang automata. Iyon ay, ang automat para sa expression na r | s para sa automata para sa r at s mula sa Figure 3 ay may form na ipinapakita sa Figure 5.

Figure 5. - Machine para sa pagsasama-sama ng mga wika

5 Hayaang magkaroon ng regular na expression na r* na may nabuong finite automaton r. Sa kasong ito, dalawang bagong estado ang ipinakilala para sa posibilidad ng pag-bypass sa automat ng expression na r, at isang e-transition sa pagitan ng pangwakas at paunang estado ay ipinakilala din para sa posibilidad ng paulit-ulit na pag-uulit ng automaton r. Kung ang isang automat na katulad ng Figure 3 ay binuo para sa regular na expression na r, kung gayon ang finite automaton na ipinapakita sa Figure 6 ay tumutugma sa regular na expression r*.

Mga setting

Ayon sa theorem ni Kleene, ang anumang regular na expression ay maaaring iugnay sa isang finite automat, na isang pormal na modelo ng algorithm para sa pagkilala sa mga lexeme na tinutukoy ng regular na expression na ito. Sa pinaka-pangkalahatang termino, ang isang finite automaton-recognizer ay tinukoy ng isang finite set ng input stream na nagsasaad ng katangian nito at mga transition sa pagitan nila. Ang pagbabago ng estado ay nangyayari kapag ang mga character ng input stream ay natanggap mula sa ibinigay na alpabeto alinsunod sa transition function , na tumutukoy sa mga posibleng kasunod na estado mula sa input na character at ang kasalukuyang estado. Kabilang sa mga posibleng estado, ang mga paunang (inisyal) at panghuling (pinahihintulutan) na mga estado ay nakikilala, kung saan ang finite automaton-recognizer ay matatagpuan, ayon sa pagkakabanggit, sa simula at pagkumpleto ng pagproseso ng mga token ng input stream. Kung ang input sequence ng mga character ay maaaring makabuo ng isang sequence ng mga transition na maaaring maglipat ng finite automat mula sa paunang estado patungo sa isa sa mga huling, ito ay itinuturing na tumatanggap at kabilang sa regular na set na kinikilala nito.

(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

Talahanayan 1

	0	1
Q1	Q4	Q2
Q2	Q3	Q1
Q3	Q2	Q4
Q4	Q1	Q3

Ang mga column ng transition table ay kumakatawan sa mga character ng input alphabet, at ang mga row ay tumutugma sa kasalukuyang estado ng DFA. Ang mga elemento ng bawat linya ay nagpapahiwatig ng mga estado ng DFA kung saan dapat itong lumipat mula sa kasalukuyang estado kapag natatanggap ang mga kaukulang character ng input alphabet. Sa partikular, sumusunod ito mula sa unang linya ng talahanayan ng paglipat na ang pagtanggap ng mga simbolo 0 at 1 sa paunang estado na Q1 ay naglilipat ng DFA sa mga estadong Q4 at Q2, ayon sa pagkakabanggit.

Kapag kinikilala ang pagkakasunud-sunod ng input mula sa talahanayan ng paglipat, madaling masubaybayan ang mga pagbabago sa estado ng DFA upang matukoy kung ang isa sa mga estado ng pagtanggap ay naabot o hindi. Sa partikular, para sa isang binary vector 01001000 na may pare-parehong bilang ng mga zero at isa, ang itinuturing na DFA ay bumubuo ng sumusunod na pagkakasunud-sunod ng mga transition, kung saan ang bawat transition ay may label na may karakter ng input alphabet na tumatawag dito:

Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1

Ang pagkakasunud-sunod ng mga transition na ito ay nagtatapos sa pagtanggap ng estado na Q1, samakatuwid, ang binary vector 01001000 ay kabilang sa regular na hanay na kinikilala ng itinuturing na DFA at natutugunan ang regular na expression sa itaas.

Sa konklusyon, dapat tandaan na ang itinuturing na impormal na paraan ng pagtatayo

Ang mga regular na expression (REs) ay isang napaka-maginhawang paraan ng pagsulat ng tinatawag na regular o awtomatikong mga wika. Samakatuwid, ginagamit ang RT bilang input language sa maraming system na nagpoproseso ng mga chain. Isaalang-alang ang mga halimbawa ng naturang mga sistema:

• Ang utos ng Unix grep, o mga katulad na utos para sa paghahanap ng mga string, na makikita sa mga Web browser o mga sistema ng pag-format ng teksto. Sa ganitong mga sistema, ang mga RE ay ginagamit upang ilarawan ang mga pattern na hinahanap ng user sa isang file. Kino-convert ng iba't ibang search engine ang RT sa alinman sa isang deterministic finite state machine (DFA) o isang non-deterministic finite state machine (NFA) at ilapat ang state machine na ito sa file na hinahanap.
• Mga generator ng lexical analyzer. Ang mga lexical analyzer ay isang bahagi ng compiler, sinisira nila ang source program sa mga lohikal na yunit (token), na maaaring binubuo ng isa o higit pang mga character at may isang tiyak na kahulugan. Kinukuha ng lexical analyzer generator ang mga pormal na paglalarawan ng mga token, na mahalagang RE, at gumagawa ng DFA na kumikilala kung aling token ang lalabas sa input nito.
• RT sa mga programming language.

Sa artikulong ito, kikilalanin muna natin ang may hangganang automata at ang mga uri nito (DFA at NFA), at pagkatapos ay isasaalang-alang natin ang isang halimbawa ng pagbuo ng minimal na DFA gamit ang isang regular na expression.

Mga Makina ng Estado

Ang finite automaton (FA) ay isang converter na nagbibigay-daan sa iyong iugnay ang isang input sa isang katumbas na output, at ang output na ito ay maaaring nakadepende hindi lamang sa kasalukuyang input, kundi pati na rin sa kung ano ang nangyari dati, sa prehistory ng finite automaton. Kahit na ang pag-uugali ng tao, at hindi lamang mga artipisyal na sistema, ay maaaring ilarawan gamit ang CA. Gamit ang KA, maaaring ilarawan ng isa hindi lamang ang pag-uugali ng mga artipisyal na sistema, kundi maging ang pag-uugali ng tao. Halimbawa, ang iyong reaksyon sa katotohanan na ang iyong kapitbahay ay nakikinig ng malakas na musika sa gabi ay magiging isa pagkatapos ng unang pangyayari at ganap na naiiba pagkatapos ng ilang mga ganoong pangyayari. Maaaring mayroong isang walang katapusang bilang ng mga naturang backstories, ang tanong ay lumitaw; Anong uri ng memorya ang dapat mayroon ang isang spacecraft upang kumilos nang iba para sa bawat prearrangement? Malinaw na hindi posibleng mag-imbak ng walang katapusang bilang ng prehistory. Samakatuwid, ang automat, tulad nito, ay naghahati sa lahat ng posibleng prehistory sa mga equivalence classes. Ang dalawang kasaysayan ay katumbas kung pareho silang makakaapekto sa pag-uugali ng automat sa hinaharap. Ang equivalence class kung saan iniuugnay ng automat ang kasalukuyang kasaysayan nito ay tinatawag ding internal state ng automat.

Ngayon tingnan natin ang mga paraan kung saan maaaring tukuyin ang CA. Maaari silang tukuyin sa anyo ng mga graph o sa anyo ng mga control table. Sa anyo ng isang graph, ang KA ay tinukoy sa sumusunod na paraan:

• ang mga vertex ng graph ay tumutugma sa mga estado ng CA.
• ang mga nakadirekta na gilid ay tumutugma sa mga function ng paglipat (malapit sa bawat naturang gilid, ang simbolo kung saan isinasagawa ang paglipat ay ipinahiwatig).
• isang vertex na may gilid na pumapasok dito na hindi nag-iiwan ng higit sa isang estado ay tumutugma sa paunang estado.
• ang mga huling estado ng CA ay minarkahan ng isang naka-bold na balangkas.

Sa anyo ng isang control table, tulad nito:

• Ang mga estado ng KA ay matatagpuan sa mga hilera ng talahanayan.
• mga character ng kinikilalang wika - sa mga hanay.
• sa intersection, ang estado ay ipinahiwatig, na maaaring maabot mula sa ibinigay na estado sa pamamagitan ng ibinigay na simbolo.

Ang isang halimbawa ng KA sa anyo ng isang graph at sa anyo ng isang control table ay ipapakita sa ibaba.

DKA at NKA

Ang pangunahing pagkakaiba sa pagitan ng isang DFA at isang NFA ay ang DFA ay maaari lamang nasa isang estado sa panahon ng operasyon, habang ang NFA ay maaaring nasa ilang mga estado sa parehong oras. Bilang isang halimbawa ng gawain ng NCA, maaari mong banggitin ang ideya ng American physicist na si Hugh Everett na ang anumang kaganapan ay naghahati sa mundo sa maraming mga mundo, kung saan ang bawat isa ay natapos ang kaganapang ito sa sarili nitong paraan. Halimbawa, sa isang mundo, nanalo si Hitler sa 2nd World. digmaan, sa isa pa - pumasok si Newton sa negosyo sa halip na pisika at ang pagtuklas ng mga batas ng klasikal na mekanika ay kailangang ipagpaliban ng 50 taon. Upang makagawa ng anumang konklusyon mula sa pagpapatakbo ng makina, dapat pag-aralan ng isa ang lahat ng "mundo". Matapos basahin ang buong input chain, ipinapalagay namin na tinatanggap ng NFA ang chain na ito kung natapos na nito ang trabaho sa isang estado ng pagtanggap sa hindi bababa sa isa sa maraming "mundo". Alinsunod dito, tinatanggihan ng automat ang rung kung ito ay natapos sa isang hindi katanggap-tanggap na estado sa bawat "mundo". Ang DFA, sa kabilang banda, ay tumatanggap ng isang string, ito ay kitang-kita kung, pagkatapos basahin ang buong input string, nahanap nito ang sarili sa isang estado ng pagtanggap.

Sa karamihan ng mga kaso, ang pagbuo ng isang NFA ay mas madali kaysa sa pagbuo ng isang DFA. Ngunit, sa kabila nito, ang paggamit ng NFA para sa pagmomodelo ay hindi magandang ideya. Sa kabutihang palad, para sa bawat NFA ay posibleng bumuo ng isang DFA na tumatanggap ng parehong input language. Sa artikulong ito, hindi kami magpapakita ng algorithm para sa pagbuo ng isang DFA mula sa isang NFA, ngunit isaalang-alang ang algorithm na ito batay sa isang visual na halimbawa sa ibaba.

Pagbuo ng Minimal DFA mula sa Regular Expression

Upang magsimula, narito ang RW syntax na ginamit sa artikulong ito:

• ang concatenation ay tinukoy na may puwang o walang laman na string (halimbawa: ab)
• unyon, gamit ang simbolo na "|"
• iteration(Kleene closure), na may simbolo na "*".

Isaalang-alang ang isang halimbawa na ibinigay ng isang regular na expression:

xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)

Kinakailangang bumuo ng kaunting DFA mula sa isang regular na expression at ipakita ang pagkilala sa isang tama at maling string.

Upang magsimula, pinapasimple namin ang RT na ito, gamit ang right-hand distributive law of concatenation na may kinalaman sa unyon, nakuha namin ang sumusunod na RT:

(xy* | ab | (x | a*)) (x | y*)

Ngayon ay bumuo kami ng isang automat para sa RV na ito:

Ayon sa panuntunan ng concatenation transformation (hindi namin ibibigay ang mga patakaran para sa pagbabago ng RV sa KA, dahil medyo halata ang mga ito), nakukuha namin ang sumusunod na automat:

Sa pamamagitan ng panuntunan sa pagbabago ng unyon:

Ayon sa panuntunan ng pagbabagong-anyo ng concatenation:

At sa dulo inilalapat namin ang panuntunan sa pagbabago ng pagsasara at makuha ang εNCA:

Inaalis namin ang mga ε-transition ("asterisk" ay nagsasaad ng mga huling estado):

Sa NFA na ito, ang mga estado na s3 at s5 ay katumbas, dahil δ(s3, x) = δ(s5, x) = s1 at δ(s3, y) = δ(s5, y) = s5, s7. Palitan ang pangalan ng mga estado s6 -> s5 at s7 -> s6:

Bumubuo kami ng DFA ayon sa NFA:

Sa DFA na ito, ang mga estado na p1 at p5 ay katumbas, dahil
δ(p1, x) = δ(p5, x) = p4 at δ(p1, y) = δ(p5, y) = p5. Palitan ang pangalan ng mga estado p6 -> p5 at p7 -> p6:

Ang automat na ito ay ang pinakamababang DFA.

Hayaang δ ang transition function, pagkatapos ang extended transition function na binuo mula sa δ ay ilalarawan ng δ', at ω ang input string.

Hayaang maging input ang chain ω = aaax, inaasahan namin na ang automat ay nasa isa sa mga estado ng pagtanggap.

δ'(p0, ε) = p0
δ'(p0, a) = δ(δ'(p0, ε), a) = δ(p0, a) = p3
δ'(p0, aa) = δ(δ'(p0, a), a) = δ(p3, a) = p5
δ'(p0, aaa) = δ(δ'(p0, aa), a) = δ(p5, a) = p5
δ'(p0, aaax) = δ(δ'(p0, aaa), a) = δ(p5, a) = p4

Ang p4 ay isang wastong end state, kaya ang string aaax ay wasto para sa automat na ito.

Ngayon ipagpalagay na ω = xyyb:

δ'(p0, ε) = p0
δ'(p0, x) = δ(δ'(p0, ε), x) = δ(p0, x) = p1
δ'(p0, xy) = δ(δ'(p0, x), y) = δ(p1, y) = p1
δ'(p0, xyy) = δ(δ'(p0, xy), y) = δ(p1, y) = p1
δ'(p0, xyyb) = δ(δ'(p0, xyy), b) = δ(p1, b) = ∅

Dito makikita natin na kung ang simbolo b ay input sa automat kapag ito ay nasa estado p1, kung gayon ang automaton na ito ay mamamatay, samakatuwid ang chain xyyb ay hindi tama.

P. S. Sa artikulong ito, ang algorithm para sa pagbuo ng isang DFA sa pamamagitan ng RT ay isinasaalang-alang, ngunit mayroong mas maginhawang mga algorithm, lalo na para sa programming, ngunit ito ay isang paksa para sa isa pang artikulo ...

Para sa karagdagang pag-aaral ng mga katangian ng finite automata at, sa partikular, para sa paglutas ng problema sa synthesis, ang sumusunod na theorem ay mahalaga.

Theorem 7.7 (determinization theorem). Para sa anumang finite automat, isang katumbas na deterministic finite automat ay maaaring itayo.

Upang patunayan ang teorama, kinakailangan, una, upang ilarawan ang algorithm para sa pagbuo ng isang deterministikong finite automat mula sa orihinal; pangalawa, bigyang-katwiran ang algorithm na ito sa pamamagitan ng mahigpit na pagpapatunay na talagang nagbibigay ito ng isang may hangganang automat na deterministiko at katumbas ng orihinal. Dito ipinapakita lamang namin ang algorithm para sa pagbuo ng isang deterministikong automat.

Ang pagbabagong-anyo ng isang di-makatwirang finite automat sa isang katumbas na deterministikong isa ay isinasagawa sa dalawang yugto: una, ang mga arko na may label na \lambda ay tinanggal, pagkatapos ay isinasagawa ang aktwal na pagpapasiya.

1. Pag-alis ng mga λ-transition (mga arc na may label na \lambda ).

Upang lumipat mula sa orihinal na makina ng estado M=(V,Q,q_0,F,\delta) sa katumbas na finite automat M"=(V,Q",q_0,F",\delta") nang walang λ-transition, sapat na upang maisagawa ang mga sumusunod na pagbabago sa orihinal na graph na M.

a. Ang lahat ng mga estado, maliban sa paunang estado, na ipinasok lamang ng mga arko na may label na \lambda , ay aalisin; ito ay tumutukoy sa set Q" ng finite automat M" . Malinaw na Q"\subseteq Q . Sa kasong ito, ipinapalagay namin na ang paunang estado ay nananatiling pareho.

b. Ang hanay ng mga arko ng finite automat M" at ang kanilang mga label (kaya ang transition function M") ay tinukoy bilang mga sumusunod: para sa alinmang dalawang estado p,r\in Q",~ p\to_(a)r humahawak kung at kung a\sa V , at isa sa mga sumusunod ay nasa graph na M: maaaring mayroong isang arko mula p hanggang r na ang label ay naglalaman ng simbolo na a , o mayroong isang estado na q na p\Rightarrow_(\lambda)^(+)q at q\to_(a)r . Sa kasong ito, ang vertex q, sa pangkalahatan, ay maaaring hindi kabilang sa set Q ", ibig sabihin, maaari itong mawala kapag dumadaan sa automat M" (Larawan 7.11). Ngunit kung q\in Q" , kung gayon, natural, ang arko (q,r) ay mapapanatili sa M" at ang simbolo a ay isa sa mga simbolo na kabilang sa label ng arko na ito (Larawan 7.12).

Kaya, sa M" lahat ng arcs M ay nakaimbak na ang mga label ay naiiba sa \lambda at kung saan nagkokonekta ng isang pares (vertices) ng mga estado mula sa set Q" (hindi inalis ayon sa item a). Bilang karagdagan, para sa anumang triple ng mga estado na p,q,r (hindi kinakailangang naiiba!), na ang p,r\in Q" at mayroong isang landas na hindi zero ang haba mula p hanggang q na ang label ay katumbas ng \lambda (ibig sabihin, ang landas sa pamamagitan ng λ-transitions), at mula q hanggang r ay humahantong ang isang arko, ang label kung saan naglalaman ng simbolo a ng input na alpabeto, sa M" ang isang arko ay binuo mula p hanggang r, ang label na naglalaman ng ang simbolo a (tingnan ang Fig. 7.11).

sa. Ang hanay ng mga huling estado na F" ng may hangganan na automat M" ay naglalaman ng lahat ng mga estado q\in Q" , ibig sabihin, ang mga estado ng may hangganan na automat M na hindi tinanggal ayon sa item a, kung saan q\Rightarrow_(\lambda)^(\ast)q_f para sa ilang q_f\in F (iyon ay, alinman sa estado q mismo ay ang panghuling estado ng finite automat M , o mula dito isang landas na hindi zero ang haba kasama ang mga arc na may label na \lambda ay humahantong sa isa sa mga huling estado ng finite automaton M ) (Larawan 7.13).

2. Talagang determinasyon.

Hayaan M=(Q,V,q_0,F,\delta) ay isang may hangganang automat na walang λ-transition. Bumuo tayo ng katumbas na deterministic finite automat M_1 .

Ang finite automat na ito ay tinukoy sa paraang ang state set nito ay ang set ng lahat ng subset ng state set ng finite automat M . Nangangahulugan ito na ang bawat indibidwal na estado ng finite automat M_1 ay tinukoy bilang ilang subset ng set ng mga estado ng finite automat M . Sa kasong ito, ang paunang estado ng bagong finite automat (i.e. M_1 ) ay isang singleton subset na naglalaman ng inisyal na estado ng lumang finite automat (i.e. M ), at ang mga huling estado ng bagong finite automat ay lahat ng naturang subset na Q na naglalaman hindi bababa sa isang pangwakas na tuktok ng orihinal na may hangganan na automat M .

Mula ngayon, na nagpapahintulot sa ilang kalayaan sa pagsasalita, tatawagin natin kung minsan ang mga estado ng may hangganan na automaton na M_1 states-sets. Mahalaga, gayunpaman, na malinaw na maunawaan na ang bawat naturang set ng estado ay isang hiwalay na estado ng bagong finite automat, ngunit hindi isang set ng mga estado nito. Kasabay nito, para sa orihinal ("luma") na may hangganan na automat M, ito ang tiyak na hanay ng mga estado nito. Sa matalinghagang pagsasalita, ang bawat subset ng mga estado ng lumang finite automat ay "na-collapse" sa isang estado ng bagong finite automat*.

*Sa pormal na paraan, ang set Q_1 ay dapat tukuyin bilang isang set na nasa isang one-to-one na sulat sa set 2^Q , ngunit mas maginhawa pa rin para sa amin na isaalang-alang na ang Q_1 ay tumutugma sa 2^Q , dahil ang set ng mga estado ng isang finite automat ay maaaring maging anumang non-empty finite set.

Ang transition function ng bagong finite automat ay tinukoy upang mula sa state-set na S sa pamamagitan ng input na simbolo a ang finite automaton M_1 ay pumasa sa state-set, na kung saan ay ang unyon ng lahat ng set ng estado ng lumang finite automat, hanggang kung saan ang lumang may hangganang automat na ito ay ipinapasa ng simbolo a mula sa bawat estado ay nagtatakda ng S . Kaya, ang finite automat M_1 ay deterministic sa pamamagitan ng construction.

Ang pandiwang paglalarawan sa itaas ay maaaring isalin sa mga formula tulad ng sumusunod: binubuo namin ang makina ng estado M_1 nang sa gayon

M_1=(Q_1,V,\(q_0\),F_1,\delta_1), saan

\begin(cases)Q_1=2^Q,\quad F_1=\(T\colon\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\forall S\subseteq Q) (\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Bigr). \end(cases)

Bigyang-pansin natin ang katotohanan na sa mga estado ng bagong finite automat ay mayroong state \varnothing , at, ayon sa (7.8), \delta_1(\varnothing,a)=\varnothing para sa anumang input character a . Nangangahulugan ito na, kapag nasa ganoong estado, hindi ito iiwan ng state machine M_1. Sa pangkalahatan, ang anumang estado q ng isang finite automat na para sa anumang input na simbolo na mayroon tayo \delta(q,a)=q ay tinatawag na absorbing state ng finite automaton. Kaya, ang estado \varnothing ng deterministic state machine M_1 ay sumisipsip. Kapaki-pakinabang din na tandaan iyon \delta_1(S,a)=\varnothing kung at kung para lamang sa bawat q\in S (mga estado ng lumang finite automat mula sa hanay ng mga estado S ) \delta(q,a)=\varnothing, ibig sabihin. sa graph M, ang bawat naturang estado q ay hindi nag-iiwan ng anumang arko na may markang simbolo a .

Mapapatunayan na ang finite automat na nakuha ng naturang algorithm ay katumbas ng orihinal.

Halimbawa 7.9. Tinutukoy namin ang may hangganan na automat na ipinapakita sa Fig. 7.14.

Ang isang katumbas na finite automat na walang λ-transitions ay ipinapakita sa fig. 7.15. Tandaan na ang vertex q_2 ay nawawala, dahil ang "walang laman" na mga arko lamang ang pumapasok dito.

Upang matukoy ang nagreresultang automat, talagang hindi kinakailangang isulat ang lahat ng 2^3=8 na estado nito, na marami sa mga ito ay maaaring hindi maabot mula sa paunang estado \(q_0\) . Upang makakuha ng maaabot mula sa mga estado ng \(q_0\), at sa kanila lamang, ginagamit namin ang tinatawag na paraan ng paghila.

Ang pamamaraang ito ay maaaring inilarawan sa pangkalahatang kaso tulad ng sumusunod.

Sa orihinal na finite automat (walang walang laman na mga arko), tinutukoy namin ang lahat ng set ng mga estado na maaabot mula sa paunang isa, i.e. para sa bawat input na character a makikita natin ang set \delta(q_0,a) . Ang bawat naturang set sa bagong automat ay isang estado na direktang naa-access mula sa una.

Para sa bawat isa sa mga tinukoy na state-set na S at bawat input na simbolo a, makikita natin ang set \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom(A)^(.))). Ang lahat ng mga estado na nakuha sa hakbang na ito ay ang mga estado ng isang bagong (deterministic) na automat, na maabot mula sa paunang vertex kasama ang isang landas na may haba na 2. Inuulit namin ang inilarawang pamamaraan hanggang sa walang mga bagong state-set (kabilang ang walang laman) na lilitaw. Maipapakita na sa kasong ito ang lahat ng naturang estado ng may hangganan na automat M_1 ay nakuha na maaabot mula sa paunang estado \(q_0\) .

Para sa may hangganan na makina ng estado sa Fig. 7.15 mayroon kaming:

\begin(aligned)& \delta_1(\(q_0\),a)=\(q_1\);\qquad \delta_1(\(q_0\),b)=\(q_1,q_3\);\\ & \ delta_1(\(q_1\),a)=\(q_1\);\qquad \delta_1(\(q_1\),b)=\(q_1\);\\ & \delta_1(\(q_1,q_3\) ,a)= \delta(q_1,a)\cup \delta(q_3,a)= \(q_1\)\cup\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \delta(q_1,b)\cup \delta(q_3,b)= \(q_1\)\cup\(q_1\)=\(q_1\). \end(nakahanay)

Dahil wala nang mga bagong state-set, ang "paghila" na pamamaraan ay nagtatapos dito, at nakuha namin ang graph na ipinapakita sa Fig. 7.16.

Regular na Komplemento sa Wika

Ang isa sa mga mahalagang teoretikal na kahihinatnan ng teorema ng pagpapasiya ay ang sumusunod na teorama.

Teorama 7.8. Ang pandagdag ng isang regular na wika ay isang regular na wika.

Hayaang maging regular na wika ang L sa alpabeto V . Pagkatapos ang pandagdag ng wikang L (bilang isang hanay ng mga salita) ay ang wika \overline(L)=V^(\ast)\setminus L.

Ayon sa Theorem 7.7, para sa isang regular na wika L, isang deterministic finite automat M ay maaaring itayo na umaamin sa L . Dahil sa isang deterministic na automat mula sa bawat vertex, para sa bawat input na simbolo, ang isang paglipat sa eksaktong isang vertex ay tinukoy, kung gayon, anuman ang string x sa alpabeto V , mayroong isang natatanging landas para dito sa M ​​, simula sa paunang estado, kung saan binabasa ang string x. Malinaw na ang string x ay pinahihintulutan ng automat M , ibig sabihin, x\in L(M) , kung at kung ang huling estado ng tinukoy na landas ay pinal. Ito ay nagpapahiwatig na ang chain x\notin L(M) kung at kung ang huling estado ng tinukoy na landas ay hindi pangwakas. Ngunit kailangan lang natin ng may hangganan na automat M" , na nagpapahintulot sa chain x kung at kung ang orihinal na finite automat M ay hindi. .

Ang napatunayang teorama ay nagpapahintulot sa amin na bumuo ng isang may hangganan na automat na hindi pinapayagan ang isang tiyak na hanay ng mga kadena sa pamamagitan ng sumusunod na pamamaraan: una, bumuo kami ng isang automat na nagpapahintulot sa isang ibinigay na hanay ng mga kadena, pagkatapos ay tinutukoy namin ito at ipasa sa automat para sa pandagdag tulad ng ipinahiwatig sa patunay ng Theorem 7.8.

Halimbawa 7.10. a. Bumuo tayo ng isang may hangganang automat na nagpapahintulot sa lahat ng mga string sa alpabeto \(0;1\) maliban sa string 101.

Una, bumuo kami ng isang may hangganan na automat na nagpapahintulot sa isang solong chain 101. Ang automat na ito ay ipinapakita sa fig. 7.17.

Ang automat na ito ay quasi-deterministic, ngunit hindi deterministic, dahil hindi ito ganap na tinukoy. Tukuyin natin ito at kumuha ng isang deterministikong katumbas na finite automaton na ipinapakita sa Fig. 7.18.

At sa wakas, ang pagpasa sa karagdagan (at pagpapalit ng pangalan ng mga estado), nakuha namin ang automaton na ipinapakita sa Fig. 7.19.

Tandaan na sa resultang automat, lahat ng vertex, maliban sa vertex s_3 , ay pinal.

Tandaan din na ang pagpasa sa complement, na tinalakay sa patunay ng Theorem 7.8, ay maaari lamang isagawa sa isang deterministikong automat. Kung binaligtad natin ang mga tungkulin ng pangwakas at hindi pangwakas na mga vertex sa automaton na ipinapakita sa Fig. 7.17, makakakuha tayo ng isang automat na tinatanggap ang wika \(\lambda,1,10\) , na hindi - dahil madaling makita - ang hanay ng lahat ng mga string maliban sa string 101.

Tandaan din na ang finite state machine sa Fig. 7.19 ay nagbibigay-daan sa lahat ng mga string na naglalaman ng paglitaw ng string 101 ngunit hindi tumutugma sa string mismo. Narito, halimbawa, ang landas na nagdadala ng 1011 chain: s_0,s_1,s_2,s_3,t.

b. Bumuo tayo ng isang may hangganang automat na nagpapahintulot sa lahat ng mga string sa alpabeto \(0;1\) , maliban sa mga naglalaman ng paglitaw ng string 101. Isaalang-alang ang isang wikang L , na ang bawat string ay naglalaman ng paglitaw ng string 101. Maaari itong tukuyin tulad ng sumusunod:

L=(0+1)^(\ast)101(0+1)^(\ast).

Kailangan nating bumuo ng isang automat upang umakma sa wikang L.

Direkta mula sa regular na expression sa kasong ito, madaling bumuo ng isang may hangganan na automat na nagpapahintulot sa wikang L (Larawan 7.20).

Pagkatapos, sa pamamagitan ng "paghila" na paraan, isasagawa natin ang pagpapasiya. Ang resulta ng pagpapasiya ay ipinapakita sa fig. 7.21.

Para sa kumpletong solusyon ng problema, Fig. 7.21 palitan ang mga tungkulin ng pangwakas at hindi panghuling vertices (Larawan 7.22).

sa. Talakayin natin ang ideya ng pagbuo ng isang may hangganan na automat na nagpapahintulot sa mga iyon at tanging mga string sa alpabeto \(0;1\) na hindi nagsisimula sa string 01 at hindi nagtatapos sa string 11 (ibig sabihin, mga string ng hindi pinapayagan ang form 01x at mga string ng form na y11, anuman ang mga chain na x,y\in\(0;1\) ).

Sa kasong ito, ang pandagdag ng wika kung saan kinakailangan upang bumuo ng isang may hangganan na automat ay ang hanay ng lahat ng naturang mga string ng mga zero at mga nagsisimula sa string 01 o nagtatapos sa string 11. Isang automat na umamin sa set na ito ng ang mga string ay itinayo bilang isang automat para sa pagsasama-sama 01(0+1)^(\ast)+(0+1)^(\ast)11 sa parehong paraan tulad ng sa patunay ng Kleene's theorem (tingnan ang Theorem 7.6).

Ang pag-aari ng klase ng mga regular na wika na isinasara sa ilalim ng complement (tingnan ang Theorem 7.8) ay agad na nagpapahiwatig na ang klase na ito ay sarado sa ilalim ng intersection, set-theoretic at simetriko na mga pagkakaiba.

Corollary 7.3. Para sa alinmang dalawang regular na wika L_1 at L_2, ang mga sumusunod na pahayag ay totoo:

1) regular ang intersection L_1\cap L_2;
2) ang pagkakaiba L_1\setminus L_2 ay regular;
3) simetriko pagkakaiba L_1\vartriangle L_2 regular.

Ang bisa ng mga pahayag ay sumusunod mula sa mga pagkakakilanlan:

\begin(aligned) &(\scriptstyle(\mathsf(1))))\quad L_1\cap L_2= \overline(\overline(L_1) \cup\overline(L_2))\,;\\ &(\scriptstyle (\mathsf(2))))\quad L_1\setminus L_2= L_1\cap \overline(L_2)\,;\\ &(\scriptstyle(\mathsf(3))))\quad L_1\,\triangle\ ,L_2 = (L_1\cup L_2)\setminus (L_1\cap L_2).\end(aligned)

Una, ang nakuha na mga resulta ay nagpapahintulot sa amin na sabihin na ang klase ng mga regular na wika na may paggalang sa mga operasyon ng unyon, intersection, at karagdagan ay isang Boolean algebra, kung saan ang yunit ay ang unibersal na wika, at ang zero ay ang walang laman na wika. . Pangalawa, ang mga algebraic na katangian ng pamilya ng mga regular na wika ay nagbibigay-daan sa amin upang malutas ang mahalagang problema ng pagkilala sa pagkakapareho ng dalawang arbitrary na may hangganan na automata.

Ayon sa Definition 7.10, ang finite automata ay katumbas kung ang mga wikang pinapayagan nila ay pareho. Samakatuwid, upang i-verify ang pagkakapareho ng automata M_1 at M_2 , sapat na upang patunayan na ang simetriko pagkakaiba ng mga wika L(M_1) at L(M_2) ay walang laman. Upang gawin ito, sa turn, ito ay sapat na upang bumuo ng isang automat na umamin sa pagkakaiba na ito at i-verify na ang wikang inaamin nito ay walang laman. Sa pangkalahatan, ang problema ng pagkilala na ang wika ng isang may hangganang automat ay walang laman ay tinatawag na problema ng kawalan ng laman para sa isang may hangganang automat. Upang malutas ang problemang ito, sapat na upang mahanap ang hanay ng mga huling estado ng automat na maaabot mula sa paunang estado. Dahil ang finite state machine ay isang nakadirekta na graph, maaaring malutas ang problemang ito, halimbawa, gamit ang breadth-first search. Ang wikang pinapayagan ng finite automat ay walang laman kung at kung ang hanay ng mga huling estado na maaabot mula sa paunang estado ay walang laman. Sa pagsasagawa, mas mainam na kilalanin ang equivalence ng finite automata gamit ang minimization algorithm, ngunit ngayon ay mahalaga para sa amin na bigyang-diin na ang pangunahing posibilidad ng paglutas ng equivalence na problema ay sumusunod mula sa Theorem 7.7 at ang mga algebraic na kahihinatnan nito.