Ngon Ngu Hinh Thuc

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

Ch¬ng1. V¨n Ph¹m vµ ng«n ng÷ $1. C¸c kh¸i niÖm c¬ b¶n. 1.1. C¸c kh¸i niÖm chung. a. B¶ng ch÷ c¸i. B¶ng ch÷ c¸i lµ mét tËp hîp h÷u h¹n c¸c phÇn tö, c¸c phÇn tö cña nã ta gäi lµ c¸c ch÷ c¸i hoÆc c¸c ký tù. b. VÝ dô. - TËp c¸c ký tù La tinh {a,b,…,z, A,B,…,Z} - TËp c¸c sè{0,1} - TËp c¸c c¸c ký tù La tinh {α ,β ,ϒ ,…}. - TËp c¸c sè {0,1,2,3,4,5,6,7,8,9}. Chó ý r¨ng b¶ng ch÷ c¸i lµ mét tËp hîp nªn ta ta vÉn dïng c¸c ký hiÖu thuéc nh trong lý thuyÕt tËp hîp.

1.2. X©u sinh ra trªn b¶ng ch÷ c¸i. a. X©u. X©u hay tõ ®îc sinh ra trªn b¶ng ch÷ c¸i lµ mét d·y bÊt kú c¸c phÇn tö thuéc d·y ®ã. Gäi x©u lµ x , ®é dµi x©u ®îc ký hiÖu lµ x. Nh vËy kh¸i niÖm x©u còng ®ång nghÜa víi kh¸i niÖm chuçi ký tù. X©u rçng lµ x©u kh«ng chøa phÇn tö nµo thêng ký hiÖu e. b. TËp C¸c x©u. Cho V lµ mét b¶ng ch÷ c¸i, gäi V+ lµ tËp tÊt c¶ c¸c x©u sinh ra tõ V trõ x©u rçng, V* lµ tËp tÊt c¶ c¸c x©u sinh ra tõ V kÓ c¶ x©u rçng. V*= V+∪{e}. c. VÝ dô: V={a,b,c} X+={abc,cab,…} V={0,1} V*={e,00,1,0,100,…} Ta quy íc r»ng an:=aa…a, n lÇn ký tù a. 1.3. C¸c phÐp to¸n trªn x©u. a. GhÐp 2 x©u. Cho x©u x=abc…k, y=rp..q phÐp ghÐp 2 x©u lµ x©u nèi 2 x©u víi nhau xy:= abc…krp..q. b. §¶o ngîc 2 x©u. Cho x=x1x2…xk gäi x©u x’:= xkxk-1…x1 lµ x©u ®¶o cña x.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

1

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

1.4. Kh¸i niÖm ng«n ng÷. a. Ng«n ng÷ trªn b¶ng ch÷ c¸i. Cho V lµ tËp ch÷ c¸i gäi tËp con bÊt kú cña V* lµ ng«n ng÷ trªn b¶ng V. Nh v©y ng«n ng÷ lµ mét tËp hîp ký hiÖu lµ L .Sè phÇn tö cña L lµ lùc lîng cña nã, nÕu h÷u h¹n th× ta nãi L lµ ng«n ng÷ h÷u h¹n vµ v× nã lµ tËp hîp nªn mäi phÐp to¸n trªn L còng gièng nh trªn tËp hîp L1∪L2:={x: x thuéc L1 hoÆc x thuéc L2} L1∩L2:={x: x thuéc L1 vµ x thuéc L2} L1L2:={x=uv: u thuéc L1 vµ v thuéc L2} L0:={e}; Ln:=Ln-1L; L+:=L1L2..Ln n>=1 gäi lµ tËp c¸c x©u cã ®é dµi nhá h¬n hoÆc b»ng n. L*:=L+∪ {e}.

1.3. V¨n ph¹m vµ ng«n ng÷ sinh bëi v¨n ph¹m. a. §Þnh nghÜa. V¨n ph¹m G lµ mét bé gåm c¸c thµnh phÇn G:=(N,T,S,P) trong ®ã: - N lµ mét tËp h÷u h¹n c¸c ký tù kh«ng kÕt thóc. - T lµ mét tËp h÷u h¹n c¸c ký tù kÕt thóc vµ N∩T=∅. - P lµ tËp c¸c luËt sinh(luËt s¶n xuÊt, quy t¾c dÉn xuÊt) , nãi c¸ch kh¸c P lµ c¸c ¸nh x¹ tõ (N∪T)* vµo (N∪T)*. NÕu q∈(N∪T)* lµ ¶nh cña p qua luËt s¶n xuÊt P ta ký hiÖu p→q vµ gäi lµ mét quy t¾c dÉn xuÊt cña P. - NÕu cã mét d·y dÉn xuÊt trong P cã d¹ng p1 →p2, p2 →p3, …,pn-1 →pn ta ký hiÖu p1 *→pn - S lµ ký tù ®Æc biÖt cña N gäi lµ tr¹ng th¸i ®Çu hoÆc ký tù b¾t ®Çu. - Ta chó ý r»ng tõ nay c¸c ký tù kh«ng kÕt thóc ta ký hiÖu b»ng c¸c ch÷ c¸i hoa vÝ nh A, B, C,…cßn c¸c ký tù kÕt thóc ta ký hiÖu lµ c¸c ch÷ c¸i thêng vÝ nh a, b, c,…

Bé m«n khoa häc m¸y tÝnh - HVKTQS

2

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

- C¸c x©u thuéc (N∪T)* th«ng thêng ký hiÖu lµ α , β , γ , χ , δ … b. Ng«n ng÷ sinh bëi v¨n ph¹m. Cho v¨n ph¹m G=(N,T,S,P), ta gäi L(G):={w: w∈T* vµ S *→w} lµ ng«n ng÷ ®îc sinh ra bëi v¨n ph¹m G c. NhËn xÐt. Tõ ®Þnh nghÜa trªn ta suy ra r»ng ng«n ng÷ sinh ra bëi v¨n ph¹m G lµ tËp tÊt c¶ c¸c x©u gåm c¸c ký tù kÕt thóc sau mét sè lÇn ®îc t¸c ®éng bëi c¸c luËt s¶n xuÊt b¾t ®Çu tõ ký tù xuÊt ph¸t. VÝ dô. - Cho G=(N,T,S,P) trong ®ã N={S}, T={a}, P={1. S → aaa, 2. S →aaaS}, Khi ®ã L(G)={a3n,n d¬ng}. - Cho G=(N,T,S,P) trong ®ã N={S}, T={0, 1}, P={1. S → 0S1, 2. S →01}, Khi ®ã S→ 0S1→00S11→000S111→…→0iS1i, vËy nªn L(G)={ 0n1n, n>=1}. - Cho G=(N,T,S,P) trong ®ã N={S,B,C}, T={a,b,c}, P={1. S → aSBC, 2. S →aBC, 3. cB →Bc, 4. aB →ab, 5. bB →bb, 6. bC →bc, 7. cC →cc }, Khi ®ã: - Víi w=anbncn , ¸p dông quy t¾c 1 n-1 lÇn ®îc: S*→an-1S(BC)n-1

(1)

- ¸p dông tiÕp quy t¾c 2 mét lÇn n÷a ta ®îc: S*→an (BC)n = S*→an BC(BC)n-1

(2)

- ¸p dông tiÕp quy t¾c 4 : S*→anbC(BC)n-1

(3)

- ¸p dông quy t¾c 6 : S*→anbc(BC)n-1= S*→anbcBC(BC)n-2

(4)

- ¸p dung quy t¾c 3: S*→anbBcC(BC)n-2

(5)

- ¸p dung quy t¾c 5,7: S*→anb2ccBC(BC)n-3

(6)

Bé m«n khoa häc m¸y tÝnh - HVKTQS

3

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

- ¸p dung quy t¾c 3 : S*→anb2cBcC(BC)n-3

(7)

- ¸p dung quy t¾c 3 : S*→anb2BccC(BC)n-3

(8)

- ¸p dung quy t¾c 5,7 : S*→anb3c3(BC)n-3 = S*→anb3c3BC(BC)n-4

(9)

- ¸p dung quy t¾c 3 lÇn 3 vµ quy t¾c 7 ta ®îc: S*→anb3Bc2cC(BC)n-4 vµ S*→anb4c4(BC)n-4

(10)

- ¸p dung quy t¾c 3 lÇn 3 vµ quy t¾c 7 ta ®îc: S*→anb3Bc2cC(BC)n-4 vµ S*→anb4c4(BC)n-4

(11)

- LÆp l¹i c¸c bíc tõ c«ng thøc (4) ®Õn (11) ta ®îc: S*→anbncn =w. VËy w∈L(G). Ngîc l¹i ta chøng minh nÕu w∈L(G) th× w ph¶i cã d¹ng anbncn ThËt vËy, ®Ó t¹o ra mét chuçi chØ gåm c¸c ký tù kÕt thóc th×: 1. LuËt 1 cã thÓ t¸c ®éng n lÇn, mçi lÇn l¹i sinh ra ký tù xuÊt ph¸t. 2. Sau nlÇn t¸c ®éng lªn luËt thø nhÊt th× x©u sinh ra cã d¹ng anS(BC)n. 3. §Ó ký tù xuÊt ph¸t mÊt ®i ta ph¶i t¸c ®éng x©u võa nhËn ®îc lªn luÊt thø 2 vµ luËt nµy chØ t¸c ®éng lªn chuèi duy nhÊt 1 lÇn vµ do ®ã ta ®îc x©u míi lµ an+1(BC)n+1. 4. §Ó ký tù kh«ng kÕt thóc B,C biÕn khái x©u th× ph¶i sö dông luËt 4,3,5,7 ®Ó h¹ bËc cña B,C vµ khö dÇn B,C theo thø tù ®îc m« t¶ tõ (4) ®Õn (11) vµ chØ cã c¸ch ®ã ta míi cã thÓ nhËn ®îc x©u gåm c¸c ký tù kÐt thóc an+1bn+1cn+1. VËy nªn L(G)={ an+1bn+1cn+1, n>=0}. d. V¨n ph¹m t¬ng ®¬ng. Hai v¨n ph¹m G1= G=(N1,T1,S1,P1) vµ G2=(N2,T2,S2,P2) gäi lµ t¬ng ®¬ng, ký hiÖu G1≈ G2 nÕu L(G1) = L( G2)

Bé m«n khoa häc m¸y tÝnh - HVKTQS

4

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

$2. C¸c lo¹i v¨n ph¹m Vµ ng«n ng÷ sinh ra bëi v¨n ph¹m. 2.1. Ph©n lo¹i v¨n ph¹m. a. V¨n ph¹m lo¹i 0. V¨n ph¹m G mµ c¸c quy t¾c dÉn xuÊt cña nã kh«ng cã bÊt kú ®iÒu kiÖn rµng buéc nµo gäi lµ v¨n ph¹m lo¹i 0 b. V¨n ph¹m lo¹i 1. V¨n ph¹m G mµ c¸c quy t¾c dÉn xuÊt cña nã cã d¹ng α→ β ∈ P tho¶ ®iÒu kiÖn α , β ∈ (N∪T)+ vµ α<= β . c. V¨n ph¹m lo¹i 2. V¨n ph¹m G mµ c¸c quy t¾c dÉn xuÊt cña nã cã d¹ng α→ β ∈ P tho¶ ®iÒu kiÖn α∈ N vµ β ∈ (N∪T)+. V¨n ph¹m lo¹i 2 cã tªn gäi lµ v¨n ph¹m phi ng÷ c¶nh. d. V¨n ph¹m lo¹i 3. V¨n ph¹m G mµ c¸c quy t¾c dÉn xuÊt cña nã cã d¹ng A→aB hoÆc A→a víi A, B ∈N vµ a∈T. V¨n ph¹m lo¹i 3 cã tªn lµ v¨n ph¹m chÝnh quy. e. NhËn xÐt. V¨n ph¹m c¸c lo¹i tho¶ ®iÒu kiÖn sau: 3⇒2⇒1⇒0. f. C¸c vÝ dô. g. VÝ dô 1. G=(N,T,S,P); N={S,A,B}; V={a,b}; P gåm 1. S →aB, 2. S →bA, 3. A →a, 4. A →aS, 5. A →bAA, 6. B →b, 7. B →bS, 8. B →aB. Râ rµng ®©y lµ v¨n ph¹m phi ng÷ c¶nh. VÝ dô 2. G=(N,T,S,P); N={S,A,B}; V={0,1}; P gåm 1. S →0A, 2. S →1B, 3. A →0A, 4. A →0S, 5. A →1B, 6. B →1B, 7. B →1, 8. B →0, 9. S→0. Râ rµng ®©y lµ v¨n ph¹m chÝnh quy.

2.2. Ph©n lo¹i ng«n ng÷. a. Ng«n ng÷ lo¹i 0. Ng«n ng÷ sinh bëi v¨n ph¹m lo¹i 0 gäi lµ ng«n ng÷ lo¹i 0. b. Ng«n ng÷ lo¹i 1. Ng«n ng÷ ®îc sinh ra bëi v¨n ph¹m lo¹i 1 gäi lµ ng«n ng÷ lo¹i 1.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

5

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

c. Ng«n ng÷ lo¹i 2. Ng«n ng÷ ®îc sinh ra bëi v¨n ph¹m lo¹i 2 gäi lµ ng«n ng÷ lo¹i 2. d. Ng«n ng÷ lo¹i 3. Ng«n ng÷ ®îc sinh ra bëi v¨n ph¹m lo¹i 3 gäi lµ ng«n ng÷ lo¹i 3 hay lµ ng«n ng÷ chÝnh quy. e. NhËn xÐt. V¨n ph¹m c¸c lo¹i tho¶ ®iÒu kiÖn sau: 3⇒2⇒1⇒0.

2.3. C©y dÉn xuÊt. a. C©y. C©y lµ tËp hîp h÷u h¹n c¸c nót vµ c¸c cung trong ®ã: - Cã duy nhÊt 1 nót gäi lµ nót gèc. - Mçi mét nót trong c©y trõ nót gèc ®îc nèi víi mét nót kh¸c b»ng mét cung ®i vµo duy nhÊt. - Mçi mét nót trong c©y trõ nót gèc nÕu bá cung ®i vµo th× nã trë thµnh gèc cña mét c©y , gäi lµ c©y con cña c©y ®· cho. b. C©y dÉn xuÊt. Cho v¨n ph¹m phi ng÷ c¶nh G=(N,T,S,P). Gi¶ sö w∈L(G), w=w1 w2…wn , wi∈T vµ S*→w, gi¶ sö r»ng dÉn xuÊt cña w lµ d·y c¸c quy t¾c cã d¹ng: S→A11 A12… A1n→A21 A22… A2m…→ w1 w2…wl, x©y dùng c©y tho¶ ®iÒu kiÖn sau: - B¬c 0: X©y dùng gèc cã nh·n S - Bíc 1: C¸c ®Ønh con cña S lµ c¸c ký tù ®îc sinh ra do ¸p dông luËt sinh thø 1. (§ã lµ A11 -

A12 …

A1n

Bíc 2. C¸c ®Ønh con cña A1j j =1..n. : Lµ nh÷ng ký tù ®îc sinh ra

do ¸p dông luËt sinh thø 2 - Bíc i: Gi¶ sö ®· x¸c ®Þnh ®îc c¸c ®Ønh ë bíc i-1, c¸c ®Ønh con ®îc sinh ra ë bíc thø i lµ c¸c ®Ønh sinh ra tõ c¸c ®Ønh ë bíc thø i1 khi ¸p dông luËt sinh thø i. - C¸c nót l¸ ®äc theo thø tù tõ tr¸i sang ph¶I lµ x©u w H×nh sau m« t¶ c©y dÉn xuÊt cña w

Bé m«n khoa häc m¸y tÝnh - HVKTQS

6

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

S A11

A12 …

A21 w1

A1n

A22…

A2m

w2 …

wn

VÝ dô: Cho G=(N,T,S,P); N={S,A}; T={a,b}; P gåm 1. S →aAS, 2. A →SbA, 3. A →SS, 4. S→a, 5. A→ba. w=aabbaa, Víi w ta cã dÉn xuÊt sau: S →aAS →aSbAS →aabAS →aabbaS→aabbaa. C©y dÉn xuÊt cña w cã d¹ng sau: S a A

S a

S a

A b

b

a

c. §Þnh lý 1.1. Cho v¨n ph¹m phi ng÷ c¶nh G=(N,T,S,P), gi¶ sö w lµ x©u kh¸c rçng, khi ®ã S* →w khi vµ chØ khi tån t¹i c©y dÉn xuÊt trong v¨n ph¹m G mµ cña c¸c nót l¸ t¹o nªn x©u w.

2.4. Mét sè tÝnh chÊt cña ng«n ng÷. Ng«n ng÷ nh ta ®· thÊy ë trªn thùc chÊt lµ tËp hîp do ®ã nã cã ®Çy dñ c¸c tÝnh chÊt cña nã, tuy nhiªn ë ®©y ta cÇn xem xÐt thªm nh÷ng tÝnh chÊt mang tÝnh ®Æc thï cña ng«n ng÷ do v¨n ph¹m sinh ra.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

7

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

a. TÝnh chÊt 1. Ng«n ng÷ sinh ra bëi v¨n ph¹m lµ ®ãng víi phÐp hîp, phÐp giao vµ nh©n ng«n ng÷.(TÝnh ®èng cã nghÜa lµ nÕu 2 v¨n ph¹m cïng lo¹i th× ng«n ng÷ sinh ra cïng lo¹i vµ hîp giao vµ nh©n cña c¸c ng«n ng÷ trªn cïng lo¹i) - Chøng minh tÝnh ®ãng cña phÐp hîp: ThËt vËy,gi¶ sö G1=(N1,T,S1,P1), G2=(N2,T,S2,P2) lµ 2 v¨n ph¹m cïng lo¹i vµ L1, L2 lµ c¸c ng«n ng÷ t¬ng øng. Gäi L= L1 ∪ L2 ta chøng minh tån t¹i v¨n ph¹m G cïng lo¹i víi G1, G2 sinh ra L. Ta x©y dung V¨n ph¹m G nh sau: 1. N:= N1∪ N2∪{S}, 2. S kh«ng thuéc N1, N2 3. T:=T 4. TËp luËt sinh P ®îc x¸c ®Þnh: P:= P1∪P2 ∪{S → S1, S → S2} Khi ®ã: - V¨n ph¹m võa nhËn ®îc cïng lo¹i víi víi 2 lo¹i v¨n ph¹m trªn do 2 luËt sinh võa thªm. - Ta chøng minh L(G)= L1 ∪ L2. Gi¶ sö w ∈ L, khi ®ã S*→w trong G, theo c¸ch x©y dùng P th× S→S1 hoÆc S→S2 v× vËy hoÆc S1*→w hoÆc S2*→w nghÜa lµ w∈L1 hoÆc w∈L2 tóc lµ w ∈ L1 ∪ L2. Chøng minh tÝnh ®ãng cña phÐp giao: Tõ c¸c v¨n ph¹m trªn ta x©y dùng G sao cho L(G)=L1∩L2 nh sau: 1. T:=T1∩T2, 2. N:=N1∪N2∪ Γ 1∪ Γ 2∪{S}, Víi Γ 1={a’| a∈T1 },Γ 2={b’| b∈T2 }, Γ 1∩ Γ 2=∅ 3. P:=P’1∪P’2∪{S → S1S2}∪P’’1∪P’’2

Bé m«n khoa häc m¸y tÝnh - HVKTQS

8

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

- P’’1 lµ tËp c¸c quy t¾c nhËn ®îc tõ tËp quy t¾c P1 b»ng c¸ch thay c¸c ký hiÖu c¬ b¶n trong T1 mµ chóng cã mÆt trong quy t¾c cña P1 bëi ký hiÖu míi ®èi ngÉu víi nã. - P’’2 lµ tËp c¸c quy t¾c nhËn ®îc tõ tËp quy t¾c P2 b»ng c¸ch thay c¸c ký hiÖu c¬ b¶n trong T2 mµ chóng cã mÆt trong quy t¾c cña P2 bëi ký hiÖu míi ®èi ngÉu víi nã. - Cßn P’1, P’2 ®îc x¸c ®Þnh nh sau: - P’1={a’b’→b’a’ | a∈T1 }, b∈T2 } - P’2={a’a’→a | a∈T1∩ T2 } KiÓm tra l¹i ta thÊy ®iÒu kh¼ng ®Þnh lµ ®óng. Chøng minh tÝnh ®ãng cña phÐp nh©n: Tõ c¸c v¨n ph¹m trªn ta x©y dùng G sao cho L(G)=L1.L2 nh sau: G=(N,T,S,P) trong ®ã T:=T1∪T2, N:=N1∪N2∪{S}, P:=P1∪P2∪{S → S1S2}. Ta chøng minh L(G)⊆L1L2, thËt vËy gi¶ sö w ∈L(G) khi ®ã tån t¹i d·y dÉn xuÊt S *→w Muèn vËy ®Çu tiªn ph¶i ¸p dông quy t¾c S→S1S2 sau ®ã ®Ó khö ®îc S1 ta ph¶i ¸p dông c¸c luËt P1, sau h÷u h¹n bíc ta sÏ ®îc d·y cã d¹ng w1S2, ¸p dông tiÕp c¸c luËt cña P2 ta sÏ khö ®îc S2 vµ nhËn ®îc x©u w1 w2=w Ta nhËn ®îc ®iÒu cÇn chøng minh. Ngîc l¹i t¬ng tù. - Ta m« t¶ c¸c tÝnh chÊt trªn th«ng qua vÝ dô sau: Cho v¨n ph¹m G1=(N1,T,S1,P1), G2=(N2,T,S2,P2) lµ 2 v¨n ph¹m cïng lo¹i trong ®ã N1={S1}, T1={a, b}, P1={ S1 →ab, S1→aS1b}; N2={S2}, T2={c}, P2={ S2 →cS2, S2→c}. X©y dùng v¨n ph¹m G3=(N, T, S, P) sao cho: L(G3)= L(G1)∪L(G2); L(G3)= L(G1) ∩L(G2); L(G3)= L(G1). L(G2). 1.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

9

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

