fao auto mat 1

  • Đề 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