Gian luoc van phan:

S->aBA|baB|bc

A->BS|bA|a

B->aS|aB

C->aB|BB

E->ca

--------Loai ky hieu

W0={S}

W1={S,a,B,A,b,c}

//tu S,B,A xet cac sx tu S,B,A

W2={S,a,B,A,b,c} U Ø

W=W1={S,a,B,A,b,c}

Σ ‘ = W∩ Σ={a,b,c}

Δ ‘=Δ∩W={S,A,B}

--------Cac sx trong P’

Chua lam

-------Tim ngon ngu chuan doan boi OH

Hinh ve

A=ε +Aa+Bb+Ca

B=Ab

C=Ba

A= ε+Aa+Abb+Abaa

= ε+A(a+bb+baa)

= ε(a+bb+baa)*

=>C=(a+bb+baa)*ba

=((a+bb)*(baa)*)*ba

=((a*(bb)*)*(baa)*)*ba

L(M)={((an1(bb)n2)n3(baa)n4)n5ba

(n1,n2…n5>=0)

------Tim BTCQ tuong ung O

q0= ε+q11+q20 (1)

q1=q00 (2)

q2=q01 (3)

q3=q10+q21+q3(0,1)

Thay(2)(3) vao (1)

q0= ε+q001+q010

= εq0(01+10)

q0= ε(01+10)*

Vay BTCQ tuong ung O la (01+10)*

------NNCQ=>VPCQ phai

G=( Σ, Δ,P,S)

Σ={0,1}

Δ={q1,q2,q3,q4}

S=q0

Hinh ve

q0->0q1|1q2

q1->1q0|1q3|1

q2->0q0|0q3|0

q3->0q3|1q3