2. Ta ®· biÕt L(G1)={anbn, n>=1}, L(G2)={cm, m>=1} . Ta chøng minh L(G3)= L(G1)∪L(G2)={ anbn,cm, n, m>=1}.V¨n ph¹m G3 ®îc x©y dùng nh sau: N:={N1∪N2∪{S ∉N1∪N2}; T:={a,b,c} vµ c¸c luËt sinh nh sau:P:={S → S1, S → S2, S1→ab, S1→aS1b}, S2 →cS2, S2→c}. - Gi¶ sö w∈L(G3) khi ®ã tån t¹i d·y dÉn xuÊt S*→w (øng víi S*→w1 →w2 →w3 …→wk=w). §Ó cã thÓ nhËn ®îc w th× w1 chØ cã thÓ lµ S1 hoÆc S2. NÕu w1 lµ S1 w2=a2S1b2… wk-1=akS1bk ,wk=ak+1bk+1 vËy suy ra w∈L(G3) ⊆L(G1) ∪L(G2) - Ngîc l¹i gi¶ sö w ∈L(G1) ∪L(G2) ta cã thÓ coi w ∈L(G1) khi ®ã tån t¹i d·y dÉn xuÊt trong G1 cã d¹ng S1*→w (øng víi S1*→w1=aS1b →w2= a2S1b2 →w3 …→wk=anbn=w). X©y dùng d·y dÉn xuÊt sau: S→S1*→w

(øng

víi

S→S1*→w1=aS1b

→w2=

a2S1b2

→w3

…

→wk=anbn=w). VËy w∈L(G3). 2. Ta x©y dùng G3 sao cho L(G3)= L(G1). L(G2)={anbncm}}. N:={S, S1,S2}, T:={a,b,c}, P:={ S→S1S2, S1 →ab, S1→aS1b, S2 →cS2, S2→c}. Ta chøng minh bao hµm thøc G=(N,T,S,P). L(G3) ⊆ L(G1). L(G2). Gi¶ sö w∈ L(G3) khi ®ã tån t¹i d·y dÉn xuÊt trong G1 cã d¹ng S*→w (øng víi S*→S1S2→w1=aS1bS2 →w2= a2S1b2S2 →w3 …→wk=anbnS2→anbnc S2→…anbncm-1S2 →anbncm=w) mµ anbn∈ L(G1) vµ cm∈ L(G2) v©y nªn w∈ L(G1).L(G2). Ta chøng minh ®iÒu ngîc l¹i, gi¶ sö w∈ L(G1).L(G2) hay w=w1w2 trong ®ã w1∈ L(G1) ,w2∈ L(G2) v× vËy tån t¹i dÉn xuÊt S1*→w1 vµ S2*→w2. LËp dÉn xuÊt míi

Bé m«n khoa häc m¸y tÝnh - HVKTQS

10

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

S→S1S2 →aS1bS2 …→anbnS2=w1S2→anbnc S2→…anbncm-1S2 →anbncm=w , ®©y lµ dÉn xuÊt trong L(G3), tõ ®©y suy ra ®iÒu ph¶i chøng minh. G=(N,T,S,P) c. TÝnh chÊt 2. Lo¹i cña ng«n ng÷ ®ãng víi phÐp lÆp. NghÜa lµ Ln cïng lo¹i víi L. d. TÝnh chÊt 3. Cho G=(N,T,S,P) kh«ng ph¶i lµ v¨n ph¹m lo¹i 0 víi ký tù xuÊt ph¸t S cã ë vÕ ph¶i cña quy t¾c dÉn xuÊt, khi ®ã tån t¹i v¨n ph¹m G’=(N’,T’,S,P’) cïng lo¹i vµ t¬ng ®¬ng víi G nhng kh«ng cã ký tù xuÊt ph¸t ë vÕ ph¶i cña quy t¾c dÉn xuÊt. Chøng minh. X©y dùng G’=(N’,T,S’,P’) nh sau: - N’:=N∪{S’}, ë ®©y S’ lµ ký hiÖu míi cha cã trong N vµ T P’:=P∪{ S’→α /S→α∈ P, α∈ (N∪T)+}, nghÜa lµ P’ gåm c¸c quy t¾c cña G bæ sung thªm c¸c quy t¾c d¹ng S’→α nÕu trong P cã quy t¾c S→α . Víi quy íc trªn ta thÊy - Kh«ng cã quy t¾c nµo mµ ký tù xuÊt ph¸t xuÊt hiÖn ë vÕ ph¶i cña dÉn xuÊt. Gi¶ sö

w∈L(G) khi ®ã tån t¹i d·y dÉn xu©t S*→ w vµ tån t¹i

α∈ (N∪T)* sao cho S→α *→ w. Theo c¸ch x©y dùng dÉn xuÊt v× trong G cã S→α nªn trong G’ cã S’→α v× vËy dÉn xuÊt S’→α *→ w lµ dÉn xuÊt trong G’ vËy nªn w∈L(G) do ®ã L(G) ⊆L(G’). Ngîc l¹i nÕu w∈L(G’) nghÜa lµ S’*→w tån t¹i α∈ (N∪T)* S’→α *→ w mµ S’→α * cã t¬ng øng S→α trong G vËy nªn S→α *→w lµ dÉn xuÊt trong G cho nªn L(G’) ⊆L(G). d. NhËn xÐt. TÝnh chÊt 3 cho phÐp chóng ta coi c¸c v¨n ph¹m lo¹i 1,2,3 kh«ng cã c¸c ký tù xuÊt ph¸t n»m ë vÕ ph¶i cña c¸c dÉn xuÊt vµ do e∈L(G) nªn trong luËt sinh ph¶i cã S→e.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

11

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

e. TÝnh chÊt 4. Cho G kh«ng ph¶i v¨n ph¹m lo¹i 0, khi ®ã hoÆc L(G)\{e} hoÆc L(G) ∪{e} lµ ng«n ng÷ cïng lo¹i víi L(G). Chøng minh. Theo nhËn xÐt cña tÝnh chÊt 3 nÕu v¨n ph¹m kh¸c 0 sinh ra tõ rçng th× ph¶i cã dÉn xuÊt S→e v× vËy L(G) ∪{e} vµ L(G)\ { e} ®ång nghÜa víi viÖc lo¹i bá hay bæ sung quy t¾c S→e cña tËp P do ®ã lo¹i cña ng«n ng÷ kh«ng thay ®æi. f. TÝnh

chÊt

5.(TÝnh

chÊt ®Ö quy cña ng«n

ng÷)

NÕu

G=(N,T,S,P) lµ v¨n ph¹m lo¹i 1(c¶m ng÷ c¶nh) khi ®ã G lµ ®Ö quy. Ta nãi mét v¨n ph¹m cã tÝnh ®Ö quy nÕu tån t¹i thuËt to¸n x¸c ®Þnh mét x©u w cho tríc cã thuéc L(G) hay kh«ng. Tríc tiªn ta cã c¸c nhËn xÐt sau: -

Nh¾c l¹i r»ng : ChØnh hîp p tõ n phÇn tö lµ mét bé gåm p phÇn

tö cã ph©n biÖt thø tù tõ n phÇn tö ®·. Sè lîng c¸c chØnh hîp lµ np. - G=(N,T,S,P) lµ c¶m ng÷ c¶nh x©u rçng e ∈L(G) khi vµ chØ khi cã tËp luËt

sinh P cã S→e do vËy cã thÓ lo¹i bá luËt nµy ®Ó ®îc v¨n

ph¹m c¶m ng÷ c¶nh míi kh«ng chøa tõ rçng G’:=(N,T,S,P’) víi ng«n ng÷ t¬ng øng L(G’)=L(G)\{e}. - Trong mäi quy t¾c dÉn xuÊt cña G’ ®é dµi vÕ ph¶i ph¶i lín h¬n ®é dµi vÕ tr¸i, gi¶ sö r»ng V= N ∪T vµ V= n vµ e ≠ w ∈L(G’) nghÜa lµ tån t¹i S*→w hay cô thÓ h¬n ta cã d·y dÉn xuÊt : S→α 1→α 2→…α

m

=w, vµ

theo ®Þnh nghÜa ng«n ng÷ suy ra α 1<=α 2<=…<=α m. - Gi¶ sö r»ng tån t¹i chØ sè i sao cho α i, α

i+1,

…α

i+j

cã ®é dµi nh

nhau vµ b»ng p , khi ®ã nÕu j>=np th× trong d·y dÉn xuÊt trªn cã Ýt nhÊt 2 x©u gièng nhau.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

12

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

- Theo nhËn xÐt vÒ chØnh hîp suy ra V* cã tèi ®a lµ np x©u cã ®é dµi p, do ®ã trong trêng hîp gièng nhau ta cã thÓ lîc bá Ýt nhÊt lµ 1 bíc trong d·y dÉn xuÊt tøc lµ nÕu α

r

= α

s

(r<s) th× dÉn xuÊt cã thÓ

m« t¶ l¹i ng¾n h¬n nh sau: S→α 1→…α r→α s+1…→α m =w Tõ ®©y ta rót ra nhËn xÐt sau: - NÕu cã mét dÉn xuÊt cña w th× dÉn xuÊt ®ã kh«ng qu¸ dµi, cã nghÜa lµ ®é dµi cña w lµ h÷u h¹n. Tõ c¸c nhËn xÐt trªn ta chøng minh tÝnh chÊt ®Æt ra theo c¸c bíc sau : -

Ta lu«n coi L(G) kh«ng chøa tõ rçng vµ ®iÒu nµy ®ång nghÜa víi viÖc trong P kh«ng cã quy t¾c S→e.

- Gi¶ sö w∈L(G) suy ra w∈V+, w=n( v× x©u kh«ng qu¸ dµi), ta chØ thuËt to¸n b»ng c¸ch x©y dùng tËp Tm nh sau: 1. Tm:={ α α ∈V+, α<=n; S*→α cã kh«ng qu¸ m bíc} 2. T0:={S} 3. Ta cã c«ng thøc truy håi sau: Tm= Tm-1∪{α β→ α ∈ P ; β ∈ Tm-1; α<=n } ThËt vËy, gi¶ sö α∈ Tm; α<=n } khi ®ã tån t¹i dÉn xuÊt s*→α , kh«ng qu¸ m bíc vµα<=n , suy ra s→α 1 →α 2 …→β→α . §iÒu nhËn ®îc cuèi cïng nghÜa lµ s*→β kh«ng qu¸ m-1 bíc vµ

β<=n , suy

ra β ∈ Tm-1 ,do ®ã α∈ Tm-1∪{α β→ α ; β ∈ Tm-1; α<=n } Ngîc l¹i nÕu α∈ Tm-1∪{α β→ α ; β ∈ Tm-1; α<=n }, khi ®ã v× β→ α vµ s*→β nªn ta nhËn ®îc:

Bé m«n khoa häc m¸y tÝnh - HVKTQS

13

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

+ s*→β→α + Do s*→β kh«ng qu¸ m-1 bíc nªn s*→α kh«ng qu¸ m bíc, do ®ã α∈ Tm. Tõ trªn ta rót ra c¸c nhËn xÐt sau: 1. NÕu S*→α vµ α<=n th× víi c¸ch x©y dùng trªn α ph¶i n»m trong Tm nµo ®ã, ng¬c l¹i nÕu S kh«ng dÉn ®îc ra α th× hoÆc α>n hoÆc ∉Tm nµo. 3. Tm kh«ng gi¶m, nghÜa lµ Tm-1 ⊆Tm víi mäi m>=1 vµ d·y bÞ chÆn do nhËn xÐt trªn, vËy tån t¹i T’:= ∪ Tm =TM0 vµ khi ®ã nÕu w ∉Tm th× w∉ L(G) dÜ nhiªn nÕu w ∈Tm th× S*→w. 4. Cuèi cïng gi¶ sö r»ng V=q khi ®ã trong V+ sè x©u cã ®é dµi nhá 5. h¬n hoÆc b»ng n lµ s=1+q+…+qn<(1+q)n+1 vµ lµ h÷u h¹n trong T’, ®iÒu nµy cã nghÜa lµ tån t¹i thuËt to¸n ®Ó x¸c ®Þnh xem w cã thuéc L(G) hay kh«ng. g. C¸c vÝ dô minh ho¹ VÝ dô 1. Cho G=(N,T,S,P) trong ®ã N:={S,B,C}, T:={a,b,c} P: 1. S→aSBC, 2. S→aBC, 3. cB→Bc, 4. aB→ab, 5. bB→bb, 6. bC→bc, 7. cC→c¸c. XÐt tõ w=abac ta x¸c ®Þnh w thuéc L(G) hay kh«ng. X©y dùng T0:={S}, T1:={S, aSBC, aBC}, T2:={ S, aSBC, aBC,abC}, T3:={ S, aSBC, aBC,abC,abc}, T4:={ S, aSBC, aBC,aBC,abc}:=T’ v× abac kh«ng thuéc T’ nªn w∉ L(G) VÝ dô 2.

Cho v¨n ph¹m

