Đề 1

Câu 1 (3điểm):

a)Cho biết ngôn ngữ sinh bởi văn phạm G:=(N,T,S,P) với các sản xuất trong P

P: s-> aSa/aa với a T,T={0,1,2}

Đây là văn phạm loại nào trong phân loại văn phạm của Chomsky.

b) Hãy xác định loại văn phạm mà anh chị vừa xác nhận ở câu a)

Câu 2(4đ):

a)xây dựng ôtomata hữu hạn đoán nhận xâu chỉ chứa số 0,1 và chẵn lần số 0.Xâu w=01101 có thuộc ôtomát vừa xây dựng không?tại sao?

b) Cho văn phạm G=(N,T,S,P) với tập các sabr xuất trongP như sau:

P: S-> 1A / 0B

A->0S / 0

B ->1S /1

Hãy xây dựng ôtomát đoán nhận ngôn ngữ sinh bởi văn phạm này và kiểm nghiệm xâu w= 11010 có đượcđoán nhận bởi FA vừa xây dựng không?

c) xây dựng ôtomát hữu hạn nhận biểu thức chính quy sau r=(10+1)*

Câu 3(3đ):

Cho văn phạm G=(N,T,S,P) với các sản xuất

P: S->bA/aB/B

A->bAA /aS /b

B-> bBB /ABC/a

Hãy đưa văn phạm về dạng chuẩn ChomSky.

Giai

Câu 1

Đây là văn phạm phi ngữ cảnh.

B, văn phạm phi ngữ cảnh là văn phạm có:

M(N, , S,R)

N là tập các kí hiệu ko kết thúc

là bảng chữ cái vào

S là biến đầu

R:các luật sinh đều có dạng: A

Trong đó A là kí hiệu ko kết thúc. là kí hiệu kết thúc

Câu 2 a, xd automat

Automat trên sẽ có dạng:

M(N, , S,R)

N={p0,p1}

={0,1}

S={p0}

R: (p0,1)=p0

(p0,0)=p1

(p1,1)=p1

(p1,0)=p0

B, kiểm tra xâu w= 11010 có thuộc automat

(p0,11010)= (p0,1010)= (p0,010)= (p1,10)= (p1,0)=p0

Vì p0 là trạng thái kết thúc. Nên xâu W đc đón nhận bởi automat

{thực ra câu a phải diễn giải tại sao lại vẽ dc . Nhưng tôi ko biết phải nói thế nào cả}

b) Cho văn phạm G=(N,T,S,P) với tập các sabr xuất trongP như sau:

P: S-> 1A / 0B

A->0S / 0

B ->1S /1

Hãy xây dựng ôtomát đoán nhận ngôn ngữ sinh bởi văn phạm này và kiểm nghiệm xâu w= 11010 có đượcđoán nhận bởi FA vừa xây dựng không?

b, xd NFA

NFA cần xd là 1 bộ M(Q, , ,q0,F)

Trong đó: q0 là trạng thái ban đầu =S

là bảng chữ cái vào ={0,1}

Ban đầu: Q=N={S,A,B}

S-> 1A (S,1)=A Q={S,A,B}

S-> 0B (S,0)=B Q={S,A,B}

A->0S (A,0)=S Q={S,A,B}

A->0 (A,0)=C {them moi} Q={S,A,B,C}

B ->1S (B,1)=S Q={S,A,B,C}

B ->1 (B,1)=D {them moi} Q={S,A,B,C,D}

Trang thái kết thúc F={C,D} là cái thêm mới

kiểm nghiệm xâu w= 11010 có đượcđoán nhận bởi FA vừa xây dựng không?

(S,11010) = (A,1010)

Ko có dịch chuyển (A,1) vì vậy đầu đọc ko dịch chuyển dc tiếp. Đầu đọc đứng yên. Xâu W ko dc đón nhận bởi FA này

c) xây dựng ôtomát hữu hạn nhận biểu thức chính quy sau r=(10+1)*

ta có

r=r1*

với r1=10+1 =r2+r3

với r3=1

r2=10= r3r4

r3=1

R4= 0

R2=r3r4

R1=r2+r3

R=r1*

Câu 3(3đ):

Cho văn phạm G=(N,T,S,P) với các sản xuất

P: S->bA/aB/B

A->bAA /aS /b

B-> bBB /ABC/a

Hãy đưa văn phạm về dạng chuẩn ChomSky.

B1: loại bỏ tất cả các biến vô ích , luật sinh , luật sinh đơn vị

- loại bỏ biến vô ích;

+ loại bỏ ki hiêu ko kết thúc:

Vì A->b

B-> a

C là kí hiệu ko kết thúc. Vì C ko suy dc ra ki hiệu kết thúc.

Tập luật còn lại:

P: S->bA/aB/B

A->bAA /aS /b

B-> bBB /a

+ loại bỏ kí hiệu ko đến đựoc: ko có

- loại bỏ luật sinh ko có

- loại bỏ luật sinh đơn vị:

có luật sinh đơn vị: S->B

Tập luật có dạng:

P: S->bA/aB/bBB/a

A->bAA /aS /b

B-> bBB /a

B2 đưa về dạng chuẩn: các luật sinh phải có dạng: B-> AC /a

- các luật sinh đã ở dạng chuẩn:

S->a

A->b

B-> a

- các luật chưa ở dạng chuẩn:

S->bA/aB/bBB

A->bAA /aS

B-> bBB

Đặt: Cb->b

Ca-> a

Các luật mới có dạng:

S->CbA/CaB/CbBB

A->CbAA /CaS

B-> CbBB

Các luật chuẩn mới là:

S->CbA/CaB

A->CaS

Các luật chưa chuẩn là:

S->CbBB

A->CbAA

B-> CbBB

Tiếp tục chuẩn hoá:

Xét luật: S->CbBB S->CbD1

D1->BB

B-> CbBB B->CbD1

A->CbAA A->CbD2

D2->AA

Vậy tập các luật sau khi chuẩn hoá là:

S->CbA/CaB/CbD1/a

A->CbD2 /CaS /b

B-> CbD1 /a

Cb->b

Ca->a

D1->BB

D2->AA