G=(N,T,S,P) trong ®ã N={ S, a 1, a2,

a3…,an},T={ a1, a2,a3…,an}, tËp quy t¾c cã d¹ng: P={1. S→a1A1, 2. A1→a2A2, 3. A2→a3A3,…, An-2→an-1An-1, An-1→an §©y lµ v¨n ph¹m chÝnh quy vµ ng«n ng÷ ®îc sinh ra cã d¹ng L(G)= {w= a1 a2a3…an}

Bé m«n khoa häc m¸y tÝnh - HVKTQS

14

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

VÝ dô 3. Cho v¨n ph¹m G= G=(N,T,S,P) trong ®ã N={S},T={ a1, a2,a3…,an}, tËp quy t¾c cã d¹ng: P={1. S→aS, 2. S→a, a∈ T}. §©y lµ v¨n ph¹m chÝnh quy vµ L(G)={w∈T+}=T+. VÝ dô 4. Cho v¨n ph¹m G= G=(N,T ,S,P) trong ®ã N={S},T={ a}, tËp quy t¾c cã d¹ng: P={1. S→aS}. §©y lµ v¨n ph¹m chÝnh quy song L(G)=φ v× kh«ng bao giê nhËn ®îc x©u kÕt thóc. VÝ dô 5. Cho v¨n ph¹m G= G=(N,T,S,P) trong ®ã N={S, A},T={ a,b}, tËp quy t¾c cã d¹ng: P={1. S→aSb, 2. S→ab}. §©y lµ v¨n ph¹m chÝnh quy vµ L(G)={anbn; n>=1}. VÝ dô 6. Cho v¨n ph¹m G= G=(N,T,S,P) trong ®ã N={S, A},T={ a,b}, tËp quy t¾c cã d¹ng: P={1. S→aS, 2. S→aA, 3. A→bA, 4. A →b}. §©y lµ v¨n ph¹m chÝnh quy vµ L(G)={anbm; m,n>=1}. VÝ dô 7. Cho v¨n ph¹m G= G=(N,T,S,P) trong ®ã N={S, A},T={ a,b}, tËp quy t¾c cã d¹ng: P={1. S→Sa, 2. A→aAb, 3. A→ab, 4.S →Aa}. §©y lµ v¨n ph¹m phi ng÷ c¶nh vµ L(G)={anbnam; m,n>=1}. VÝ dô 8. Cho v¨n ph¹m G= G=(N,T,S,P) trong ®ã N={S, a 1, a2, …,ak } T={ a1, a2,a3…,ak,b}, tËp quy t¾c cã d¹ng: P={1. S→SaiAi, 2. S→b, aiAj→Ajai, bAi→aib }.Ng«n ng÷ L(G)={wbw∈T*}. Ta minh ho¹ cho trêng hîp nµy nh sau: Víi k=2, N={S, a1, a2 },T={ a1, a2, b}, tËp quy t¾c cã d¹ng: P={1. S→SA1a1, 2. S→SA2a2 3. S→b, 4. a1 A1→A1a1, 5. a2 A2→A2a2 , 6. a1A2→A2a1, 7. a2 A1→A1a2 , 8. bA1→a1b, 9. bA2→a2b}.

Ch¬ng 2. Automat vµ ng«n ng÷ chÝnh quy. $1.Automat Bé m«n khoa häc m¸y tÝnh - HVKTQS

15

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

5.1. C¸c kh¸i niÖm c¬ b¶n. a. C¬ chÕ ho¹t ®éng cña Automat. Ta cã thÓ m« t¶ automat nh mét hÖ thèng xö lý th«ng tin gåm c¸c bé phËn: 1.X – kªnh nhËn th«ng tin vµo 2.Y – kªnh ph¸t tÝn hiÖu ra 3.S – bé chÕ biÕn xö lý th«ng tin vµ biÕn ®æi tr¹ng th¸i x

Bé chÕ biÕn th«ng tin vµ biÕn ®æi tr¹ng th¸i S

y

§ång thêi ta quy íc c¬ chÕ ho¹t ®éng cña hÖ thèng lµ rêi r¹c nghÜa lµ th«ng tin vµo - ra thùc hiÖn liªn tiÕp t¹i nh÷ng thêi ®iÓm kh¸c nhau. b. C¸c lo¹i Automat. 1. Automat Mealy. Bé M=( X,Y, S,δ ,λ ) trong ®ã X -TËp h÷u h¹n c¸c ký hiÖu vµo Y - TËp h÷u h¹n c¸c ký hiÖu ra S - TËp h÷u h¹n gäi lµ tËp c¸c tr¹ng th¸i δ

- ¸nh x¹ tõ XxS→S gäi lµ hµm chuyÓn tr¹ng th¸i.

λ

- ¸nh x¹ tõ XxS→Y gäi lµ hµm ®a th«ng tin ra.

§îc gäi lµ Automat Mealy Víi ®Þnh nghÜa trªn ta hiÓu Automat Mealy ho¹t ®éng theo c¬ chÕ tÝn hiÖu ph¸t ra phô thuéc vµo tÝn hiÖu vµo vµ tr¹ng th¸i nhËn tÝn hiÖu. 2. Automat Moore. Bé M=( X,Y, S,δ ,λ ) trong ®ã X -TËp h÷u h¹n c¸c ký hiÖu vµo Y - TËp h÷u h¹n c¸c ký hiÖu ra S - TËp h÷u h¹n gäi lµ tËp c¸c tr¹ng th¸i δ

- ¸nh x¹ tõ XxS→S gäi lµ hµm chuyÓn tr¹ng th¸i.

λ

- ¸nh x¹ tõ S→Y gäi lµ hµm ®a th«ng tin ra.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

16

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

§îc gäi lµ Automat Moore Víi ®Þnh nghÜa trªn ta hiÓu Automat Moore ho¹t ®éng theo c¬ chÕ tÝn hiÖu ph¸t ra phô thuéc tr¹ng th¸i nhËn tÝn hiÖu. 3. Automat tr¹ng th¸i. Automat tr¹ng th¸i lµ bé M=( X,S,δ ) trong ®ã X -TËp h÷u h¹n c¸c ký hiÖu vµo S - TËp h÷u h¹n gäi lµ tËp c¸c tr¹ng th¸i δ

- ¸nh x¹ tõ XxS→S gäi lµ hµm chuyÓn tr¹ng th¸i.

Víi ®Þnh nghÜa trªn ta hiÓu Automat tr¹ng th¸i ho¹t ®éng theo c¬ chÕ kh«ng cã kªnh ra, nã chØ nhËn tÝn hiÖu ph¸t ra vµ ®æi tr¹ng th¸i . Râ rµng Automat tr¹ng th¸i lµ trêng hîp riªng cña Automat Moore khi Y trïng víi S. 4. Automat kh«ng trÝ nhí. Bé M=( X,Y, S,λ ) trong ®ã X -TËp h÷u h¹n c¸c ký hiÖu vµo Y - TËp h÷u h¹n c¸c ký hiÖu ra S - Tr¹ng th¸i, λ

- ¸nh x¹ tõ X→Y gäi lµ hµm ®a th«ng tin ra.

Gäi lµ Automat kh«ng trÝ nhí. Automat kh«ng trÝ nhí ho¹t ®éng chØ cã mét tr¹ng th¸i. ë mäi thêi ®iÓm tÝn hiÖu ph¸t ra chØ phô thuéc tÝn hiÖu vµo. VÝ dô: Automat m« t¶ phÐp céng cña 2 sè nhÞ ph©n mµ tõ vµo lµ c¸c phÇn tö cña tËp X={00,01,10,11} ®Çu ra y lµ c¸c phÇn tö Y={0,1}. Kªnh vµo x cã 2 m¹ch x1, x2 t¬ng øng c¸c sè nhÞ ph©n 0,1.

X1 X2

y

Bé m«n khoa häc m¸y tÝnh - HVKTQS

17

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

B¶ng hµm chuyÓn tr¹ng vµ hµm ra ®îc cho díi d¹ng sau:

X

00

01

10

11

S S0 S1

S0 S0

S0 S1

S0 S1

S1 S1

λ

00

01

10

11

0 1

1 0

1 0

0 1

5.2. C¸c ph¬ng ph¸p biÓu diÔn Automat. a. Ph¬ng ph¸p ®å thÞ. BiÓu diÔn Automat díi d¹ng ®å thÞ cã híng trong ®ã: 6. Mçi tr¹ng th¸i S øng víi mét nót M=( X,Y, S,δ ,λ ) 7. Cung cã híng ®i tõ nót s1 ®Õn s2 nÕu δ (s1,a)=s2. 8. Trªn cung (s1,s2) ta ghi gi¸ trÞ ®Çu vµo a. VÝ dô: Víi Automat h÷u h¹n M=( X, S,δ ,s0, F) trong ®ã X - TËp h÷u h¹n c¸c ký hiÖu vµo S - TËp tr¹ng th¸i s0 - Tr¹ng th¸i ®Çu F - Tr¹ng th¸i kÕt thóc Ta xÐt automat sau: M=( X, S,δ ,s0,{ s0}) trong ®ã X={0,1}, S={s0, s1, s2, s3} δ ( s0, 0)= s2, δ ( s0, 1)= s1, δ ( s1, 0)= s3, δ ( s1, 1)= s0, δ ( s2, 0)= s0, δ ( s2, 1)= s3, δ ( s3, 0)= s1, δ ( s3, 1)= s2 vµ ®å thÞ ®îc m« t¶ nh sau: s 0

1 1

s 1

Bé m«n khoa häc m¸y tÝnh - HVKTQS s

s

2

3

18

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

0 0

0

0

1 1 VÝ dô 2. Ta xÐt automat sau: M=( {X, S, δ , s0,{s3}) trong ®ã X={0,1}, S={s0, s1, s2, s3}, δ ( s0, 0)= s2, δ ( s0, 1)= s1, δ ( s1, 0)= s2 δ ( s1, 1)= s3, δ ( s2, 0)= s3, δ ( s2, 1)= s1, δ ( s3, 0)= s3, δ ( s3, 1)= s3 vµ ®å ®å thÞ cã d¹ng sau: s 1

1

1

s 1

s

0 1

0

0

s

1,0

3

0

2

b. Dïng hµm chuyÓn. NÕu dïng ph¬ng ph¸p b¶ng ta cã b¶ng sau: S0 S1 S2 S3

0 S2 S3 S0 S1

1 S1 S0 S3 S2

$2. Automat h÷u h¹n ®o¸n nhËn ng«n ng÷ chÝnh quy. 2.1. Automat h÷u h¹n a. §Þnh nghÜa. Víi Automat h÷u h¹n M=( X, S,δ ,s0, F) trong ®ã: X - TËp h÷u h¹n c¸c ký hiÖu vµo S - TËp tr¹ng th¸i s0 - Tr¹ng th¸i ®Çu F - TËp tr¹ng th¸i kÕt thóc

Bé m«n khoa häc m¸y tÝnh - HVKTQS

19

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

δ

- ¸nh x¹ tõ XxS→S gäi lµ hµm chuyÓn tr¹ng th¸i, trong trêng hîp

nµy Automat gäi lµ automat ®¬n ®Þnh. NÕu δ : XxS→2S khi ®ã M gäi lµ automat ®a ®Þnh. b. M« t¶ ho¹t ®éng cña Automat. Ta cã thÓ m« t¶ c¸c bíc lµm viÖc cña Automat h÷u h¹n nh sau: Khi cho x©u x1 x2… xn =w∈X*, ®Çu tiªn m¸y ë tr¹ng th¸i s0 vµ ®Çu ®äc nh×n vµo « cã ký hiÖu x1. TiÕp theo m¸y tõ tr¹ng th¸i s0 sang s1=δ (s0,x1) vµ ®Çu ®äc dÞch sang x2, sau ®ã tiÕp tôc dÞch

chuyÓn

tõ

tr¹ng

th¸i

s1

sang

tr¹ng

th¸i

míi

s 2=

δ (s1,x2)=δ (δ (s0,x1),x2),… , cho ®Õn khi ®¹t ®Õn tr¹ng th¸i sn=δ (sn-1,xn)= δ (δ (sn-2xn -1),xn) == δ (δ (δ (sn-3,xn -2),xn-1),xn)=… δ

(δ (…(δ (s0,x1),x2),x3)…,xn):= δ (s0,x1,x1,…, xn):= δ (s0,w). Qu¸

tr×nh ®ã ®îc m« t¶ nh sau: X©u vµo w= x1

x2

s0

s1

x3 … xn-1 s2……

xn sn-1

sn

c. Automat ®o¸n nhËn x©u. Ta nãi automat ®o¸n nhËn ®îc x©u w nÕu sn∈F, trêng hîp ngîc l¹i ta nãi automat kh«ng ®o¸n nhËn ®îc x©u w. d. Ng«n ng÷ ®o¸n nhËn bëi automat. TËp T(M):={w ∈X*: δ (s0,w) ∈F} gäi lµ ng«n ng÷ ®îc ®o¸n nhËn bëi Automat M. TËp tr¹ng th¸i S trong qu¸ tr×nh tÝnh to¸n lµ h÷u h¹n nªn M ®îc gäi lµ automat h÷u h¹n.

2.2 C¸c ph¬ng ph¸p biÓu diÔn Automat a. Ph¬ng ph¸p cho b¶ng chuyÓn. Ta x©y dùng b¶ng nh sau: 1. Mét cét liÖt kª c¸c tr¹ng th¸i cña tËp S.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

20

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

2. Cét liÒn kÒ liÖt kª gi¸ trÞ cña hµm chuyÓn t¬ng øng víi tr¹ng th¸i vµ ký tù vµo. Tr¹ng

Ký tù vµo

th¸i s0 s1

x1 x2 x3 ….. δ (s0,x1) δ (s0,x2) δ (s0,x3)

xj ……

δ (s0,xn) δ (s1,x1) δ (s1,x2) δ (s1,x3) δ (s1,xn) .

sk

.

.

xn δ (s0,xj) δ (s1,xj)

.

δ (sk,x1) δ (sk,x2) δ (sk,x3)

δ (sk,xj)

δ (sk,xn) VÝ dô1. Cho automat ®¬n ®Þnh sau:M=(X,S,s0,δ ,F) trong ®ã X={0,1}, S={s0, s1, s2, s3}, F={ s0}. Hµm chuyÓn cã d¹ng sau: Tr¹ng

Ký tù vµo

th¸i 0 s0 s2 s1 s3 s2 s0 s3 s1 Cho x©u vµo w=110101. Khi ®ã δ (s0,1)=s1,

δ (s1,1)=s0,

1 s1 s0 s3 s2

δ (s0,0)=s2,

δ (s2,1)=s3,

δ (s3,0)=s1,

δ (s1,1)=s0. §iÒu nµy chøng tá Automat M ®o¸n nhËn x©u w=110101. D·y tr¹ng th¸i cña M khi cho x©u vµo w= 110101 ®îc biÓu diÔn nh sau: w= s0

1

1 s1

0 s0

1 s2

0

1 s3

s1

Bé m«n khoa häc m¸y tÝnh - HVKTQS

s0 21

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

Cã thÓ biÓu diÔn qu¸ tr×nh trªn t¬ng ®¬ng víi diÔn ®¹t sau: δ (s0,110101)=

δ (δ (s0,1),10101)=

δ (s1,10101)=

δ (δ (s1,1),0101))= δ (δ (s0,0101))= δ (δ (s0,0),101)= δ (s2,101)= δ (δ (s2,1),01)= δ (s3,01)= δ (δ (s3,0),1)= δ (s1,1)=s0∈F. VÝ dô2. Cho automat ®¬n ®Þnh sau:M=(X,S,s0,F) trong ®ã X={0,1}, S={s0, s1, s2, s3}, F={ s3}. Hµm chuyÓn cã d¹ng sau: Tr¹ng

Ký tù vµo

th¸i 0 s0 s1 s1 s3 s2 s0 s3 s3 Cho x©u vµo w=10110. Khi ®ã

1 s2 s0 s3 s3

δ (s0,1)=s2, δ (s2,0)=s0, δ (s0,1)=s2, δ (s2,1)=s3, δ (s3,0)=s3. D·y tr¹ng th¸i cña M khi cho x©u vµo w= 10110 ®îc biÓu diÔn nh sau: w= s0

1

0 s2

1 s0

1 s2

0 s3

s3

b. Ph¬ng ph¸p cho Automat b»ng ®å thÞ chuyÓn. Dïng ®å thÞ cã híng ®Ó m« t¶ hµm chuyÓn theo nguyªn t¾c sau: - Mçi tr¹ng th¸i s lµ mét ®Ønh cña ®å thÞ - NÕu a ∈X vµ tõ tr¹ng th¸i si chuyÓn sang tr¹ng th¸i sj=δ (si,a) th× sÏ cã mét cung cã híng tõ si sang ®Ønh sj vµ trªn cung ®ã ®îc g¸n nh·n a. - NÕu δ (si,a)={sj1, sj2 , sj3,…, sjk} ®èi víi automat kh«ng ®¬n ®Þnh tõ si sang {sj1, sj2 , sj3,…, sjk } cã k cung g¸n cïng mét nh·n a.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

22

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

- §Ønh vµo cña ®å thÞ chuyÓn lµ ®Ønh øng víi tr¹ng th¸i ban ®Çu s0. C¸c ®Ønh cã tr¹ng th¸i kÕt thóc ®îc khoanh trßn 2 lÇn hoÆc khoanh ®Ëm. VÝ dô 4. Cho M=(X,S,δ ,s0,F) trong ®ã X={0,1}, S={ s0, s1, s2, s3}, F={s0} Hµm chuyÓn ®îc m« t¶ díi biÓu ®å sau s 0

1

s

1

1

0 0

0

s

s

1

2

0

3

1 VÝ dô 3. Cho M=(X,S,s0,F) trong ®ã X={0,1}, S={ s0, s1, s2, s3}, F={s2, s4} Hµm chuyÓn ®îc m« t¶ díi biÓu ®å sau: 0,1

0,1

S0

1

s0 3

0

1

0

s 4

s 1

1

s 2

0,1

2.3. ThuËt to¸n m« pháng ®o¸n nhËn x©u vµo. a. ThuËt toµn m« pháng automat h÷u h¹n ®o¸n nhËn x©u vµo. Th«ng tin vµo: - X©u w, kÕt thóc bëi ký hiÖu hÕt file lµ eof.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

23

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

- Mét automat h÷u h¹n víi tr¹ng th¸i ®Çu lµ s0 vµ tËp tr¹ng th¸i kÕt thóc lµ F. Th«ng tin ra: - §óng nÕu M ®o¸n nhËn x©u w - Sai nÕu M kh«ng ®o¸n nhËn x©u w ThuËt to¸n: Begin u:=s0; c:= ký hiÖu tiÕp theo; while c<>eof do begin u:= δ (u,c); c:= ký tù tiÕp theo; end; if u in F return (true) else return (false); end; VÝ dô 4. Cho automat ®¬n ®Þnh sau:M=(X,S,s0, δ , F) trong ®ã X={0,1}, S={s0, s1, s2, s3}, F={ s2, s4}. Hµm chuyÓn cã d¹ng sau:

Tr¹ng th¸i s0 s1 s2 s3 s4

Ký tù vµo 0 {s0, s3} e s2 s4 s4

1 {s0, s1} s2 s2 e s3

Bé m«n khoa häc m¸y tÝnh - HVKTQS

24

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

Cho x©u vµo w=w1 w2…wk . §èi víi automat kh«ng ®¬n ®Þnh trªn th× hµm chuyÓn tr¹ng δ khi m¸y ë trang th¸i s vµ tÝn hiÖu vµo lµ a ®îc δ (s,a) ⊆ S V× vËy xuÊt hiÖn t×nh tr¹ng rÏ nh¸nh, ta x©y dùng c©y ®o¸n nhËn x©u nh sau: - Gèc lµ s0. - C¸c ®Ønh con cña gèc s0 lµ c¸c tr¹ng th¸i trong δ (s0,w1) trong ®ã w1 lµ ký tù ®Çu tiªn cña x©u w. - §èi víi ®Ønh s* ⊆ δ (s0,w1) ta x©y dùng c¸c ®Ønh con cña nã lµ c¸c ®Ønh thuéc tËp δ (s*,w2) vµ cø tiÕp tôc cho ®Õn ký tù cuèi cïng cña x©u. - Trong c©y nµy nÕu cã mét ®êng ®i tõ s0 ®Õn mét l¸ chøa tr¹ng th¸i kÕt thóc th× ta nãi m¸y M ®o¸n nhËn ®îc x©u vµo ®ang xÐt, ngîc l¹i ta nãi M kh«ng ®o¸n nhËn ®îc x©u vµo ®ã. Víi x©u vµo cã d¹ng w=01001 m¸y M cã c©y ®o¸n nhËn ®i tõ s0 ®Õn s4 ⊆ F nªn m¸y M ®o¸n nhËn x©u trªn. C©y cã d¹ng sau:

s

0

0

S

s 0

3

1

1

1

s 0

s

0

0

S

0 0

1

s

0

s

0

0

3

0

Bé m«n khoa häc m¸y tÝnh - HVKTQS

25

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat S

1 s 0

1

3

1

1

s

s 4

s

1

4

2.4. Sù t¬ng ®¬ng gi÷a Automat ®¬n ®Þnh vµ ®a ®Þnh. a. §Þnh lý 2.1. Líp ng«n ng÷ ®o¸n nhËn bëi autom¸t ®¬n ®Þnh trïng víi líp ng«n ng÷ ®o¸n nhËn ®îc bëi automat kh«ng ®¬n ®Þnh. Chøng minh. 1. Theo ®Þnh nghÜa automat ®¬n ®Þnh vµ kh«ng ®¬n ®Þnh th× líp ng«n ng÷ ®o¸n nhËn ®o¸n nhËn ®îc bëi ®¬n ®Þnh n»m trong líp ng«n ng÷ ®o¸n nhËn ®îc bëi automat kh«ng ®¬n ®Þnh. 2. Ta chøng minh bao hµm thøc ngîc l¹i. Gi¶ sö M=(X,S,s0, δ , F) lµ automat ®a ®Þnh, ta x©y dùng automat ®¬n ®Þnh N=(X’,S’,q0, δ ’, F’) nh sau: - X’: = X - S’ : = 2S={U: ∀U ⊆S} - q0= {s0} - F’:={U ⊆S : U∩F≠∅} -

δ ’: S’xX’

S’ nh sau: ∀U⊆ S ∀x∈X δ ’(U,x):=∪ s∈Uδ (s,x).

Víi c¸ch x©y dùng trªn th× râ rµng N lµ automat ®¬n ®Þnh. Ta ph¶i chøng minh L(M) ⊆ L(N) ThËt vËy, gi¶ sö w ∈L(M) Theo ®Þnh nghÜa x©u ®o¸n nhËn ®îc th×: X©u vµo

w= x1

x2

x3 … xn-1

xn

Bé m«n khoa häc m¸y tÝnh - HVKTQS

26

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

s0 Râ

rµng

s1

s1∈ δ (s0,x1);

s2……

sn ∈F

sn-1

s2∈ δ (δ (s0,x1),x2);

si∈ δ (δ (…δ

(s0,x1),x2),x3)..),xi); §Æt chän U0 ={ s0}=q0, Ui = δ (δ (…δ (s0,x1),x2),x3)..),xi). Khi ®ã ta cã: U1=δ (δ (s0,x1)= ∪ s∈u0δ (s,x1)= δ ’(U0,x1), U2= ∪ s∈u1δ (s,x2)= δ ’(U1,x2) Ui= ∪ s∈ui-1δ (s,xi)= δ ’(Ui-1,xi) si ∈ Ui vµ sn ∈F (i=1..n) V× sn ∈Un vµ sn ∈F nªn Un∩F≠∅ nªn theo ®Þnh nghÜa F’ suy ra Un ∈F’ Theo nh÷ng kÕt luËn trªn ®Þnh nghÜa hµm δ ’ ta sÏ cã: w= x1

x2

{s 0}

x3 … U1

xn-1

U2……

xn Un-1

Un

∈F’ §iÒu nµy cã nghÜa lµ w ∈ L(M). §Þnh lý ®îc chøng minh. VÝ dô 1. Cho automat kh«ng ®¬n ®Þnh N=(X, S, s0, δ , F) víi X={a,b}, S={s0, s1}, F={s1} hµm chuyÓn δ S xX

Tr¹ng th¸i s0 s1

2S cho nh sau:

Ký tù vµo a {s0, s1} ∅

b s1 {s0, s1}

Khi ®ã automat t¬ng ®¬ng víi automat trªn cã d¹ng sau:

Bé m«n khoa häc m¸y tÝnh - HVKTQS

27

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

M=(X’, S’, q2, δ ’, F’) víi X’=X={a,b}, S’={ q1, q2, q3, q4} ë ®©y q1=∅, q2={s0}, q3={s1}, q4={ s0, s1}, cßn F’={q3, q4}

Tr¹ng

Ký tù vµo

th¸i q1 q2 q3 Q4

a ∅ q4 ∅ q4

b ∅ q3 q4 q4

Ta cã L(N)=L(M). VÝ dô 2. XÐt automat kh«ng ®¬n ®Þnh sau: 0

s

1

s

0

0

s

1

2

1

Hµm chuyÓn cã d¹ng sau:

Tr¹ng th¸i s0 s1 S2

Ký tù vµo 0 {s0, s1} ∅ ∅

1 ∅ s2 s2

Hµm chuyÓn cña qu¸ tr×nh ®¬n ®Þnh ho¸ ®îc x¸c ®Þnh nh sau:

Tr¹ng th¸i {s0} {s1}

Ký tù vµo 0 {s0, s1} ∅

1 ∅ {s2}

Bé m«n khoa häc m¸y tÝnh - HVKTQS

28

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

{s2} {s0,s1} {s0,s2} {s1,s2} {s0,s1,s2}

∅ {s0,s1} {s0,s1} ∅ {s0,s1}

{s2} {s2} {s2} {s2} {s2}

Nh vËy Automat ®¬n ®Þnh cã d¹ng: {s1} 0 0

{s0}

1

1 1

{s0,s1}

{s2}

0 1

1

{s0,s1,s2}

{s1,s2}

Ng«n ng÷ ®o¸n nhËn ®îc cña 2 Automat trªn ®Òu lµ L(G)={0k1m,m,k>=1,m }.

$3. Sù liªn hÖ Automat-Ng«n ng÷ chÝnh quy, Quan hÖ t¬ng ®¬ng-Automat h÷u h¹n. 3.1. Automat h÷u h¹n vµ ng«n ng÷ chÝnh quy. a. §Þnh lý 2.2.

NÕu G=(N,T,s0,P) lµ v¨n ph¹m lo¹i 3 th× tån t¹i

Automat h÷u h¹n M sao cho L(G)=L(M) Chøng minh: Kh«ng gi¶m tÝnh tæng qu¸t ta coi G lµ v¨n ph¹m tuyÕn tÝnh tr¸i tøc lµ v¨n ph¹m cã luËt sinh d¹ng A

aB, A

a,

ta x©y dùng M =(X, S, q0, δ , F) nh sau: - LÊy X:=T; q0:=s0; S:=N∪{A}, A lµ tr¹ng th¸i bæ sung cha cã trong N - F:={s0, A} nÕu s0

e lµ quy t¾c trong P,

- F:={ A} nÕu

e kh«ng cã trong P.

s0

- Ngoµi ra nÕu s0

e lµ quy t¾c cña P th× kh«ng ¶nh hëng ®Õn kÕt

qu¶, ta gi¶ thiÕt s0 kh«ng xuÊt hiÖn trong c¸c luËt sinh kh¸c cña P.

X©y dùng hµm chuyÓn nh sau

Bé m«n khoa häc m¸y tÝnh - HVKTQS

29

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

-δ (B,a) chøa C ⇔B

aC∈P

-δ (B,a) chøa A ⇔B

a∈P ∀B,C∈N

-δ (A,a):=∅ cho mäi a∈T. Ta chøng tá L(M)=L(G). LÊy x∈L(G), gi¶ sö x=x1…xn khi ®ã ta cã dÉn xuÊt sau trong G nh sau: s0

x1A1

(B

xn )

x1x2A2

x1x2x3A3

… x1x2x3…xn-1B

x1…xn

Víi c¸ch x©y dùng hµm chuyÓn ta cã: -δ (s0,x1)⊇ A1, δ (A1,x2)⊇ A2, … ,δ (An-2,xn-1)⊇ B, δ (B,xn)⊇ A∈F, v× A thuéc F nªn suy ra L(G) ⊆ L(M). Ngîc l¹i gi¶ sö x=x1…xn∈L(M) nghÜa lµ δ (q0,x)= δ (q0, x1…xn )= δ (δ …δ (δ (q0, x1),x2),…,xn)∈F= {A,s0} {A} suy ra tån t¹i d·y sao cho khi ®ã ta cã dÉn xuÊt sau trong G nh sau: s0 ,A1 , A2, …, An-1, B sao cho δ (s0,x1)⊇ A1, δ (A1,x2)⊇ A2, … ,δ (An-2,xn-1)⊇ An-1, δ (An-1,xn)⊇ B. Theo c¸ch x©y dùng δ trong M th× B=A hoÆc B=s0 - NÕu nh B=A, khi ®ã tõ

δ (An-1,xn) ⊇ B =A

nghÜa hµm chuyÓn suy ra An-1

khi ®ã theo ®Þnh

xn∈P.

- NÕu B=s0 suy ra trong G cã luËt sinh s0

e

Theo c¸ch x©y dùng trªn trong P cña G ph¶i cã c¸c quy t¾c sau: s0

x1 A1

A1

x 2 A2

Bé m«n khoa häc m¸y tÝnh - HVKTQS

30

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

A2

x 3 A3

…………… An-2

xn-1An-1

An-1

xn A.

A

xn

HoÆc luËt sinh s0

e

§iÒu nµy cã nghÜa lµ tån t¹i s0*

x, vËy nªn x∈L(G).

b. C¸c vÝ dô. XÐt V¨n ph¹m G=({s0,B,C},{0,1},s0, P) trong ®ã P gåm 1. s0

0B

2. C

1C

3. s0

1C

4. C

1

5. B

0B

6. C

0

7. B

0s0

8. s0

0

Automat ®o¸n nhËn ng«n ng÷ ®îc x©y dùng nh sau: M=({0,1},{s0,A,B,C},s0,{A}), Dùa vµo hµm chuyÓn ta cã Automat sau: s 0

0

0

A C

0

B 0

1

0,1

C

1

c. §Þnh lý 2.3. Cho Automat M =(X, S, q0, δ , F) khi ®ã tån t¹i v¨n ph¹m chÝnh quy G sao cho L(M)=L(G). Chøng minh. Kh«ng gi¶m tæng qu¸t ta coi auotmt M =(X, S, q0, δ , F) lµ ®¬n ®Þnh. Ta x©y dùng G nh sau: - N:=S - T:=X - s0:=q0

Bé m«n khoa häc m¸y tÝnh - HVKTQS

31

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

- TËp quy t¾c P ®îc x¸c lËp nh sau: aC nÕu δ (B,a)=C

B

a nÕu δ (B,a)=C vµ C∈F

B

Ta nhËn they râ rµng G lµ v¨n ph¹m lo¹i 3. Ta chøng minh L(G)=L(M) - LÊy x∈L(G), gi¶ sö x=x1…xn, khi ®ã ta cã dÉn xuÊt sau trong G nh sau: s0

x1A1

x1x2A2

x1x2x3A3

… x1x2x3…xn-1An-1

x1…xn

Víi c¸ch x©y dùng hµm chuyÓn ta cã: -δ (s0,x1) = A1, δ (A1,x2)= A2, … ,δ (An-2,xn-1)= An-1, δ (An-1,xn)= An∈F, Mµ δ (s0,x)= δ (δ (...(δ (s0,x1),x2), ...,xn)=An∈F Suy ra x ∈ L(M). - Ngîc l¹i gi¶ sö x=x1…xn∈L(M) nghÜa lµ δ (q0,x)= δ (q0, x1…xn )= δ (δ …δ (δ (q0, x1),x2),…,xn)∈F suy ra tån t¹i d·y sao cho khi ®ã ta cã dÉn xuÊt sau trong G nh sau: s0 ,A1 , A2, …, An-1, An sao cho δ (s0,x1)= A1, δ (A1,x2)= A2, … ,δ (An-2,xn-1)= An-1, δ (An-1,xn)=An ∈F Khi ®ã theo c¸ch x©y dùng trªn th× δ (s0,x1)= A1, δ (A1,x2)= A2, … ,δ (An-2,xn-1)= An-1, δ (An-1,xn)=An ⇔s0 An

x1A1, A1

x2A2, A2

x3A3 ,…, An-1

xn. VËy nªn tån t¹i d·y dÉn xuÊt s0*

xn-1An vµ v× An∈F nªn x, nghÜa lµ x∈L(G).

§Þnh lý ®îc chøng minh.

3.3 Quan hÖ t¬ng ®¬ng a. Quan hÖ 2 ng«i. Cho tËp S ta nãi trªn S cã mét quan hÖ 2 ng«i R nÕu nÕu cÆp phÇn tö (x,y) x¸c lËp mèi quan hÖ víi nhau th«ng qua R, ký hiÖu xRy. Hay nãi c¸ch kh¸c R lµ tËp con cña SxS. c. Quan hÖ t¬ng ®¬ng. Quan hÖ 2 ng«i R gäi lµ t¬ng ®¬ng nÕu tho¶

Bé m«n khoa häc m¸y tÝnh - HVKTQS

32

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

c¸c ®iÒu kiÖn sau: 1. Víi mäi x ∈S ta cã xRx(ph¶n x¹) 2. Víi mäi x,y∈S xRy kÐo theo yRx(®èi xøng) 3. Víi mäi x,y,z∈S xRy, yRz kÐo theo xRz(b¾c cÇu) d. Líp t¬ng ®¬ng. Cho R lµ quan hÖ 2 ng«i trªn S gäi tËp: [x]:={y: xRy} líp t¬ng ®¬ng øng víi phÇn tö x, ta dÔ dµng nhËn thÊy c¸c líp t¬ng ®¬ng hoÆc trïng nhau hoÆc rêi nhau. e. §Þnh lý vÒ quan hÖ t¬ng ®¬ng vµ ph©n ho¹ch. R lµ quan hÖ t¬ng ®¬ng trªn S khi vµ chØ khi tån t¹i mét ph©n ho¹ch cña S ( Hä tËp con {Si} gäi lµ ph©n ho¹ch cña S nÕu USi=S vµ Si∩Sj=∅,i ≠ j) §Ó minh ho¹ cho kh¼ng ®Þnh trªn ta xÐt vÝ dô sau: Cho N:={1,2,…} tËp c¸c sè nguyªn vµ quan hÖ R sau: Víi mäi (i,j):ij  chia hÕt cho 5. DÔ dµng nhËn thÊy ®ã lµ quan hÖ t¬ng ®¬ng vµ N ®îc ph©n ho¹ch thµnh 3 líp [1]={1, 6, 11,…}; [2]={2,7,12, …}; [3]={3,8,13,…}. f. ChØ sè cña quan hÖ t¬ng ®¬ng. Cho R lµ quan hÖ t¬ng ®¬ng trªn S gäi sè c¸c líp t¬ng ®¬ng do R do sinh ra trªn S lµ chØ sè cña quan hÖ t¬ng ®¬ng.

3.4. Quan hÖ t¬ng ®¬ng vµ Automat h÷u h¹n a. Quan hÖ t¬ng ®¬ng trªn ( X*,M). Cho automat M=(X,S,q0, δ ,F) quan hÖ RM x¸c lËp trªn X* nh sau: x, y ∈X*, xRy⇔δ (q0, x)= δ (q0, y). DÔ dµng nhËn thÊy R lµ quan hÖ t¬ng ®¬ng trªn X*. b. Quan hÖ t¬ng ®¬ng bÊt biÕn ph¶i. Quan hÖ t¬ng ®¬ng trªn X* gäi

lµ bÊt biÕn ph¶i nÕu xRy kÐo theo xzRyz víi mäi z∈X*.

V× δ (q0, xz )= δ (δ (q0, x),z)= δ (δ (q0, y),z)= δ (q0, yz) nªn RM lµ quan hÖ bÊt biÕn ph¶i.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

33

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

c. §Þnh lý 2.4.(VÒ ng«n ng÷ ®o¸n nhËn bëi Automat h÷u h¹n.) C¸c ®iÒu kiÖn sau lµ t¬ng ®¬ng: 1. TËp L ⊆X* ®o¸n nhËn bëi automat h÷u h¹n. 2. TËp L ⊆X* lµ hîp cña c¸c líp t¬ng ®¬ng sinh ra bëi quan hÖ t¬ng ®¬ng bÊt biÕn ph¶i cã chØ sè h÷u h¹n. 3. R lµ quan hÖ t¬ng ®¬ng x¸c ®Þnh nh sau xRy: NÕu xz ∈L th× yz ∈L víi mäi z∈X* khi ®ã R cã chØ sè h÷u h¹n. Chøng minh. 1⇒2. Gi¶ sö L ®o¸n nhËn automat h÷u h¹n M=(X, S, q0, δ , F). Gäi R’ lµ quan hÖ x¸c ®Þnh nh sau: xR’y⇔δ (q0, x)= δ (q0, y) khi ®ã dÔ dµng thÊy: - R’ lµ quan hÖ t¬ng ®¬ng bÊt biÕn ph¶i trªn X*. - L:=L(M)={x: δ (q0, x) ∈F}=∪{x: δ (q0, x)=s, s∈F } nªn L cã tèi ®a lµ F líp tong ®¬ng, do ®ã chØ sè cña R’ lµ h÷u h¹n. 2⇒3. Gi¶ sö r»ng: - R’ lµ quan hÖ t¬ng ®¬ng bÊt biÕn ph¶i cã chØ sè h÷u h¹n - L lµ hîp c¸c líp t¬ng ®¬ng sinh bëi R’. Do tÝnh bÊt biÕn ph¶i nªn ta cã: xR’y th× xzR’yz, V× c¸c líp t¬ng ®¬ng hoÆc trïng nhau hoÆc rêi nhau mµ yz∈[xz] nªn suy ra xz∈L⇔yz∈L, ®iÒu nµy theo 3. nghÜa lµ xRy, vËy nªn xR’y suy ra xRy nghÜa lµ líp t¬ng ®¬ng cña quan hÖ R’ chøa mét líp t¬ng ®¬ng nµo ®ã cña quan hÖ R, v× R’ cã chØ sè h÷u h¹n nªn R còng cã chØ sè h÷u h¹n. 3⇒1. Gi¶ thö R lµ quan hÖ t¬ng ®¬ng theo 3 lµ xRy⇔ NÕu xz∈L th× yz∈L ta chøng minh L ®o¸n nhËn bëi automat h÷u h¹n. Gi¶ sö xRy khi ®ã theo gi¶ thiÕt víi w,z ∈X* khi ®ã: - xwz∈L⇔ ywz∈L nghÜa lµ xwRyw suy ra R lµ quan hÖ t¬ng ®¬ng bÊt biÕn ph¶i. - Gäi S’ tËp c¸c líp t¬ng ®¬ng cña R, khi ®ã S’ cã chØ sè h÷u h¹n.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

34

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

Ta x©y dùng atomat sau M’=(X, S’, q0, δ , F’) trong ®ã: - S’:={[x] : x ∈X*}; F’:= {[x] : x ∈L} 2. q’0={e} ; δ ’([x],w):=[xw] Víi automat x©y dùng nh trªn th× L(M’)=L v× r»ng δ ’(q’0,w):=[w] vµ w∈L(M’) khi vµ chØ khi [w] ⊆F’.

3.5. Bæ sung mét sè tÝnh chÊt cña ng«n ng÷ chÝnh quy. Do trong v¨n ph¹m chÝnh quy c¸c luËt sinh t¬ng ®èi ®¬n gi¶n do ®ã ngoµi c¸c tÝnh chÊt chung ng«n ng÷ chÝnh quy cßn cã thªm mét sè tÝnh chÊt ®Æc thï trong môc nµy ta sÏ bæ sung mét sè tÝnh chÊt ®ã a. TC1. Ng«n ng÷ chÝnh quy kÝn víi phÐp hîp (®· chøng minh) b. TC2. Ng«n ng÷ chÝnh quy kÝn víi phÐp lÊy phÇn bï Chøng minh. Gi¶ sö N=(X, S, q0, δ , F) ®o¸n nhËn tËp L(N) , M:=( X, S, q0, δ , F’) trong ®ã F’:=S\F. PhÇn bï cña L(N) lµ R(N) ta chøng minh r»ng R(N) còng lµ ng«n ng÷ chÝnh quy. Gi¶ sö w ∈R(N) ⇔ w ∈X*\L(N) nghÜa lµ δ (q0,w) ∈F’ hay δ (q0,w) ∈S vµ δ (q0,w) ∉F do ®ã w ®îc ®o¸n nhËn bëi Automat M=(X,S, δ ,q0,S\F) vËy nªn w ∈L(M). Suy ra R(N)=L(M) mµ L(M) lµ ng«n ng÷ chinh quy nªn suy ra R(N) chÝnh quy. TC3. TÊt c¶ c¸c x©u h÷u h¹n ®Òu lµ ng«n ng÷ lo¹i 3. Chøng minh. Ta xÐt x©u w=a1 a1…an. Ta x©y dùng automat sau M:=({ a1,…,an},{q0,q1,…,qn,p},δ ,q0,{qn}) trong ®ã δ ( qi-1,ai):=qi (i=1,n); δ ( qi-1,a):=p

a<>ai(i=1,,n), δ ( qn,a):=

δ ( p,ai)=p víi mäi a

Bé m«n khoa häc m¸y tÝnh - HVKTQS

35

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

Ta dÔ dµng chøng minh automat trªn ®o¸n nhËn x©u w th«ng qua s¬ ®å sau:

q

q

1

2

q

q

a02

3

a1

a3 a

p

a

a

q n

a

nÕu w=e Ta cã thÓ xÐt automat sau: M:=(X,{q0,p},δ ,{q0}) trong ®ã δ ( q0,e):=q0 ; δ ( q0,a):=p víi mäi a ∈X c. TC4. Líp c¸c ng«n ng÷ chÝnh quy ®ãng ®èi víi phÐp nh©n. Gi¶ sö M1 =(X1, S1, q1, δ 1, F1) vµ M2 =(X2, S2, q2, δ 2, F2) ®o¸n nhËn L1 vµ L2 t¬ng øng, ta cÇn chøng minh L1L2:={uv, u∈L1, v∈L2} lµ ng«n ng÷ chÝnh quy, muèn vËy ta x©y dùng automat h÷u h¹n ®o¸nnhËn nã. Kh«ng gi¶m tæng qu¸t ta coi S1 ∩ S2=∅, X1 = X2=X. Ta x©y dùng automat M:=(X, S, q1, δ ,F) nh sau: - S:= S1 ∪ S2 - F:=F2 nÕu e kh«ng thuéc L2 ngîc l¹i F:=F1 ∪ F2 - Hµm chuyÓn cã d¹ng δ (q,a):={ δ 1(q,a)} víi q∈S1\F1, a∈X δ (q,a):={ δ 1(q,a), δ 2(q,a)} víi q∈F1, a∈X δ (q,e):={q2} víi q∈F1 δ (q,a):={ δ 2(q,a)} víi q∈S2, a∈X Gäi L(M) ng«n ng÷ ®o¸n nhËn M NhËn thÊy r»ng víi w∈L(M)⇔ δ (q1,w) ∈F. - NÕu e kh«ng thuéc L2 th× δ (q1,w) ∈F2 nghÜa lµ ta cã víi x©u vµo w= x1

x2

x3 …

xn-1

xn

Bé m«n khoa häc m¸y tÝnh - HVKTQS

36

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

q1

δ (q1,x1)

δ (q1,x1x2)

….

δ (q1,x1…xn) ∩ F2≠∅

Gi¶ sö r»ng tån t¹i chØ sè j lín nhÊt sao cho pj=δ (q1,x1…xj-1) ∈F1, khi ®ã ta cã: x1…xj-1 ∈L1 , δ (pj ,xj)={δ 1(pj,,xj), δ 2(pj,,xj) }, ta cã δ 2(pj,,e)=q2 ta chän ®êng ®i theo hµm δ 2(q2,,xj+1),…ta sÏ cã e

xj+1

xj+2 …

xn-1

pj

q2

δ (q2,xj+1)

….

xn δ (q2,xj+1…xn) ∩ F2≠∅

nghÜa lµ xj+1 xj+2 …xn-1 xn∈L2 v× e lµ ký tù trèng ta cã thÓ lîc bá. - Trêng hîp e∈L2 khi ®ã F=F1∪F2. Gi¶ sö w∈L(M) ⇔ δ (q1,w) ∈F1 hoÆc δ (q1,w) ∈F2. Gi¶ sö r»ng δ (q1,w) ∈F1 suy ra w ∈L1 nÕu kh«ng gièng trêng hîp ®Çu. Ngîc l¹i, gi¶ sö r»ng uv∈L1L2 ⇔ u∈L1, v∈L2, theo ®Þnh nghÜa th× δ 1(q1,u) ∈F1 vµ δ 2(q2,v) ∈F2 nghÜa lµ

u= u1 q1 v= v1 q2

u2 …

uk-1

p1

pk-2

v2 …

vl-1

pk+2

uk pk-1

pk∈F1(theo δ 1)

vl pk+l

pk+l+1∈F2 (theo δ 2)

MÆt kh¸c bæ sung thªm δ (pk,e)=q2 ta sÏ nhËn ®îc uev∈L(M) d. TC5. Líp c¸c ng«n ng÷ chÝnh quy ®ãng víi phÐp lÊy bao ®ãng. Chøng minh. M =(X, S, q0, δ , F) lµ automat ®o¸n nhËn L, gäi L*=∪Ln, trong ®ã Li: =Li-1L víi L0={e}. Ta x©y dùng Automat M’=(X,S’,q’0,δ ’, F) nh sau:

Bé m«n khoa häc m¸y tÝnh - HVKTQS

37

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

S’:=S∪{q’0}, F’:=F∪{q’0}, trong ®ã nÕu q0 ∈ F th× q’0:=q0; nÕu q0∉F th× chän q’0 kh¸c q0. Víi hµm chuyÓn cã d¹ng sau: - δ ’(q’0,a):={ δ (q0,a),q’0} nÕu δ (q0,a) ∈ F - δ ’(q’0,a):= {δ (q0’,a)} nÕu δ (q0,a) ∉F - δ ’(q,a):={ δ (q,a),q0} nÕu δ (q,a) ∈ F vµ q∈ S - δ ’(q,a):= {δ (q,a) } nÕu δ (q,a) ∉F, q∈ S Ta chøng minh L* ®o¸n nhËn bëi M’ Gi¶ sö x∈L*, khi ®ã hoÆc x=e hoÆc x=x1x2…xn víi xi ∈ L i=1…n. Ta cã δ ’(q’0,e):={ δ (q0,e),q’0}={q0,q’0} nÕu δ (q0,e) ∈ F δ ’(q’0,e):= δ (q’0,e)=q’0 nÕu δ (q0,e) ∉F. VËy nªn δ ’(q’0,e) ∈ F’, hay e∈L(M’). Gi¶ sö xi ∈L nªn δ (q0,xi) ∈ F, mµ δ ’(q’0,xi):={ δ (q0,xi), q’0} v× δ (q0,xi) ∈ F nªn δ ’(q’0,xi) ∈F’ vËy nªn x∈L(M’). Ngîc l¹i, gi¶ sö x=x1x2…xn∈L(M’)⇔δ ’(q’0,x)∈F’⇔δ ’(q’0, x1x2…xn)∈F’ NghÜa lµ tån t¹i d·y tr¹ng th¸i q1, q2,…qn sao cho qi∈ δ ’(qi-1, xi), i=1..n. x= x1

x2 …

q’0

q1

xi qi-1

xn qn-1

qn∈F’ (1)

{δ (qi-1,xi), q0} nÕu δ (qi-1,xi) ∈ F vµ qi-1∈ S

Mµ qi∈ δ ’(qi-1, xi)=

δ (qi-1,xi)

nÕu δ (qi-1,xi) ∉ F vµ qi-1∈ S

Do ®ã víi mçi i=1…n th× δ ’(qi-1, xi) hoÆc chøa (qi = q0 vµ δ (qi-1, xi) ∈F) hoÆc (qi=δ (qi-1, xi) vµ δ (qi-1, xi) ∉F) nghÜa lµ xi∈L ®iÒu nµy cã nghÜa lµ x ∈L*( chó ý ë vÕ thø 2 kh«ng xÈy ra v× qn = δ (qn-1, xn) ∈F).

Bé m«n khoa häc m¸y tÝnh - HVKTQS

38

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

e. TC6. Líp c¸c tËp ®o¸n nhËn ®îc bëi c¸c Automat h÷u h¹n lµ líp nhá nhÊt chøa tÊt c¶ c¸c tËp h÷u h¹n vµ ®ãng víi c¸c phÐp to¸n hîp, nh©n, ghÐp, vµ lÊy bao ®ãng.

$4. Ng«n ng÷ chÝnh quy vµ biÓu thøc chÝnh quy. 4.1. Ng«n ng÷ chÝnh quy. a. §Æt vÊn ®Ò. Trong môc nµy ta l¹i ®a ra mét c¸ch tiÕp cËn míi vÒ ng«n ng÷ chÝnh quy c¸c tiÕp cËn nµy nh»m kh¼ng ®Þnh líp ng«n ng÷ chÝnh quy lµ líp bÐ nhÊt. b. Ng«n ng÷ trªn b¶ng. Cho tËp X, tËp con E⊆X gäi lµ ng«n ng÷ trªn b¶ng X. Ta cã thÓ ®Þnh nghÜa c¸c phÐp to¸n trªn ng«n ng÷ tuy nhiªn chóng ta quan t©m ®Õn 3 phÐp to¸n hîp, giao,vµ lÆp. c. Ng«n ng÷ s¬ cÊp. Gi¶ xö X={x1, x2,…, xn} ta gäi ∅ vµ {xi} lµ c¸c ng«n ng÷ s¬ cÊp trªn X. d. Ng«n ng÷ chÝnh quy. -

C¸c ng«n ng÷ s¬ cÊp trªn X lµ chÝnh quy.

3. NÕu E, F lµ ng«n ng÷ chÝnh quy trªn X th× E∪F, EF, E+ lµ ng«n ng÷ chÝnh quy trªn b¶ng X -

Kh«ng cã ng«n ng÷ chÝnh quy nµo kh¸c ngoµi c¸c ng«n ng÷

chÝnh quy ®· ®îc ®Þnh nghÜa trªn.

4.2. BiÓu thøc chÝnh quy. a. §Þnh nghÜa. Trªn b¶ng X ta ®Þnh nghÜa biÓu thøc chÝnh quy nh sau: 1. ∅ lµ biÓu thøc chÝnh quy nã biÓu diÔn ng«n ng÷ rçng. 2. NÕu a∈X th× a lµ biÓu thøc chÝnh quy nã biÓu diÔn ng«n ng÷ {a}. 3. NÕu r ,s lµ 2 biÓu thøc chÝnh quy trªn X biÓu diÔn 2 ng«n ng÷ t¬ng øng R, S th× r∪s lµ biÓu thøc chÝnh quy biÓu diÔn ng«n ng÷ R ∪ R, S

Bé m«n khoa häc m¸y tÝnh - HVKTQS

39

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

r.s lµ biÓu thøc chÝnh quy biÓu diÔn ng«n ng÷ R.S r+ lµ biÓu thøc chÝnh quy biÓu diÔn ng«n ng÷ R+ b. C¸c ®Þnh lý. §Þnh lý 2.5. Mäi ng«n ng÷ chÝnh quy trªn b¶ng X ®Òu nhËn ®îc tõ c¸c ng«n ng÷ s¬ cÊp sau mét sè lÇn h÷u h¹n ¸p dông c¸c phÐp to¸n hîp, nh©n vµ lÆp. §Þnh lý 2.6. Mäi ng«n ng÷ trªn X lµ chÝnh quy khi vµ chØ khi nã biÓu diÔn biÓu thøc chÝnh quy. Chøng minh. Ta chøng minh ®iÒu nµy b»ng quy n¹p. Gi¶ sö E lµ mét ng«n ng÷ chÝnh quy trªn X vµ E≠∅ nÕu: E={xi} lµ ng«n ng÷ s¬ cÊp th× r=xi lµ biÓu thøc chÝnh quy t¬ng øng. E=E1∪E2 trong ®ã E1, E2 ng«n ng÷ chÝnh quy ®îc biÓu diÔn bëi c¸c biÓu thøc chÝnh quy r1, r2 t¬ng øng, khi ®ã theo ®Þnh nghÜa th× r1∪ r2 lµ chÝnh quy vµ biÓu diÔn E=E1∪E2 . C¸c trêng hîp cßn l¹i t¬ng tù. Ngîc l¹i, 2 trêng hîp ®Çu hiÓn nhiªn ng«n ng÷ ®îc nã biÓu diÔn lµ chÝnh quy. Gi¶ sö r»ng r1, r2 lµ 2 biÓu thøc chÝnh quy biÓu diÔn ng«n ng÷ chÝnh quy E1 vµ E2, ta chøng minh - r1∪ r2 lµ chÝnh quy vµ biÓu diÔn ng«n ng÷ E=E1∪E2. ThËt vËy r1∪ r2 lµ chÝnh quy do ®Þnh nghÜa biÓu thøc chÝnh quy vµ biÓu diÔn ng«n ng÷ E, cßn E lµ chÝnh quy do ®Þnh nghÜa ng«n ng÷ chÝnh quy. C¸c trêng hîp kh¸c t¬ng tù. c. Chó ý. - Mét ng«n ng÷ chÝnh quy lµ v« h¹n khi vµ chØ khi biÓu thøc chÝnh quy biÓu diÔn nã cã dÊu lÆp(+). - Líp tÊt c¶ c¸c ng«n ng÷ chÝnh quy trªn X lµ líp bÐ nhÊt chøa c¸c tËp h÷u h¹n vµ ®ãng ®èi víi c¸c phÐp to¸n hîp, nh©n vµ lÆp.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

40

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

d. ThuËt to¸n Thom s¬n. Bµi to¸n: Cho biÓu thøc chÝnh quy t×m automat kh«ng ®¬n ®Þnh ®o¸n nhËn ng«n ng÷ chÝnh quy tõ biÓu thøc chÝnh quy ®· cho.Tøc lµ: Vµo: Mét biÓu thøc chÝnh quy r trªn bé X. Ra :Mét automat N ®o¸n nhËn ng«n ng÷ L(r) Néi dung thuËt thuËt to¸n gåm c¸c bíc sau: - B1. §èi víi tõ rçng e x©y dùng automat kh«ng ®¬n ®Þnh ®o¸n nhËn tõ rçng sau: e

s 0

f

Víi s0 lµ tr¹ng th¸i ®Çu, cßn f lµ tr¹ng th¸i kÕt thóc. x

s

f

0

- B2. Víi x∈X, x©y dùng automat kh«ng ®¬n ®Þnh ®o¸n nhËn {x} nh sau: - B3. Gi¶ sö N(r) vµ N(s) lµ c¸c automat thµnh phÇn øng víi r vµ s ta x©y dùng c¸c automat sau cho: + Víi r ∪s cã automat ®o¸n nhËn N(r) ∪N(s) sau

e

N(s)

e

s

f

0

e

e N(r)

Bé m«n khoa häc m¸y tÝnh - HVKTQS

41

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

ë ®©y s0 lµ tr¹ng th¸i ban ®Çu, f lµ tr¹ng th¸i kÕt thóc cña N vµ N nhËn ®îc b»ng c¸ch tæ hîp 2 automat thµnh phÇn N(r) vµ N(s) theo s¬ ®å b¶ng chuyÓn trªn. +Víi r.s ta x©y dùng automat sau:

S

f

0

N(s)

N(r)

N nhËn ®îc tõ N(s) vµ N(r) b»ng c¸ch lÊy tr¹ng th¸i ®Çu cña N(s) lµm tr¹ng th¸i ®Çu cña N vµ tr¹ng th¸i kÕt thóc cña N(r) lµm tr¹ng th¸i kÕt thóc cña N vµ ®ång nhÊt tr¹ng th¸i kÕt thóc cña N(s) víi tr¹ng th¸i ®Çu cña N(r). +Víi r+ ta x©y dùng nh sau: e

S 0

f

e

e

e

N(r) ë ®©y s0 tr¹ng th¸i ®Çu, f tr¹ng th¸i kÕt thóc cña N. 2. T¸ch r thµnh c¸c r1,…,rk lµ c¸c biÓu thøc chÝnh quy thµnh phÇn. 3. ¸p dông c¸c B1, B2 ®Ó x©y dùng c¸c automat kh«ng ®¬n ®Þnh N1,…, Nk ®o¸n nhËn c¸c L(r1),…,L(rk) 4. Dïng B3 ®Ó x©y dùng L(r).

Bé m«n khoa häc m¸y tÝnh - HVKTQS

42

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

VÝ dô. Cho r=(a,b)*abb ¸p dông Thomson x©y dùng automat ®o¸n nhËn r. 1. Ký hiÖu r1=a,r2=b x©y dùng ©uotmt ®o¸n nhËn 2 ng«n ng÷ trªn s

as

2

3

s

s

4

5

b

2. X©y dùng r3=r1∪ r2 {(a,b)} e s

e

s

as

2

3

e

b

3. X©y dùng (r3)*

s

s

4

5

4. X©y dùng r4=(r3)*r1

e

s

1

6

5. X©y dùng r5=r4r2 6. X©y dùng r6=r5r2, cuèi cïng ta ®îc e s 2

s

es

0

1

b

e

a

s

e

3

s

s

4

5

s

s

6

7

s

e

8

s

e

9

s

a

b

b e

4.2. Automat vµ ng«n ng÷ chÝnh quy. a. Ng«n ng÷ trªn automat ®¬n ®Þnh. Cho M= (X, S, q0, δ , F) lµ automat ®¬n ®Þnh, gi¶ sö E∈X+, ta nãi ng«n ng÷ E chÊp nhËn ®îc bëi M nÕu ∀w∈E, δ (q0,w)∈F. Trong trêng hîp ng«n ng÷ E chÊp nhËn ®îc bëi M ta ký hiÖu δ (q0,E)∈F.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

43

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

Víi mçi automat M, gäi T(M):={E∈X+: δ (q0,E) ∈F}, râ rµng T(M) lµ tËp tÊt c¶ c¸c x©u ®o¸n nhËn bëi M. b. Ng«n ng÷ trªn automat kh«ng ®¬n ®Þnh. Cho M= (X, S, q0, δ , F) lµ automat ®a ®Þnh, gi¶ sö E∈X+, ta nãi ng«n ng÷ E chÊp nhËn ®îc bëi M nÕu ∀w∈E, δ (q0,w)∩F≠∅ . Trong trêng hîp ng«n ng÷ E chÊp nhËn ®îc bëi M ta ký hiÖu δ (q0,w)∩F≠∅ . Víi mçi automat M, gäi T(M):={E∈X+: δ (q0,w)∩F≠∅ }, râ rµng T(M) lµ tËp tÊt c¶ c¸c x©u ®o¸n nhËn bëi automat ®a ®Þnh M. c. §Þnh lý 2.7. Mäi ng«n ng÷ trªn b¶ng ch÷ c¸i X ®Òu biÓu diÔn ®îc bëi automat h÷u h¹n khi vµ chØ khi nã biÓu diÔn ®îc díi d¹ng automat h÷u h¹n kh«ng ®¬n ®Þnh. Chøng minh. Ng«n ng÷ biÓu diÔn ®îc trªn automat h÷u h¹n th× dï automat ®ã lµ ®¬n ®Þnh hay ®a ®Þnh ®Òu ®îc coi lµ automat ®¬n ®Þnh. Ngîc l¹i nÕu mét ng«n ng÷ biÓu diÔn b»ng automat h÷u h¹n kh«ng ®¬n ®Þnh th× sÏ tån t¹i automat ®¬n ®Þnh ®o¸n nhËn nã.

4.3. Automat h÷u h¹n lìng cùc. a. §Þnh nghÜa. Cho Cho M= (X, S, q0, δ , F) ta gäi lµ automat lìng cùc nÕu: - F chØ cã mét phÇn tö F={qr} qr≠ q0 - ∀q∈S, mäi x∈X, q0∉ δ (q,x) - Víi mäi x ∈X, δ (qr,x)=∅. Trong ®ã q0 vµ qr lµ tr¹ng th¸i ®Çu vµ tr¹ng th¸i kÕt thóc. Tõ ®Þnh nghÜa suy ra r»ng ®å thÞ biÓu diÔn automat lìng cùc lµ mét ®å thÞ lìng cùc, trong ®ã q0 lµ cùc vµo kh«ng cã cung vµo nã, cßn qr lµ cùc ra vµ kh«ng cã cung ®i ra tõ nã. q 0

b

q 1

q

b

q

1

1

Bé m«n khoa häc m¸y tÝnh - HVKTQS

q

q

q

q

2

3

2

3

44

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

a

b

b

a

b

b

b

b

H×nh 1 lµ automat kh«ng ®¬n ®Þnh vµ kh«ng lìng cùc. Cßn h×nh sau lµ ®¬n ®Þnh vµ lìng cùc. c. §Þnh lý 2.8. Mäi ng«n ng÷ trªn X biÓu diÔn ®îc bëi automat h÷u h¹n kh«ng ®¬n ®Þnh khi vµ chØ khi nã biÓu diÔn ®îc bëi automat lìng cùc. Chøng minh. Gi¶ sö E biÓu diÔn ®îc bëi automat kh«ng ®¬n ®Þnh M= (X, S, q0, δ , F) ta x©y dùng automat lìng cùc M’= (X, S’, q0, δ ’, {q’f}) sau: - S’:= S ∪{q’0, q’f} - δ ’(q,x)= δ (q,x) nÕu δ (q,x) ∩F=∅, víi q ∈ S, x ∈ X - δ ’(q,x)= δ (q,x) ∪{qf’} nÕu δ (q,x) ∩F≠∅ , víi q ∈ S, x ∈ X - Víi mäi x ∈X, δ ’(qo’,x)= δ (qo,x) - Víi mäi x ∈X, δ ’(q’f,x)=∅. Víi cµi ®Æt trªn suy ra: - M’ lµ automat lìng cùc. Ta cÇn chøng minh w ∈T(M)⇔w ∈T(M’). Ta cã c¸c biÓu thøc t¬ng ®¬ng sau : w ∈T(M)⇔ δ ’(qo,w) ∩F≠∅ ⇔ qf ∈ δ ’(qo,w) ⇔ w ∈T(M’) Ta chøng minh : w ∈T(M)⇔ δ ’(qo,w) ∩F≠∅ . ThËt vËy, víi w ∈T(M)⇔ δ (qo,w) ⊆ F

suy ra δ (qo,w)∩F≠∅ nªn

δ ’(qo,w)= δ (qo,x) ∪{qf} suy ra δ ’(qo,w) ∩F≠∅ . Ngîc

l¹i,

nÕu

δ ’(qo,w)

∩F≠∅

th×

δ ’(qo,w)

∩F

=

{δ (qo,x)

∪{q’f}}∩F≠∅ mµ q’f∉F nªn δ (qo,w) ∩F≠∅ .

Bé m«n khoa häc m¸y tÝnh - HVKTQS

45

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

NÕu δ ’(qo,w) ∩F≠∅ mµ δ ’(qo,w)= δ (qo,w) nÕu δ (qo,w) ∩F=∅ ( ⇒δ ’(qo,w) ∩F=∅ ) δ (qo,w) ∪{q’f} nÕu δ (qo,w) ∩F≠∅ nªn δ ’(qo,w)= δ (qo,w) ∪{q’f}, nghÜa lµ q’f∈ δ ’(qo,w) ⇔ w ∈T(M’).

4.4. BiÓu diÔn ng«n ng÷ chÝnh quy bëi Automat. a. §Þnh lý 2.9. Mäi ng«n ng÷ chÝnh quy trªn b¶ng X ®Òu biÓu diÔn ®îc bëi automat h÷u h¹n. Ta chøng minh quy n¹p theo qu¸ tr×nh x©y dùng ng«n ng÷ chÝnh quy. Gi¶ sö E ={xi}, xi∈X hoÆc E=e ta x©y dùng automat sau: xi

q 0

q

q

1

0

e

Gi¶ sö E, F lµ 2 ng«n ng÷ chÝnh quy vµ M1, M2 lµ 2 automat lìng cùc biÓu diÔn E vµ F. Ta x©y dùng automat sau:

S’

e

0

e

M2

M1

s

s

0

f

q f

e

e Sf’

Theo h×nh trªn ta thªm vµo 2 tr¹ng th¸i míi lµ tr¹ng th¸i ®Çu s’0 vµ tr¹ng th¸i kÕt thóc s’f viÖc chuyÓn tr¹ng th¸i s’0 sang tr¹ng th¸i ®Çu q0 hoÆc s0 lµ khi gÆp tõ rçng e. T¬ng tù viÖc chuyÓn tõ tr¹ng th¸i kÕt thóc qf sang s’f khi automat gÆp tõ rçng e.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

46

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

Còng nh vËy ta cã c¸c automat lìng cùc biÓu diÔn E.F vµ E+ nh sau:

q

Q

0

f

q s

s

0

f

e q

o

0

1

q

q

0

f

e

Q’ f

VËy c¸c ng«n ng÷ chÝnh quy trªn X ®Òu biÓu diÔn ®îc b»ng automat h÷u h¹n. §Þnh lý 2.10. Mäi ng«n ng÷ biÓu diÔn ®îc b»ng automat h÷u h¹n trªn X ®Òu lµ ng«n ng÷ chÝnh quy trªn X. Chøng minh. Gi¶ sö E lµ ng«n ng÷ trªn X ®îc biÓu diÔn bëi automat h÷u h¹n lìng cùc M cã n tr¹ng th¸i M=(X, S, δ , q0, qf) ta chøng minh E lµ chÝnh quy trªn X b»ng quy n¹p theo sè tr¹ng th¸i cña M. - Víi n=2, khi ®ã M chØ cã 2 tr¹ng th¸i M=(X, {q 0.qf}, δ , q0, F) v× M lµ automat lìng cùc nªn cã d¹ng q 0

xi

q f

do ®ã E=L(M)={x1, x2,…, xk } lµ ng«n ng÷ chÝnh quy trªn X. - Gi¶ sö ®iÒu kh¼ng ®Þnh trªn ®óng ®Õn n tr¹ng th¸i, ta chøng minh ®óng ®Õn n+1 tr¹ng th¸i. M=(X, S, δ , q0, qf) lµ automat lìng cùc biÓu diÔn ng«n ng÷ E trªn X, khi ®ã E=L(M) vµ S=n+1. Chän

Bé m«n khoa häc m¸y tÝnh - HVKTQS

47

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

tr¹ng th¸i tuú ý q’ kh¸c q0 vµ qf. Gäi L1:={w: q’ kh«ng n»m trªn ®êng ®i tõ q0 ®Õn qf øng víi x©u w} L2:={w: q’ n»m trªn ®êng ®i tõ q0 ®Õn qf øng víi x©u w} Khi ®ã râ rµng L(M)=L1∪ L2. Trong M ta bá ®i q’ vµ c¸c cung nèi víi q’ ta sÏ ®îc automat lìng cùc M1 vµ M1 biÓu diÔn L1 v× vËy L1 lµ chÝnh quy do sè tr¹ng th¸i cña M1 nhá h¬n hoÆc b»ng n. Gäi L3 ={w∈X+: w lµ nh·n cña ®êng ®i tõ q0 ®Õn q’} L4 ={w∈X+: w lµ nh·n cña ®êng ®i tõ q’ ®Õn q’} L5 ={w∈X+: w lµ nh·n cña ®êng ®i tõ q’ ®Õn qf} Khi ®ã L2= L3 L4 L5. Gäi M3 lµ automat lìng cùc thu ®îc tõ M b»ng c¸ch bá ®i c¸c cung nèi víi qf vµ c¸c cung ra tõ q’, râ rµng L3=L(M3). Gäi M5 lµ automat lìng cùc víi cùc vµo lµ q’ cùc ra lµ qf ®å thÞ thu ®îc tõ M sau khi bá ®i q0 vµ c¸c cung nèi víi q0 cïng c¸c cung vµo nèi víi q’, râ rµng L5=L(M5). X©y dùng M4 nh sau: - Bá q0, qf cïng c¸c cung nèi chóng - T¸ch q’ thµnh 2 ®Ønh q’0 vµ q’f cïng c¸c c¹nh ®i ra tõ q’ vµ c¹nh ®i vµo tõ q’ t¬ng øng. Khi ®ã L4=L(M4)+ Theo quy n¹p th× Li i=1..5 lµ chÝnh quy, vËy suy ra E chÝnh quy. VÝ dô: XÐt automat

a,b

q 1

a,b

q 0

b

b

a

a qa f0

q ’

a,b

Bé m«n khoa häc m¸y tÝnh - HVKTQS

48

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

b

C¸c automat M1

a,b q

a,b

q

aq

1

a

0

Automat M3

q

f0

a,b

Automat M4

1

q

q

q’

0 0

q ’

a,b

q’

1

a

f

a

a,b b

q 1

b

q q ’

b

f

Automat M5 a

a,b a

a,b b

4.5 X¸c ®Þnh biÓu thøc chÝnh quy cña Automat. Bé m«n khoa häc m¸y tÝnh - HVKTQS q 1

49

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

a. Bµi to¸n: Cho automat M h·y x¸c ®Þnh biÓu thøc chÝnh quy r ®Ó sao cho L(r)= L(M). b. §Þnh lý 2.11. Gi¶ sö E, p, q lµ biÓu thøc chÝnh quy vµ e∉L(p) khi ®ã E=qp* lµ nghiÖm cña ph¬ng tr×nh E=Ep+q. Chøng minh. Tõ ph¬ng tr×nh E=Ep+q ta cã: E=Ep+q=

Ep2+qp+q=

(Ep+q)p+q=

(Ep+q)p2+pq+q=Ep3+qp2+qp+q TiÕp tôc ta ®îc: E= Epi+1+qpi+qpi-1+…+qp+q XÐt x∈L(E), gi¶ sö  x =i v× e∉L(p) nªn x©u y nµo ®ã mµ y∈L(Epi+1) th×  y  >=i+1 vËy nªn x∉L(Epi+1) do ®ã x∈L(qpi+qpi-1+…+qp+q) vËy nªn x∈L(qp*). Ngîc l¹i gi¶ sö x∈L(qp*) vµ  x =i, tõ ®¼ng thøc E= Epi+1+qpi+qpi1

+…+qp+q suy ra x∈L(E). §Þnh lý ®îc chøng minh.

c. øng dông ®Þnh lý. Nhê ®Þnh lý lý trªn ta t×m ®îc tËp ng«n ng÷ ®o¸n nhËn automat M=(X, S, δ , s0, F). -

XÐt

s∈S

ký

hiÖu

rs

lµ

biÓu

thøc

chÝnh

quy

mµ

L(rs)={ x∈X*:δ ( s0,x)=s}, khi ®ã tËp ng«n ng÷ ®o¸n nhËn bëi automat M cã thÓ viÕt díi d¹ng: L(M)=∪s∈F L(rs). - XÐt tËp {(s’,a) ∈SxX: δ ( s’,a)=s}={(a1,s1), (a2,s2),…, (am(s),sm(s))} (1). Khi ®ã ta cã rs=

rs1a1+

rs2a2+

rs3a3+…+

rm(s)am(s)

víi

s∈S

vµ

s≠ s0

(2) rs=

rs1a1+

rs2a2+

rs3a3+…+

rm(s)am(s)

+e

víi

s=s0

(3)

Bé m«n khoa häc m¸y tÝnh - HVKTQS

50

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

HÖ (1), (2) gåm  S  +1 ph¬ng tr×nh gi¶i hÖ nµy ta x¸c ®Þnh ®îc biÓu thøc chÝnh quy sao cho L(r)=L(M). VÝ dô. Cho automat 0

0

S

s 1

0

f

S

0

1

2

Khi ®ã hµm chuyÓn cã d¹ng sau: 0 S0 S1

1 S0 ,S1 e

S2

S2 S2

e S 0, e

Ta lÇn lît tÝnh tËp 4. {(s’,a) ∈SxX: δ ( s’,x)=s0}={(0,s0), (1,s1)}

(4).

5. {(s’,a) ∈SxX: δ ( s’,x)=s1}={(0,s0)}

(5).

6. {(s’,a) ∈SxX: δ ( s’,x)=s2}={(0,s2), (1,s1)}

(6).

Khi ®ã rs0=rs0.0 + rs1.1+ e

(7)

rs1=rs0.0

(8)

rs2= rs2.0+ rs1.1

(9)

r= rs2 (v× L(r)= L(rs2)={ x∈X*:δ ( s0,x)=s2}) (10) Thay rs1 ë (8) vµo (7) ®îc rs0=rs0.0 + rs0.01+ e hay rs0=rs0(0+01)+ e, Theo ®Þnh lý trªn ta cã rs0=e(0 +01)*

(11)

Tõ (8), (9) vµ (10) ta l¹i cã r=r.0+rs0.01=r.0+(0 +01)*.01 ¸p dông l¹i ®Þnh lý ta ®îc r=(0 +01)*.010*. VËy L(M)=L(r)={ (0 +01)*.010*}.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

51

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

4.6. §¸nh gi¸ lùc lîng ng«n ng÷ chÝnh quy. a. §Æt vÊn ®Ò. V¨n ph¹m chÝnh quy G sinh ra ng«n ng÷ chÝnh quy hoÆc cho automat h÷u h¹n M ®o¸n nhËn ng«n ng÷ ®ã, vÊn ®Ò lµ lµm thÕ nµo ®Ó x¸c ®Þnh L(G) hay L(M) lµ h÷u h¹n hay v« h¹n. §Þnh lý sau tr¶ lêi cho c©u hái trªn. b. §Þnh lý 2.12. Tån t¹i thuËt to¸n x¸c ®Þnh ng«n ng÷ ®o¸n nhËn bëi automat h÷u h¹n lµ h÷u h¹n hay v« h¹n. Chøng minh. Ta chøng minh mÖnh ®Ò t¬ng ®¬ng sau: NÕu L lµ ng«n ng÷ ®o¸n nhËn bëi automat h÷u h¹n M cã n tr¹ng th¸i th×: 1. L ≠∅ ⇔ L chøa mét x©u w tho¶ w<=n. 2. L v« h¹n ⇔ L chøa mét x©u w cã ®é dµi l tho¶ n < l <2n. ThËt vËy víi 1/ do L≠∅ nªn tån t¹i w=w1 w2…wm∈L, gi¶ sö w> n(⇔m>n) th× suy ra qu¸ tr×nh ®o¸n nhËn w ph¶i tr¶i qua h¬n n+1 chuyÓn tr¹ng th¸i, v× M chØ cã n tr¹ng th¸i nªn suy ra trong qu¸ tr×nh ®o¸n nhËn cã Ýt nhÊt mét tr¹ng th¸i xuÊt hiÖn 2 lÇn gi¶ sö r»ng qi0=δ (q0, w1 w2…wio ) vµ qi0=δ (q0, w1 w2…wjo ) khi ®ã xÐt x©u w’= w1 w2…wio wjo+1…wm râ rµng w’∈L vµ

w’< w, lÆp l¹i qu¸

tr×nh trªn cho ®Õn khi nhËn ®îc ®iÒu cÇn chøng minh. 2. L v« h¹n, khi ®ã L ph¶i chøa x©u cã ®é dµi tuú ý w - NÕu w>2n ta lÆp l¹i c¸ch lµm ë 1/ cho ®Õn khi w<2n - Ngîc l¹i, nÕu tån t¹i w sao cho w>n theo c¸ch lµm ë 1/ nhê ®ã ta cã thÓ sinh ra v« sè x©u b»ng c¸ch thªm vµo w sè lÇn tuú ý ®o¹n ký tù bÞ c¾t bá wio…wjo+1 ®Ó nhËn ®îc tõ míi, do vËy L v« h¹n.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

52

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

Ch¬ng 3. V¨n ph¹m phi ng÷ c¶nh. $1. V¨n ph¹m phi ng÷ c¶nh vµ c©y dÉn xuÊt cña nã. 1.1. C¸c kh¸i niÖm. a. Giíi thiÖu. V¨n ph¹m phi ng÷ c¶nh (VPPNC) ®îc ph©n lo¹i theo Chomsky lµ líp v¨n ph¹m cã ý nghÜa rÊt quan träng trong viÖc øng dông ®Ó x©y dùng c¸c ng«n ng÷ lËp tr×nh vµ lý thuyÕt ch¬ng tr×nh dÞch. Trong qu¸ tr×nh dÞch mét ch¬ng tr×nh nguån ra ch¬ng tr×nh ®Ých, ngêi ta sö dông c¸c cÊu tróc có ph¸p cña VPPNC ®Ó ph©n tÝch c¸c x©u vµo, cÊu tróc ®ã ®îc x¸c ®Þnh tõ c¸c chuçi quy t¾c sinh ra tõ x©u ®ã vµ nhê ®ã bé ph©n tÝch có ph¸p cña ch¬ng tr×nh dÞch sÏ cho biÕt x©u vµo ®ang xÐt cã thuéc x©u do v¨n ph¹m phi ng÷ c¶nh sinh ra hay kh«ng. b. V¨n ph¹m phi ng÷ c¶nh. Bé G=(N, T, s, P) gäi lµ v¨n ph¹m phi ng÷ c¶nh trong ®ã: - N tËp c¸c ký hiÖu kh«ng kÕt thóc. - T tËp c¸c ký hiÖu kÕt thóc. - s∈N ký hiÖu xuÊt ph¸t. - P tËp c¸c quy t¾c dÉn xuÊt d¹ng P={ A

α  A∈N, α ∈ (N

∪T)*}.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

53

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

1.2. C©y suy dÉn ®Çy ®ñ trong v¨n ph¹m phi ng÷ c¶nh. a. C©y suy dÉn ®Çy ®ñ. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P), c©y suy dÉn ®Çy ®ñ trong v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) lµ c©y ®îc thµnh lËp tõ mét d·y dÉn xuÊt ®Çy ®ñ trong G, nãi c¸ch kh¸c ta cã thÓ ®Þnh nghÜa nh sau:

C©y suy dÉn ®Çy ®ñ trong v¨n

ph¹m phi ng÷ c¶nh G=(N, T, s, P) lµ c©y tho¶ c¸c ®iÒu kiÖn sau: - Mçi ®Ønh ®îc g¸n mét nh·n, nh·n g¸n ë c¸c ®Ønh lµ c¸c ký hiÖu trong (N ∪T∪{e}). Gèc cña c©y g¸n nh·n s. - Mçi ®Ønh trong nh·n lµ mét ký hiÖu nµo ®ã trong N. - Mçi ®Ønh ngoµi(®Ønh l¸) ®îc g¸n nh·n lµ mét ký hiÖu trong tËp T∪{e} - NÕu ®Ønh m ®îc g¸n nh·n lµ A cßn c¸c ®Ønh con cña nã ®îc g¸n nh·n theo thø tù tõ tr¸i sang ph¶i X1,X2,X3 , ,Xn th× A X1X2X3 …Xn lµ mét quy t¾c nµo ®ã cña P. NÕu ®äc thø tù c¸c nh·n ë l¸ tõ tr¸i sang ph¶i ta sÏ nhËn ®îc mét x©u n»m trong L(G) vµ gäi lµ kÕt qu¶ suy dÉn ®Çy ®ñ cña G b. VÝ dô 1. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P), trong ®ã c. N={s,A}, T={a, b}.P={1. s

sa, 2. s

Aa, 3. A

aAb, 4.

ab}. C©y suy dÉn ®Çy ®ñ cña x©u w= a nbnam lµ

A

s

c©y sau:

s

VÝ dô 2. 1. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P), trong ®ã N={s}, T={a1,…,an}.P={1. s s

asa, 2. s

aa, trong ®ã a ∈T}.

C©y suy dÉn ®Çy ®ñ cña x©u w= a1…an an an-1…a1 lµ c©y sau: s

(H×nh 1 cho vÝ dô 1, h×nh 2 cho vÝ dô 2). m lÇn

s

s

a a

Bé m«n khoa häc m¸y tÝnh - HVKTQS s

54

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

.

a a

b

n lÇn a

b

a

b

a

b

VÝ dô 2. 1. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P), trong ®ã N={s}, T={a1,…,an}.P={1. s

asa, 2. s

aa, trong ®ã a ∈T}.

C©y suy dÉn ®Çy ®ñ cña x©u w= a1…an an an-1…a1 lµ c©y sau:

s

a1 s

a2

a1 a2

an-1

an-1

an

an

1.3. Sù nhËp nh»ng trong ng«n ng÷ phi ng÷ c¶nh. a. §Þnh nghÜa. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P), ta nãi v¨n ph¹m G lµ nhËp nh»ng nÕu tån t¹i mét x©u w lµ kÕt qu¶ cña 2 c©y dÉn xuÊt ®Çy ®ñ kh¸c nhau trong G, ng«n ng÷ do v¨n ph¹m nhËp nh»ng sinh ra gäi lµ ng«n ng÷ nhËp nh»ng. b. VÝ dô. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P)

trong ®ã

N={s}

Bé m«n khoa häc m¸y tÝnh - HVKTQS

55

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

T={+, a,*}, P={s

s+s, s

s*s, s

a}, trong ®ã + lµ

phÐp céng, * lµ phÐp nh©n. X©u a+a*a lµ kÕt qu¶ cña c©y suy dÉn ®Çy ®ñ sau s

s s

s *

+

a

a

+

s

s

s

s

s

s

a

a H×nh 1

* a

a

H×nh 2

H×nh 1 nÕu thùc hiÖn phÐp nh©n tríc vµ c©y suy dÉn ®Çy ®ñ h×nh 2 nÕu thùc hiÖn phÐp céng tríc Râ rµng x©u trªn lµ kÕt qu¶ cña 2 c©y suy dÉn kh¸c nhau.

$2. Gi¶n lîc v¨n ph¹m phi ng÷ c¶nh. 2.1. Ký hiÖu cã Ých vµ ký hiÖu thõa. a. Ký hiÖu cã Ých. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P), A ®îc gäi lµ ký hiÖu cã Ých nÕu tån t¹i suy dÉn s *

α Aβ

*

w, víi

α , β ∈ (N ∪T)*, A∈(N ∪T). b. Ký hiÖu thõa. NÕu A kh«ng tho¶ m·n ®iÒu kiÖn trªn th× A ®îc gäi lµ ký hiÖu thõa . c. Ký hiÖu v« sinh. Ký hiÖu A gäi lµ v« sinh nÕu víi mäi w∈T* kh«ng tån dÉn xuÊt A * w. d. Ký hiÖu kh«ng ®Õn ®îc. NÕu tõ ký hiÖu xuÊt ph¸t s kh«ng dÉn ®îc mét x©u nµo cã chøa ký hiÖu A th× ta nãi A lµ ký hiÖu kh«ng ®Õn ®îc, vËy ký hiÖu ký hiÖu thõa lµ ký hiÖu v« sinh vµ ký hiÖu kh«ng ®Õn ®îc. e. Bæ ®Ò 3.1.( Lo¹i ký hiÖu v« sinh). Cho v¨n PNC G=(N,T, s, P) víi L(G)≠∅ . Cã thÓ x©y dùng v¨n ph¹m phi ng÷ c¶nh G’=(N’, T, s, 56 Bé m«n khoa häc m¸y tÝnh - HVKTQS

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

P’) sao cho G ≈ G’ vµ víi mçi A∈N’ tån t¹i mét x©u w∈T* ®Ó A * w. Chøng minh. Ta x©y dùng N’ nh sau: - NÕu trong P cã quy t¾c d¹ng A * w th× ta ®a A vµo trong N’. - NÕu A

X1X2...Xn lµ quy t¾c trong P mµ Xi lµ biÕn thuéc T hoÆc

Xi lµ biÕn ®· ®îc ®a vµo N’ tríc ®ã th× ta ®a A vµo N’. Qu¸ tr×nh trªn sÏ dõng sau h÷u h¹n bíc v× sè c¸c quy t¾c lµ h÷u h¹n vµ ta x©y dùng ®îc tËp N’. - X©y dùng tËp quy t¾c P’⊆P gåm c¸c quy t¾c mµ c¸c

ký hiÖu

trong quy t¾c thuéc tËp T∪N’. Bæ ®Ò sÏ ®îc chøng minh nÕu L(G)⊆L(G’). Gi¶ sö w∈L(G) nghÜa lµ tån t¹i s *

w, mµ ®Ó ®Õn ®îc víi x©u w

th× ph¶i ¸p dông c¸c quy t¾c dÉn xuÊt kh«ng chøa c¸c ký hiÖu v« sinh do ®ã dÉn xuÊt ph¶i chøa c¸c quy t¾c trong P’ v× nÕu kh«ng th× kh«ng bao giê vÒ ®îc x©u gåm c¸c ký tù kÕt thóc, ®iÒu nµy cã nghÜa lµ w∈L(G’). f. Bæ ®Ò 3.2.( Lo¹i ký hiÖu kh«ng ®¹t ®Õn). Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) víi L(G)≠∅ . Cã thÓ x©y dùng v¨n ph¹m phi ng÷ c¶nh t¬ng ®¬ng G’=(N’, T’, s, P’) sao cho víi mçi x∈N’∪T’ tån t¹i α , β ∈ (N’∪T’)* ®Ó : s*

α xβ .

Chøng minh. Ta x©y dùng tËp V nh»m lo¹i bá ký hiÖu kh«ng ®¹t ®Õn nh sau: V0:={s}, Vi:={x A

α xβ ∈ P vµ A∈Vi-1}∪ Vi-1

Ta nhËn thÊy r»ng Vi-1 ⊆Vi⊆N∪T. V× d·y Vi kh«ng gi¶m nªn sÏ tån t¹i V=∪Vi=Vi0. X©y dùng G’=(N’,T’,s,P’) nh sau: N’:=N∩V; T’:=T∩V;

Bé m«n khoa häc m¸y tÝnh - HVKTQS

57

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

P’:={ TËp tÊt c¶ c¸c quy t¾c cña P chØ chøa c¸c ký hiÖu thuéc V}. Ta chØ cÇn chøng minh L(G)⊆L(G’). Gi¶ sö w∈L(G), nghÜa lµ tån t¹i dÉn xuÊt s

*

w, theo gi¶ thiÕt

th× d·y dÉn xuÊt nµy n»m trong P tuy nhiªn râ rµng c¸c dÉn xuÊt nµy kh«ng thÓ cã c¸c ký hiÖu kh«ng ®Õn ®îc v× vËy c¸c dÉn xuÊt nµy ph¶i thuéc tËp P’ do ®ã w∈L(G’). VÝ dô. Cho G=(N, T, s, P) trong ®ã: - N={s, A, B, C} - T={x,y,z} - P gåm: 1. s 5. C

Ax, 2. s

y, 6.B

x, 7. C

B y, 3. A

y, 4. A

B,

x.

TËp V ®îc x©y dùng nh sau: V0:= {s}, V1:= {w: d →α wβ ∈ P vµ d∈V0}∪V0= {w: s →α wβ ∈ P}∪ {s}={s, A, B, x, y}, V2:={ w: d →α wβ ∈ P vµ d∈V1}∪V1={s, A, B, x, y}=V1. VËy - N’:= N ∩V={s,A,B}; T’:=T ∩V={x, y}, -

P’:={1. s

2.s

B y, 3. A

Ax, x, 4. A

B,

5. A

y}.

g. §Þnh lý 3.1. Mäi ng«n ng÷ phi ng÷ c¶nh kh«ng rçng ®Òu cã thÓ ®îc sinh ra tõ mét v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) kh«ng cã ký hiÖu thõa VÝ dô. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) trong ®ã N:={s, A, B}, T:={a} P:={s

AB, S

a, A

a}, Khi ®ã L(G)={a}. V¨n ph¹m

G’=(N’, T’, s, P’) trong ®ã T’={a}, N’:={s}, P’:={s

a}.

2.2. C¸c e-quy t¾c.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

58

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

a. §Þnh nghÜa. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) nÕu trong P cã quy t¾c A

e, A ∈ N th× ta nãi trong G cã e-quy t¾c.

Ta th©ý nÕu L(G) kh«ng chøa e th× cã thÓ lo¹i hÕt c¸c e-quy t¾c trªn, nhng trong trêng hîp e ∈ L(G) th× kh«ng thÓ lo¹i toµn bé equy t¾c. b. §Þnh lý 3.2. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P). Khi ®ã L(G)\{e} ®îc sinh ra bëi v¨n ph¹m phi ng÷ c¶nh G’=(N’, T’, s, P’) kh«ng chøa c¸c ký hiÖu thõa vµ kh«ng chøa e-quy t¾c. Chøng minh. Kh«ng gi¶m tÝnh tæng qu¸t ta coi G kh«ng chøa c¸c ký hiÖu thõa. - NÕu A

e ∈ P th× A gäi lµ ký hiÖu triÖt tiªu. α

- NÕu B

∈ P mµ α gåm c¸c ký hiÖu triÖt tiªu th× B lµ ký

hiÖu triÖt tiªu. - NÕu B

α B ∈ P mµ B lµ ký hiÖu triÖt tiªu trong lÇn xÐt tríc

th× B l¹i kh«ng bÞ coi lµ ký hiÖu triÖt tiªu. LÆp l¹i qu¸ tr×nh trªn cho tíi khi trong N kh«ng cßn t×m ®îc c¸c ký hiÖu triÖt tiªu míi. - Lo¹i bá tÊt c¶ c¸c ký hiÖu triÖt tiªu trong N ta ®îc tËp míi gäi lµ N’. TËp P’ ®îc x¸c ®Þnh nh sau: - NÕu A A

X1 X2…Xn ∈P th× ta ®a vµo P’ quy t¾c d¹ng α 1α 2…α

n

, trong ®ã A∈N’ :

+ NÕu Xi lµ ký hiÖu kh«ng triÖt tiªu th× ®Æt α i=Xi + NÕu Xi lµ ký hiÖu triÖt tiªu th× ®Æt α i=e + NÕu mäi Xi lµ ký hiÖu triÖt tiªu th× thay α i=e víi i=1..n. th× A kh«ng cßn thuéc N’ nªn trêng hîp nµy kh«ng xÈy ra. Ta chØ cÇn chøng minh L(G)\{e}⊆L(G’). Râ rµng e∉L(G’) vµ w∈L(G)\{e} cã nghÜa lµ tån t¹i s *

w mµ mçi

mét dÉn xuÊt thµnh phÇn chØ ®îc sinh ra bëi c¸c ký tù kh«ng triÖt

Bé m«n khoa häc m¸y tÝnh - HVKTQS

59

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

tiªu vµ ®iÒu nµy cã nghÜa lµ c¸c quy t¾c dÉn xuÊt ®ã n»m trong P’ vµ do ®ã w∈L(G’). VÝ dô. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) trong ®ã T={a,b}; N={s,A,B} P={s

AB; A

aA; A

e; B

bB; B

e. Lo¹i bá c¸c e-quy t¾c. Ta thÊy e ∈ L(G), theo ®Þnh lý th× lo¹i A

e; B

e v× A, B lµ ký

tù triÖt tiªu. s

AB, tõ A

aA suy ra A

Do ®ã P’={s

AB; A

a; B

a vµ B b;s

bB suy ra B

A; s

b.

B}

Râ rµng v¨n ph¹m G’ kh«ng cã e-quy t¾c.

2.3. Quy t¾c ®¬n. a. §Þnh nghÜa. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P), nÕu cã quy t¾c dang A

B ∈ P; A, B∈N th× ta nãi ®ã lµ quy t¾c ®¬n

cña G. Ta thÊy r»ng quy t¾c ®¬n chØ cã t¸c dông kÐo dµi thêi gian sinh ra ng«n ng÷ v× vËy ta t×m c¸ch rót lo¹i quy t¾c d¹ng nµy khi cã thÓ mµ kh«ng ¶nh hëng tíi ng«n ng÷ ®îc sinh ra bëi v¨n ph¹m ®· cho. §Þnh lý sau ®©y cho ta c©u tr¶ lêi ®ã. b. §Þnh lý 3.3. Mäi v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) kh«ng chøa x©u rçng ®Òu cã thÓ sinh ra tõ mét v¨n ph¹m phi ng÷ c¶nh kh«ng cã ký hiÖu thõa, kh«ng cã e-quy t¾c, kh«ng cã quy t¾c ®¬n. Chøng minh. Theo c¸c ®Þnh lý trªn kh«ng gi¶m tæng qu¸t ta coi v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) sao cho

e∉L(G) trong N

kh«ng cã ký hiÖu thõa vµ P kh«ng cã e-quy t¾c. Ta x©y dùng v¨n ph¹m phi ng÷ c¶nh G’=(N’, T’, s, P’) kh«ng cã quy t¾c ®¬n nh sau: - N’:=N. - §a tÊt c¶ c¸c quy t¾c kh«ng ®¬n cña P vµo P’. - NÕu A

B ∈ P, víi A, B ∈ N’, khi ®ã ch¾c ch¾n tån t¹i dÉn

xuÊt:

Bé m«n khoa häc m¸y tÝnh - HVKTQS

60

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

s

*

α Aβ

α Bβ

*

α wβ , víi α , β ∈ (N’ ∪T)*, w

∈ T* do N’ gåm c¸c ký hiÖu kh«ng thõa. -Ta thay quy t¾c A A

α Aβ ,

B vµ ®a vµo P’ c¸c quy t¾c s

w

Khi ®ã 2 quy t¾c trªn kh«ng ®¬n vµ chøc n¨ng sinh ng«n ng÷ gièng nh A

B, do ®ã L(G)=L(G’).

d. VÝ dô. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P)

trong ®ã

T={a}, N={s,A,B} P={s

s+A, s

A, A

A * B, A

Ta x©y dùng v¨n ph¹m míi víi P’={s s

A*B,A

a, s

B, B s+A, A

a} A * B, B

a,

a } kh«ng cßn quy t¾c ®¬n vµ G≈ G’.

$3. V¨n ph¹m chuÈn Chomsky vµ Greibach. 3.1 V¨n ph¹m chuÈn Chomsky. a. §Þnh nghÜa. V¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) gäi lµ v¨n ph¹m chuÈn Chomsky nÕu mäi quy t¾c ®Òu cã d¹ng A A

BC hoÆc

a víi A, B, C ∈ N vµ a ∈ T.

b. §Þnh lý 3.4. Víi v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) bao giê còng tån t¹i v¨n ph¹m phi ng÷ c¶nh chuÈn Chomsky G’=(N’, T, s, P’) t¬ng ®¬ng víi nã. Chøng minh. Gi¶ sö v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P), theo c¸c ®Þnh lý trªn ta cã thÓ coi trong P kh«ng chøa c¸c e-quy t¾c vµ quy t¾c ®¬n. Ta còng cã thÓ gi¶ thiÕt trong P chØ gåm c¸c quy t¾c d¹ng A

a

hoÆc A

Bé m«n khoa häc m¸y tÝnh - HVKTQS

61

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

B1 B2…Bn (a ∈ T, Bi ∈ N), nÕu cha ®¹t ®îc ®iÒu ®ã ta x©y dùng G’ sao cho L(G)=L(G’) vµ G’ cã tËp quy t¾c P’ d¹ng A

a hoÆc A

B1 B2…Bn (a ∈ T, Bi ∈ N) nh sau: -Víi mçi a ∈ T ta ®Æt t¬ng ®¬ng víi ký hiÖu ¨, ®Æt N’:=N ∪{¨ a ∈ T} -Trong tÊt c¶ c¸c quy t¾c cña P mµ trong ®ã vÕ ph¶i cña quy t¾c cã chøa ký hiÖu chÝnh a ∈ T th× trong quy t¾c ®ã ta thay a bëi ¨ ta ®îc P1. §Æt P’:=P1∪{ ¨

aa ∈ T}

Khi ®ã ta nhËn ®îc v¨n ph¹m G’ t¬ng ®¬ng G nhng c¸c quy t¾c dÉn xuÊt cã d¹ng A

B1 B2…Bn (a ∈ T, Bi ∈ N). C¸c

a hoÆc A

trêng hîp sau sÏ xÈy ra: TH1. NÕu P gåm c¸c quy t¾c d¹ng A

a; A

BC khi ®ã ®Þnh lý

®îc chøng minh. TH2. NÕu P gåm c¸c quy t¾c d¹ng A ∈ T, Bi ∈ N) th× ta cã thÓ thay A

a hoÆc A

B1 B2…Bn (a

B1 B2…Bn (a ∈ T, Bi ∈ N) bëi c¸c

quy t¾c sau: A

B1K1; K1

B2K2;…; Kn-3

Bn-2Kn-2; Kn-2

Bn-1Bn ë ®©y c¸c

K1…Kn-2 lµ c¸c ký hiÖu phô míi. §Æt - N’:=N ∪{K1,…, Kn-2}; - P’:={A

a; A

B1K1; K1

B2K2;…; Kn-3

Bn-2Kn-2; Kn-2

Bn-1Bn Khi ®ã v¨n ph¹m phi ng÷ c¶nh G’=(N’, T, s, P’) tho¶ m·n ®iÒu kiÖn ®Þnh lý. c. C¸c vÝ dô. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) trong ®ã N={s, A}; T={a,b}; P={s A

aAs;s

a; A

sbA; A

ss;

ba}. Ta x©y dùng

G’ nh sau:

Bé m«n khoa häc m¸y tÝnh - HVKTQS

62

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

- B1. X©y dùng G’ víi N’:={s, A, ¨, b’’(a,b ngang)}; P’:={s s

¨As;A

sb’’A; A

ss; A

ta ®îc c¸c quy t¾c d¹ng ta cÇn A

b’’¨; ¨

a;b’’

a vµ A

a; b}

B1 B2…Bn .

B2. X©y dùng v¨n ph¹m phi ng÷ c¶nh chuÈn Chomsky Cã T={a, b}; P’:= {s

a;s

¨B 1; B1

As; A

sB2; B2

b’’A; A

ss; A

b’’¨; ¨

a;b’’

b}. §©y lµ v¨n ph¹m chuÈn

Chomsky. VÝ dô 2. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P)

víi

N={s,A,B};T={a,b} P={s

bA;s

aB;A

bAA;A

as;A

a;B

aBB,B

bs; B

b}.

B1. X©y dùng G’ nh sau: T:={a,b}; N’:={s,A,B,¨,b’’}; P’:={ s B

b’’A;s

b’’s; B

¨B;A b;¨

b’’AA;A

a;b’’

¨s;A

a;B

¨BB;

¨s;A

a;

b}.

B2. X©y dùng chuÈn Chomsky. T:={a,b}; N’:={s,A,B,¨,b’’,B1,B2}; P’:={ s B

b’’A;s

¨B2; B2

¨B;A BB; B

b’’B1;B1 b’’s; B

AA;A b;¨

a;b’’

b}.

3.2. V¨n ph¹m phi ng÷ c¶nh chuÈn Greibach. a. §Þnh nghÜa. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) ta gäi quy t¾c dÉn xuÊt cña P lµ A-quy t¾c nÕu nã cã d¹ng A

α víi

α ∈ ∈(N ∪T)+ b. §Þnh nghÜa. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) ta nãi G lµ v¨n ph¹m cã d¹ng chuÈn Greibach nÕu víi mäi quy t¾c dÉn xuÊt cña P ®Òu cã d¹ng A

aα víi a ∈ T; α ∈ N*.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

63

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

c. Bæ ®Ò 3.3. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P), gi¶ sö α 1Bα 2; 2. B

trong P cã c¸c quy t¾c d¹ng : 1. A

β i (i=1…

r). Khi ®ã cã thÓ x©y dùng v¨n ph¹m G’ tho¶ c¸c ®iÒu kiÖn sau: - L(G)=L(G’) α 1Bα 2} ∪{A

- P’=P\{ A

α

1

β iα

2

(i=1…r)}.

Bæ ®Ò 3.3 cho phÐp ta thay quy t¾c 1 bëi quy t¾c d¹ng A α

1

β iα

2

mµ kh«ng thay ®æi L(G).

Chøng minh. LÊy w ∈ L(G’) khi ®ã tån t¹i s

*

w trong G’.

- NÕu c¸c dÉn xuÊt thµnh phµn cña dÉn xuÊt nµy kh«ng sö dông Aquy t¾c th× ®¬ng nhiªn nã vÉn lµ dÉn xuÊt trong G nªn w ∈ L(G). - NÕu dÉn xuÊt s α

1

β iα

2

α

1

β iα

2

*

w trong G’ cã dÉn xuÊt thµnh phÇn d¹ng A

víi i nµo ®ã th× ta thay dÉn xuÊt trªn bëi A

α

1

Bi α

2

w lµ dÉn xuÊt trong G nªn w ∈ L(G).

vµ khi ®ã s *

Ngîc l¹i, nÕu w ∈ L(G) khi ®ã tån t¹i s

*

w, sÏ xÈy ra c¸c trêng hîp

sau: - NÕu dÉn xuÊt trªn kh«ng sö dông A- quy t¾c th× dÉn xuÊt trong G còng lµ trong G’ - NÕu dÉn xuÊt trong G cã dïng A-quy t¾c d¹ng A th× ®Ó cã s

*

w

α

1

Bi α

2

β

i

th× ta ph¶i sö dông quy t¾c d¹ng B

khi dã chØ cÇn thay 2 bíc nµy b»ng mét quy t¾c cña G’ nªn w ∈ L(G’). d. Bæ ®Ò 3.4. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P), gi¶ sö trong P cã c¸c quy t¾c d¹ng sau: 1. A

A α i (i=1…r); (1) 2. A

β j (j=1..s ) (2).

Khi ®ã tån t¹i v¨n ph¹m phi ng÷ c¶nh G’ tho¶ m·n ®iÒu kiÖn sau: 1. L(G)=L(G’)

Bé m«n khoa häc m¸y tÝnh - HVKTQS

64

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

A α i } ∪{A

P’:=P\{ A

β j Z} ∪{Z

α i, Z

α iZ}

víi

i=1…r, j=1…s vµ Z∉N . Chøng minh. Thùc chÊt cña bæ ®Ò lµ thay c¸c A- quy t¾c bëi c¸c quy t¾c d¹ng: β j Z} ∪{Z

{A

α i, Z

α iZ}

víi i=1…r, j=1…s vµ

Z∉N . X©y dùng G’ nh sau: - N’:=N ∪{Z} A α i } ∪{A

- P’:= P\{A

β j Z} ∪{Z

α i, Z

α iZ}

víi i=1…r, j=1…s vµ Z∉N . LÊy w ∈ L(G) khi ®ã tån t¹i dÉn xuÊt s *

w vµ:

- NÕu dÉn xuÊt nµy kh«ng sö dông A- quy t¾c (1),(2) ë bíc nµo ®ã th× dÉn xuÊt nµy còng lµ cña G’ -NÕu dÉn xuÊt nµy sö dông quy t¾c (1),(2) ë bíc nµo ®ã ch¼ng h¹n: γ 1Aγ

2

γ 1Aα i1γ

α ik…α i2α i1γ

γ 1Aα i2α i1γ

2

γ 1Aα ik…α i2α i1γ

2

2

γ 1β

j

2

Khi ®ã ta thay d·y trªn b»ng c¸c quy t¾c cña P’ nh sau: -γ 1Aγ γ 1α

ik

γ 1β j Z γ

2

…α i2α i2Zγ

2

γ 1β j Zα ikγ

2

γ 1β j α ikα

γ 1β j α ik…α i2α i1γ

2

2

ik-1

Z γ 2…

, nªn suy ra w ∈

L(G’). Ngîc l¹i, w ∈ L(G’) th×: - NÕu trong

dÉn xuÊt s

*

w trong G’ kh«ng sö dông quy t¾c

nµo liªn quan ®Õn Z th× w ∈ L(G) - NÕu trong cã bíc nµo liªn quan ®Õn Z ch¼ng h¹n cã ®o¹n dÉn xuÊt sau:

Bé m«n khoa häc m¸y tÝnh - HVKTQS

65

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

tβ j Z γ

tAγ

tβ j α ikZ γ

tβ j α ikα

…α i2Z γ

ik-1

tβ

j

tβ

j

α ik…α i2α i1γ ta cã thÓ thay nh sau: tAα i1γ

tAγ

tAα

i2

α i1Z γ

tAα ikα

ik-1

…α i2α

i1

γ

α ik…α i2α i1γ do ®ã w ∈ L(G). e. §Þnh lý 3.5. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P), khi ®ã tån tai v¨n ph¹m phi ng÷ c¶nh G’=(N’, T’, s, P’) lµ v¨n ph¹m chuÈn d¹ng Greibach. Chøng minh. Kh«ng gi¶m tæng qu¸t ta coi G lµ v¨n ph¹m chuÈn Chomsky. Gi¶ sö N={s,A1, A2,…,An} ta tiÕn hµnh c¸c bíc sau: B1:TiÕn hµnh thay thÕ c¸c quy t¾c dÉn xuÊt ®Ó sao cho c¸c quy t¾c dÉn xuÊt cña v¨n ph¹m cã d¹ng: Ai

Ajγ víi γ ∈ N*, i>j. ViÖc

nµy ®îc thùc hiÖn quy n¹p. Gi¶ sö c¸c quy t¾c ®· söa vÒ d¹ng Ai Ajγ víi γ ∈ N*, i>j, i=1,…,k. Ta söa ®æi cho quy t¾c Ak+1 ë vÕ tr¸i. Ajγ víi γ ∈ N* lµ quy t¾c vµ j
- NÕu Ak+1

tËp c¸c quy t¾c míi b»ng c¸ch thay Aj ë vÕ ph¶i cña mçi Aj– quy t¾c theo bæ ®Ò 1. B2. LÆp l¹i quy tr×nh nµy kh«ng qu¸ k-1 lÇn ta nhËn ®îc A

k+1

Alγ víi γ ∈ N*, l>= k+1. B3. - Trêng hîp l=k+1 th× ¸p dông bæ ®Ò 2 b»ng c¸ch ®a vµo biÕn míi Zk+1. - LÆp l¹i quy tr×nh trªn cho mçi biÕn cña tËp N ta sÏ nhËn ®îc c¸c quy t¾c d¹ng sau: 1. A k

Alγ víi γ ∈ N*, l>k.

2. Ak

aγ víi γ ∈ N*, a ∈ T

3. Zk

γ víi γ ∈ (N∪{Z1, Z2,…, Zm}*

Bé m«n khoa häc m¸y tÝnh - HVKTQS

66

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

Chó ý r»ng c¸c ký hiÖu tr¸i nhÊt cña c¸c vÕ ph¶i trong c¸c A n- quy t¾c ph¶i thuéc T v× An lµ chØ sè cao nhÊt, cßn ký hiÖu tr¸i nhÊt cña An-1 quy t¾c ph¶i thuéc T* hoÆc lµ An. Do ®ã ta ®îc d¹ng chuÈn Greibach. VÝ dô. ChuyÓn v¨n ph¹m phi ng÷ c¶nh G=({A1, A2 , A3},{a, b},A1, P) trong ®ã P 1. A1

A2 A3

4. A3

A1 A2

2. A2

A3 A1

5. A3

a

3. A2

b

ViÖc chuÈn ho¸ ®îc tiÕn hµnh theo c¸c bíc sau: B1. - VÕ ph¶i cña quy t¾c 4 cã A1, A2 vµ biÕn ë vÕ tr¸i cã chØ sè cao nªn thay A1 bëi A2A3 chó ý r»ng A1

A2A3 chØ cã A1 ë vÕ tr¸i.

KÕt qu¶ lµ: 1. A1

A2 A3

4. A3

A2 A3 A2

2. A2

A3 A1

5. A3

a

3. A2

b

- Ta th©ý quy t¾c 4 míi biÕn ®Çu bªn ph¶i (A2) chØ sè thÊp h¬n ta thay A2 bëi quy t¾c 2 hoÆc quy t¾c 3 ta ®îc: A3

A3A1 A3 A2 vµ A3

bA3A2 Ta nhËn ®îc tËp quy t¾c míi: 1. A1

A2 A3

4. A3

A3A1 A3 A2

2. A2

A3 A1

5. A3

bA3A2

3. A2

b

6. A3

a

- ¸p dông bæ ®Ò 2 cho c¸c A3- quy t¾c 4-6: §èi víi A3-quy t¾c 4 ta bæ sung Z3 khi ®ã quy t¾c A3

A3 A1 A3

A2 ®îc thay thÕ bëi bëi c¸c quy t¾c: A3

bA3 A2Z3

A3

aZ3

Z3

A1 A3A2

Z3

A1A3 A2Z3

Bé m«n khoa häc m¸y tÝnh - HVKTQS

67

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

Cuèi cïng ta cã tËp quy t¾c sau: 1. A1

A2 A3

4. A3

bA3A2Z3

2. A2

A3 A1

5. A3

aZ3

3. A2

b

6. Z3

7. A3

bA3A2

8. Z3 A1A3A2Z3

A1 A3 A2

9. A3

a

B2.- TÊt c¶ c¸c quy t¾c A3-quy t¾c cã vÕ ph¶i b¾t ®Çu víi ký tù kÕt thóc. B©y giê ta xÐt A2-quy t¾c: A2

A3 A1, ¸p dông c¸c A3-

quy t¾c võa ®îc thÕ ë trªn ®Ó ®a A2-quy t¾c vÒ d¹ng chuÈn. Víi c¸ch lµm trªn ta ®îc: 1. A1

A2 A3

4. A3

2.

bA3A2Z3

5. A3

3. A2

b

2.1. A2

6. Z3 aA1

2.4. A2

aZ3

bA3A2

8. Z3

A1A3A2Z3

2.2. A2

7. A3 9. A3

bA3A2Z3 A1, 2.3. A3

A1 A3 A2 a bA3A2A1

aZ3 A1.

- §a A1-quy t¾c A1

A2 A3 vÒ d¹ng chuÈn sau khi ¸p dông c¸c

A2quy t¾c: 1.1 A1

b A3

1.4 A1

aA1A3

1.2. A1

bA3A2Z3A1A3

1.5. A1 4. A3

bA3A2Z3

2.

5. A3

aZ3

2.1. A2 2.4. A2

b

6. Z3 aA1

2.2. A2

aZ3A1A3

bA3A2A1A3

1. 3. A2

1.3.A1

A1A3A2Z3

7. A3 8. Z3 9. A3

bA3A2Z3 A1, 2.3. A3

bA3A2 A1A3 A2 a bA3A2A1

aZ3 A1.

B3. Ta thÊy Z3- quy t¾c cha thuéc d¹ng chuÈn nªn tiÕp tôc biÕn ®æi: - Víi quy t¾c 8: Ta thay c¸c A1- quy t¾c 1.1-1.5 vµo vÕ ph¶i ®îc 8.1. Z3

b A3A3A2

8.3.Z3

aZ3A1A3A3A2,

8.2.Z3

bA3A2Z3A1A3A3A2

Bé m«n khoa häc m¸y tÝnh - HVKTQS

68

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

8.4 Z3

aA1A3A3A2

8.5 Z3

bA3A2A1A3A3A2.

VËy ta nhËn ®îc c¸c quy t¾c chuÈn Greibach tõ 1.1- 8.5.

$4.Automat ®Èy xuèng(Automat push-down). Nh ta ®· biÕt ng«n ng÷ chÝnh quy ®îc s¶n sinh ra bëi c¸c v¨n ph¹m chÝnh quy, ®ång thêi l¹i ®îc ®o¸n nhËn bëi automat h÷u h¹n. Trong môc nµy ta l¹i thÊy r»ng líp c¸c ng«n ng÷ phi ng÷ c¶nh ®îc sinh ra bëi v¨n ph¹m phi ng÷ c¶nh l¹i ®îc ®o¸n nhËn bëi mét lo¹i automat kh¸c, gäi lµ automat ®Èy xuèng, cã ®iÒu automat ®Èy xuèng ë ®©y ph¶i kh«ng ®¬n ®Þnh, cßn líp automat ®Èy xuèng ®¬n ®Þnh chØ cho phÐp ®o¸n nhËn tËp con thùc sù cña v¨n ph¹m phi ng÷ c¶nh.

4.1. C¸c kh¸i niÖm. a. M« t¶ automat PA. PA vÉn gi÷ nh÷ng thµnh phÇn c¬ b¶n cña automat h÷u h¹n gåm: - Mét bé ®iÒu khiÓn cã h÷u h¹n tr¹ng th¸i. - Mét ®Çu ®äc cho phÐp ®äc lÇn lît c¸c ký tù tõ tr¸i sang ph¶i c¸c ký hiÖu cña x©u vµo ghi trªn mét b¨ng vµo. - Mét b¨ng lµm viÖc gäi lµ ng¨n xÕp(stack) nhê b¨ng nµy mµ kh¶ n¨ng ghi nhí ®îc t¨ng thªm. Ng¨n xÕp ®îc tæ chøc theo nguyªn t¾c LIFO, khi ®a mét ký hiÖu vµo ng¨n xÕp th× ký hiÖu ®ã ®îc ®Æt lªn ®Çu ng¨n vµ ®Èy c¸c ký hiÖu cò xuèng díi, khi ®äc th× chØ cã mét ký hiÖu ®îc ®äc Êy lµ ký hiÖu trªn cïng vµ khi ®äc xong th× ký hiÖu ®ã ®îc xo¸ khái ng¨n xÕp. 0 1

1

1

0

1

1

0

1 Bé ®iÒu khiÓn(q)

1

0 Bé m«n khoa häc m¸y tÝnh - HVKTQS 1

69

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

- Mét bíc chuyÓn cña automat ®îc thùc hiÖn nh sau: Víi tr¹ng th¸i cña hiÖn t¹i cña bé ®iÒu khiÓn, ký hiÖu vµo mµ ®Çu ®äc quan s¸t ®îc lóc ®ã vµ ký hiÖu ë ®Çu ng¨n xÕp mµ automat chuyÓn sang tr¹ng th¸i míi nµo ®ã, ghi mét x©u ký hiÖu vµo ng¨n xÕp vµ ®Çu ®äc chuyÓn sang ph¶i mét « vµ ta gäi qu¸ tr×nh trªn lµ mét bíc chuyÓn. - NÕu ký hiÖu vµo kh«ng ¶nh hëng tíi bíc chuyÓn ta gäi ®ã lµ bíc chuyÓn nh¾m m¾t, thùc chÊt cña nã lµ t¹m dõng quan s¸t b¨ng vµo(®Çu ®äc ®øng yªn) nh»m chÊn chØnh Stack. - §o¸n nhËn x©u vµo cña PA ®îc thùc hiÖn theo 2 c¸ch: 1. X©u vµo ®îc ®äc xong vµ PA chuyÓn ®Õn mét tr¹ng th¸i kÕt thóc nµo ®ã. 2. X©u vµo ®îc ®äc xong vµ ng¨n xÕp trë thµnh rçng. ( Sau nµy ta sÏ thÊy râ 2 c¸ch tiÕp cËn trªn lµ t¬ng ®¬ng) - VÝ dô. Cho v¨n ph¹m G=({0,1,c},{S},S, P) víi P gåm c¸c luËt sinh: 1. S

0S0; 2. S

1S1; 3. S

c.

Ng«n ng÷ ®îc sinh ra bëi v¨n ph¹m nµy lµ L(G)={wcw’ w∈{0,1}*} Nã ®îc ®o¸n nhËn bëi automat ®Èy xuèng nh sau: - X©u wcw’ ®Æt trªn b¨ng vµo. - Ng¨n xÕp ë trn¹g th¸i rçng - §Çu ®äc chuyÓn tõng bíc tõ tr¸i qua ph¶i. - Automat chØ cã 2 tr¹ng th¸i q, p víi q lµ tr¹ng th¸i ®Çu. Qu¸ tr×nh ®o¸n nhËn wcw’ ®îc thùc hiÖn nh sau:

Bé m«n khoa häc m¸y tÝnh - HVKTQS

70

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

- ë tr¹ng th¸i q. ®äc ®îc ë b¨ng vµo ký hiÖu ®Çu tiªn cña w (0 hoÆc 1) vµ ®a ký hiÖu ®ã vµo ng¨n xÕp, vÉn ë tr¹ng th¸i q vµ ®Çu ®äc chuyÓn sang ký tù tiÕp theo. - Thùc hiÖn nh trªn víi mäi ký tù cßn l¹i cña w, khi ®ã ta nhËn ®îc trong Stack x©u w víi ký tù ph¶i nhÊt n»m trªn cïng. ChuyÓn ®Çu ®äc sang ký tù tiÕp theo. - GÆp ký tù c chuyÓn tr¹ng th¸i p vµ chuyÓn ®Çu ®äc sang ph¶i. - ë tr¹ng th¸i p ký hiÖu ®îc ®äc ë b¨ng vµo lµ 0 hoÆc 1 trïng víi ký tù n»m trªn ®Ønh Stack, loÞa ký tù ®ã khái ng¨n xÕp,gi÷ nguyªn tr¹ng th¸i p vµ chuyÓn ®Çu ®äc sang ph¶i - Qu¸ tr×nh kÕt thóc khi Stack rçng, còng lµ lóc ta ®äc xong x©u wcw’. - NhËn xÐt. Nhê ng¨n xÕp cã kh¶ n¨ng lu gi÷ mét sè bÊt kú c¸c ký hiÖu mµ PA ®Èy xuèng cã thÓ nhí ®îc x©u w cho dï nã cã ®é dµi bao nhiªu. Automat h÷u h¹n kh«ng cã kh¶ n¨ng nµy. b. Automat Push Down lµ mét bé M=(Q, T, Γ ,δ , q0, Z0, F) trong ®ã: - Q lµ tËp h÷u h¹n c¸c tr¹ng th¸i. - T lµ tËp h÷u h¹n c¸c c¸c phÇn tö lµ b¶ng ch÷ c¸i vµo -

Γ lµ tËp h÷u h¹n c¸c c¸c phÇn tö

lµ b¶ng ch÷ c¸i ®Èy

xuèng. -

q0 ∈ Q lµ tr¹ng th¸i ®Çu cña automat.

-

z0 ∈ Γ lµ ký hiÖu ®Æc biÖt cña b¨ng ®Èy xuèng gäi lµ ký hiÖu b¾t ®Çu, z0 xuÊt hiÖn ®Çu tiªn ë ®Ønh cña bé ®Èy xuèng.

-

F⊆Q lµ tËp tr¹ng th¸i kÕt thóc.

-

δ lµ ¸nh x¹ δ : Q x T∪{e}xΓ

Γ *

2Qx

Chó ý r»ng:

Bé m«n khoa häc m¸y tÝnh - HVKTQS

71

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

1. δ (q,a,Z)={(q1,γ 1), (q2,γ 2), (q3,γ 3),…, (qm,γ

m

)}, víi q,qi ∈ Q, a ∈

T,Z ∈ Γ , γ i ∈Γ * NghÜa lµ: Automat ë tr¹ng th¸i q nh×n thÊy ký hiÖu a ë b¨ng vµo, Z lµ ký hiÖu ë ®Ønh cña bé ®Èy xuèng, khi ®ã automat ®æi sang tr¹ng th¸i qi thay Z bëi x©u γ i vµ dÞch ®Çu ®äc sang ký hiÖu tiÕp theo, ta quy íc r»ng ký hiÖu tr¸i nhÊt cu¨ x©u γ

i

sÏ n»m ë trªn[®¸y]

vµ ký hiÖu ph¶i nhÊt ®Æt n»m ë ®¸y[®Çu ng¨n] cña Stack. 2. δ (q,e,Z)={(q1,γ 1), (q2,γ 2), (q3,γ 3),…, (qm,γ

m

)}, víi q,qi ∈ Q, Z ∈

Γ , γ i ∈Γ *. NghÜa lµ: Automat ë tr¹ng th¸i q kh«ng phô thuéc ký hiÖu vµo ®îc ®äc ký tù Z ë ®Ønh cña bé ®Èy xuèng, khi ®ã automat ®æi sang tr¹ng th¸i qi nµo ®ã víi i=1..m vµ Z ®îc ®æi sang γ

i

vµ ®Çu ®äc

®øng yªn. d. C¸c vÝ dô. M=(Q, T, Γ ,δ , q0, Z0,F) víi: Q={q1, q2}, T:={0,1,c}, Γ ={R,B,G},

q0=q1, Z0={R}, F=∅

δ : 1.

δ (q1,0,R)={(q1,BR)},

2.

δ (q1,0,B)={(q1,BB)},

3.

δ (q1,0,G)={(q1,BG)} 4.

δ (q1,c,R)={(q2,R)},

5.

δ (q1,c,B)={(q2,B)},

6.

δ (q1,c,G)={(q2,G)} 7. δ (q2,0,B)={(q2,e)}, 9.

8. δ (q1,e,R)={(q2,e)},

δ (q1,1,R)={(q1,RG)}

10.

δ (q1,1,B)={(q1,GB)}

11.

δ (q1,1,G)={(q1,GG)} 12. δ (q2,1,G)={(q2,e)}

Bé m«n khoa häc m¸y tÝnh - HVKTQS

72

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

VÝ dô 2. Cho M:=({q1,q2},{0,1},{Z,0,1},δ , Z, ∅}, víi c¸c hµm chuyÓn nh sau: 1. δ (q1,0,Z)={(q1,0)}, 2. δ (q1,1,Z)={(q1,1)}, 3. δ (q1,0,0)={(q1,00), (q2,e)} δ (q1,0,1)={(q1,10)},

4.

δ (q1,1,0)={(q1,01)},

5.

6.δ (q1,1,1)={(q1,11),(q2,e)} 7. δ (q2,0,0)={(q2,e)}, 8. δ (q2,1,1)={(q2,e)}, 9. δ (q1,1,Z)={(q2,e)} 10. δ (q2,e,Z)={(q2,e)}.

4.2.

Ng«n

ng÷

®o¸n

nhËn

bëi

automat

Pushdown(PA). a. H×nh tr¹ng cña PA. + Ta nãi h×nh tr¹ng cña PA lµ cÆp (q, γ ),q∈Q, γ ∈Γ * nÕu M ë tr¹ng th¸i q,γ

n»m trªn Stack víi ký hiÖu tr¸i nhÊt n»m trªn

®Ønh [®¸y] Stack. NÕu a∈T∪{e}; γ , β ∈ Γ *; Z∈Γ vµ nÕu (p, β ) ∈ δ (q,a,Z) khi ®ã ta viÕt nh sau: a:(q,Zγ ) ⇒(p, β γ ) [ a:(q,γ Z) ⇒(p, β γ ) vµ ®äc lµ automat ë h×nh tr¹ng (q,Zγ ) khi nh×n thÊy ký hiÖu vµo a nã chuyÓn sang tr¹ng th¸i (p, β γ ). + §èi víi x©u w=a1a2...an nÕu ai: (qi,γ i) ⇒(qi+1, γ

i+1

) khi ®ã ta

viÕt: w: (q1,γ 1) *⇒(qn+1, γ

n+1

)

Bé m«n khoa häc m¸y tÝnh - HVKTQS

73

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

+ Quy íc e:(q,γ ) ⇒(q, γ ) b. NhËn xÐt. ë mçi thêi ®iÓm, t×nh tr¹ng cña PA x¸c ®Þnh nhê 3 yÕu tè: - X©u γ ∈ Γ * trong ng¨n xÕp( víi ký hiÖu bªn tr¸i nhÊt n»m ë ®¸y[®Ønh] - Tr¹ng th¸i q∈ Q - PhÇn x©u cha ®äc ®Õn x∈ T*(víi ký hiÖu bªn tr¸i nhÊt lµ ký hiÖu sÏ ®îc ®äc tiÕp). x

q γ ( PA trong trêng hîp ký hiÖu tr¸i nhÊt n»m ë ®¸y) c. Ng«n ng÷ ®o¸n nhËn bëi PA. + Cho automat Pushdown M=(Q, T, Γ ,δ , q0, Z0, F) ta nãi ng«n ng÷ ®o¸n

nhËn bëi M lµ tËp:

U(M):={w ∈ T*| w :(q0,Z0) *⇒(q, γ ), q∈F, γ

∈ Γ *}.

+ Cho automat Pushdown M=(Q, T, Γ ,δ , q0, Z0, F) ta nãi ng«n ng÷ ®o¸n nhËn bëi M lµ tËp: N(M):={w ∈ T*| w :(q0,Z0)* ⇒(q, e), q∈Q}. + Chó ý r»ng 2 ®Þnh nghÜa trªn kh¸c nhau ë chç mét dùa vµo tr¹ng th¸i kÕt thóc, mét dùa vµo viÖc vÐt rçng Stack. VÝ dô. Cho M:=({q1,q2},{0,1},{Z,0,1},δ , Z, ∅}, víi c¸c hµm chuyÓn nh sau: 1. δ (q1,0,Z)={(q1,0)}, 2. δ (q1,1,Z)={(q1,1)}, 3. δ (q1,0,0)={(q1,00), (q2,e)}

Bé m«n khoa häc m¸y tÝnh - HVKTQS

74

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

4.

δ (q1,0,1)={(q1,10)},

5.

δ (q1,1,0)={(q1,01)},

6.δ (q1,1,1)={(q1,11),(q2,e)} 7. δ (q2,0,0)={(q2,e)}, 8. δ (q2,1,1)={(q2,e)}, 9. δ (q1,1,Z)={(q2,e)} 10. δ (q2,e,Z)={(q2,e)}. - Tõ quy t¾c 1-6 cho phÐp M nhí c¸c ký hiÖu ®äc vµo ng¨n xÕp. - Trong quy t¾c 3,6 M cã thÓ tuú chän gi÷a 2 bíc chuyÓn, chän bíc chuyÓn thø 2 khi cho r»ng ®· ®¹t ®iÓm chÝnh gi÷a cña x©u vµo. - Trong trêng hîp ®ã nã chuyÓn sang tr¹ng th¸i q2 vµ b¾t ®Çu so s¸nh phÇn x©u cßn l¹i trªn b¨ng vµo víi x©u trong ng¨n xÕp nhê c¸c quy t¾c 7 vµ 8. - NÕu x©u vµo cã d¹ng ww’ th× M cã kh¶ n¨ng ®äc hÕt x©u vµ nã xo¸ nèt Z bëi quy t¾c 10 ®Ó thõa nhËn x©u ®ã theo kiÓu ng¨n xÕp rçng. - Quy t¾c 9 cho phÐp thõa nhËn x©u rçng. e. Automat tiÒn ®Þnh. Automat Pushdown M=(Q, T, Γ ,δ , q0, Z0,F) ®îc gäi lµ tiÒn ®Þnh nÕu tho¶ m·n c¸c ®iÒu kiÖn sau: 1. ∀q∈Q, Z ∈ Γ nÕu δ (q,e,Z)≠∅ th× δ (q,a,Z)= ∅ víi mäi a ∈ T. 2. Kh«ng tån t¹i q ∈ Q, Z∈ Γ , a ∈ T∪{e} ®Ó | δ (q,a,Z) | >1. f. NhËn xÐt. - §iÒu kiÖn 1 kh«ng cho phÐp ®æi tr¹ng th¸i gièng nhau gi÷a tõ rçng vµ ký hiÖu vµo. - §iÒu kiÖn 2 kh«ng cho phÐp ®æi h×nh tr¹ng gièng nhau gi÷a (q,e,Z) vµ (q,a,Z). VÝ dô. M=(Q, T, Γ ,δ , q0, Z0, F) víi: Q={q1, q2}, T:={0,1}, Γ ={R,B,G},

q0={q1}, Z0=R, F=∅

Bé m«n khoa häc m¸y tÝnh - HVKTQS

75

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

δ : δ (q1,0,R)={(q1,BR)},

1.

2.

δ (q1,1,R)={(q1,GR)},

3.

δ (q1,0,B)={(q1,BB)} 4. δ (q1,0,G)={(q1,BG)},

5. δ (q1,1,B)={(q1,GB)},

6. δ (q1,1,G)={(q1,GG),(q2,e)} 7. δ (q2,0,B)={(q2,e)},

8. δ (q2,1,G)={(q2,e)},

9. δ (q1,e,R)={(q2,e)} 10. δ (q2,e,R)= {(q2,e)} Ta dÔ dµng thÊy M lµ automat ®Èy xuèng kh«ng tiÒn ®Þnh. MÆt kh¸c, ta cã thÓ chøng minh ®îc N(M)={ww’ | w ∈ {0,1}*}. VÝ dô tõ x©u: 001100 ta cã b¶ng chuyÓn ®æi sau:(Xem b¶ng ë trang sau)

TÝn

hiÖu C¸c h×nh tr¹ng nhËn ®îc

vµo e

(q1,R)

(q2,e) {vËy e ∈ N(M)}

0 (q1,BR) 00 (q1,BBR) 001 (q1,GBBR) 0011 (q1,GGBBR)

(q2,BBR)

Bé m«n khoa häc m¸y tÝnh - HVKTQS

76

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

00110 (q1,BGGBBR)

(q2,BR)

001100 (q1,BGGBBR)

E

(q2,R)

(q2,e)

4.3. C¸c ®Þnh lý vÒ automat Pushdown. a. §Þnh lý 3.6. Tån t¹i ng«n ng÷ ®o¸n nhËn ®îc bëi automat PA kh«ng tiÒn ®Þnh nhng kh«ng tån t¹i automat Pushdown tiÒn ®Þnh ®o¸n nhËn nã. b. §Þnh lý 3.7. Líp c¸c ng«n ng÷ ®o¸n nhËn ®îc bëi automat PA kh«ng tiÒn ®Þnh b»ng tr¹ng th¸i kÕt thóc trïng víi líp ng«n ng÷ ®o¸n nhËn ®îc bëi automat ®Èy xuèng víi b¨ng ®Èy rçng U(M)=N(M). c. §Þnh lý 3.8. Cho v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) khi ®ã tån t¹i automat PA M sao cho L(G)=N(M). Chøng minh. Gia sö G=(N, T, s, P) la v¨n ph¹m phi ng÷ c¶nh ta coi nã ®· ®îc biÕn ®æi vÒ d¹ng chuÈn Greibach, kh«ng gi¶m tæng qu¸t ta coi e ∈ L(G). X©y dùng M=({q1}, T, N, s, δ , q1,∅) ( Q:={q1}, T:=T, Γ :=N, Z0:=s, F:= ∅) - Hµm chuyÓn x¸c ®Þnh nh sau: δ (q1,a,A):={(q1, γ )  víi ®iÒu kÞÖn A - NhËn thÊy r»ng:

xAβ

xaα β

aγ ∈ P}

⇔ a: (q1,Aβ )⇒(q1,α β ) víi A∈N;

α ,β ∈ N*. xaα β

ThËt vËy, xAβ

⇔ A

aα nghÜa lµ (q1,α )∈ δ (q1,a,A)

theo ®Þnh nghÜa suy ra a: (q1,Aβ )⇒(q1,α β ). - NÕu w∈L(G)⇔∃s

*

w⇔∃ s

w1A1α

1

w1w2A2α

2

w1w2w3A3α 3...

Bé m«n khoa häc m¸y tÝnh - HVKTQS

77

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

w1w2w3...wn-1An-1

w1w2w3...wn-1wnAn

w1w2w3...wn-1wn ⇔

w1:(q1,s)⇒(q1,α 1); w2:(q1,A1α 1)⇒(q1,A2α 2); ...; wn-1:(q1,An-1α

n-1

)⇒(q1,An)

wn:(q1,An)⇒(q1,e). VËy w=w1w2w3...wn-1wn:(q1,s) *⇒(q1,e), do qu¸ tr×nh trªn lµ t¬ng ®¬ng nªn suy ra L(G)=N(M). c. §Þnh lý 3.9. Cho automat PA M==(Q, T, Γ ,δ , q0, Z0,F) khi ®ã tån t¹i v¨n ph¹m phi ng÷ c¶nh G=(N, T, s, P) sao cho ng«n ng÷ ®o¸n nhËn ®îc bëi automat PA trïng víi ng«n ng÷ ®o¸n nhËn ®îc bëi v¨n ph¹m G. Chøng minh. Tõ ®Þnh lý 3.7 ta cã thÓ coi F=∅ ta x©y dùng G nh sau: - N:={[q,A,p]p,q∈Q ∧ A∈}∪{s}( s lµ ký hiÖu míi) - P gåm c¸c quy t¾c sau: [q0, Z0, q], q0 ∈Q; ∀q∈Q;

1. s

2. [q, A, p]

a[q1, B1, q2][q2, B2, q3]...[qm, B1, qm+1] nÕu

(q1,B1...Bm)∈ δ (q,a,A) hay lµ a: (q,A) ⇒(q1,B1...Bm); qi ∈Q; A,Bi∈ Γ NhËn thÊy r»ng nÕu m=0 khi ®ã stack rçng nªn q1=p do ®ã (p,e))∈ δ (q,a,p) v× vËy trong G cã quy t¾c [q,A,p]

a.

Gi¶ sö w∈L(G) nghÜa lµ tån t¹i d·y dÉn xuÊt s *

w nªn theo tËp

quy t¾c võa x©y dùng ta cã s

[q0, Z0, q] *

w ⇔w:(q0,Z0) ⇒ (q,e) v× thÕ w∈ N(M)

$5. M¸y Turing. 5.1. LÞch sö ph¸t triÓn vµ m« t¶ m¸y Turing. a. LÞch sö ph¸t triÓn. Vµo gi÷a nh÷ng n¨m 30 cña thÕ kû tríc c¸c nhµ Khoa häc nh Godel, Kleene, Church, Turing cè g¾ng ®a ra c¸c kh¸i niÖm to¸n häc cho thuËt to¸n. Trong sè c¸c kh¸i niÖm ®îc ®a ra th× cña Turing ®îc thõa nhËn réng r·i h¬n c¶ bëi nã thuËn tiÖn

Bé m«n khoa häc m¸y tÝnh - HVKTQS

78

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

cho viÖc nghiªn cøu c¸c vÊn ®Ò lý thuyÕt vµ øng dông ®ã lµ dïng kh¸i niÖm m¸y Turing ®Ó m« t¶ kh¸i niÖm thuËt to¸n, h¬n thÕ n÷a sau khi xuÊt hiÖn m¸y tÝnh ®iÖn tö, m¸y Turing ®· trë thµnh m« h×nh to¸n häc cho c¸c m¸y tÝnh thùc tÕ. b. ThuËt to¸n vµ luËn ®Ò Turing-Church. Lµ mét d·y h÷u h¹n c¸c biÕn ®æi s¬ cÊp nh»m thùc mét nhiÖm vô cô thÓ nµo ®ã. Trong m« h×nh m¸y Turing ngêi ta chØ dïng mét lo¹i biÕn ®æi s¬ cÊp ®¬n gi¶n lµ thay mét ký hiÖu nµy b»ng mét ký hiÖu kh¸c do ®ã cã thÓ ®ång nhÊt c©u hái cã hay kh«ng mét thuËt to¸n gi¶i mét bµi to¸n nµo ®ã víi cã hay kh«ng m¸y Turing tÝnh nã. Trªn c¬ së lý thuyÕt thuËt to¸n Turing vµ Church ®· nªu ra luËn ®Ò sau: Mäi hµm sè tÝnh ®îc theo nghÜa trùc gi¸c ®Òu tÝnh ®îc bëi mét m¸y Turing tÝnh nã. MÆc dï luËn ®Ò nµy ®Õn nay vÉn cha ®îc chøng minh nhng ngêi ta vÉn kh«ng t×m ®îc ph¶n vÝ dô phñ ®Þnh nã. d. M« t¶ m¸y Turing. M¸y Turing gåm: - Mét ®Çu ®äc – viÕt: Gåm mét automat h÷u h¹n tr¹ng th¸i vµ mét bé ®iÒu khiÓn b¨ng. - Mét b¨ng dµi “v« h¹n tiÒm n¨ng” vÒ 2 phÝa trªn b¨ng nµy ®îc chia thµnh tõng «, mçi « cã thÓ ghi mét tÝn hiÖu. M¸y Turing ®îc ®iÒu khiÓn b»ng mét ®ång hå ch÷, ë mét khëi ®iÓm bÊt kú, ®Çu ®äc ®äc tÝn hiÖu trªn b¶ng ch÷. TÝn hiÖu ®îc ®äc nµy lµ tÝn hiÖu vµo cña automat ®Çu ®äc vµ t¹i thêi ®iÓm ®ã automat thay ®æi tr¹ng th¸i råi cho ra mét tÝn hiÖu nã ®îc viÕt trªn b¨ng ®Ì lªn tÝn hiÖu cò. §ång thêi bé ®iÒu khiÓn thùc hiÖn mét trong 3 thao t¸c sau: - ChuyÓn ®Çu ®äc vÒ bªn ph¶i 1 « - ChuyÓn ®Çu ®äc vÒ bªn tr¸i 1 « - Dõng m¸y

Bé m«n khoa häc m¸y tÝnh - HVKTQS

79

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

Chó ý r»ng ®Çu ®äc cã thÓ di chuyÓn vÒ c¶ 2 phÝa.  0  1  0  1  1  0  0 1 

Bé ®iÒu khiÓn Automat hh

5.2. C¸c kh¸i niÖm c¬ b¶n. a. §Þnh nghÜa m¸y Turing. M¸y Turing lµ mét bé T=(S, Σ , δ , q0) trong ®ã: - Q lµ tËp h÷u h¹n c¸c tr¹ng th¸i. - X lµ tËp h÷u h¹n c¸c ký hiÖu vµo. - δ :Q x X’ x{L,R,H}

QxX’ lµ hµm chuyÓn tr¹ng th¸i, trong

®ã Q’={Q,e}. Hµm chuyÓn thêng cho díi d¹ng bé 5 sau: qx

q’yd trong ®ã d ∈{L,R,H} vµ gäi nã lµ lÖnh m¸y( v× lµ

lÖnh m¸y nªn ®iÒu kiÖn lµ 2 lÖnh kh¸c nhau cïng chung vÕ tr¸i) - L, R ký hiÖu chØ híng dÞch chuyÓn sang tr¸i hoÆc sang ph¶i cña ®Çu ®äc. δ (s,a,M)= (q,b) cã nghÜa lµ m¸y ë tr¹ng th¸i s, ®Çu ®äc ®ang trá vµo a m¸y ®æi sang tr¹ng th¸i q, thay a bëi b vµ di chuyÓn ®Çu ®äc theo híng M. - qo lµ tr¹ng th¸i b¾t ®Çu cña m¸y Turing. a. Ho¹t ®éng cña m¸y Turing. - Ký hiÖu e lµ ký hiÖu rçng. Mét « ®îc ghi ký hiÖu e cã nghÜa lµ kh«ng ghi g× c¶, viÖc ghi e thay cho x nghÜa lµ xãa x. - C¸c sè liÖu ban ®Çu ®îc ghi trªn b¨ng tríc khi m¸y b¾t ®Çu ho¹t ®éng vµ sau khi t¾t m¸y ta còng ®äc kÕt qu¶ trªn b¨ng.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

80

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

- Mét chuçi d¹ng:

CqD víi q∈Q, c∈X*, D∈X’+ gäi lµ mét h×nh

tr¹ng cña m¸y nÕu: + Trªn b¨ng cã tõ cD + §Çu ®äc ë tr¹ng th¸i q. C

q

D

Bé ®iÒu khiÓn Automat hh

c. ChuyÓn h×nh tr¹ng. Gi¶ sö ∝, β lµ 2 h×nh tr¹ng cña m¸y M. Ta nãi M chuyÓn trùc tiÕp tõ h×nh tr¹ng ∝ sang h×nh tr¹ng β vµ ký hiÖu M: ∝

β nÕu xÈy ra mét trong c¸c trêng hîp sau:

1. ∝= CqxD, β =CqyD (qx

q’yH)

2. ∝= Cqx1x2D, β =Cyq’x2D (qx1

q’yR)

3. 4. ∝= Cqx, β =Cyq’e (qx

q’yR)

5. ∝= Cx1qx2D, β =Cyq’x1yD (qx1 6. qxD, β =q’eyD (qx

q’yL)

q’yL)

Ta cã thÓ m« t¶ c¸c trêng hîp trªn nh sau: C x D

C

q

q’

C x 1 x2 D q

y D

C y x2 D q’

Bé m«n khoa häc m¸y tÝnh - HVKTQS

81

Vâ Minh Phæ – C¸c bµi gi¶ng ng«n ng÷ h×nh thøc vµ ¤t«mat

C¸c trêng hîp kh¸c t¬ng tù. c. ChuyÓn nhiÒu bíc. Ta nãi ∝ chuyÓn nhiÒu bíc ®Õn β ký hiÖu lµ ∝⇒ β nÕu tån t¹i ∝=∝1,∝2,∝3,...,∝n= β sao cho ∝i

∝i+1 víi

i=1..n-1.

Bé m«n khoa häc m¸y tÝnh - HVKTQS

82