Báo Cáo Đồ Án
Môn Automata
Đề tài: Chuyển từ một NPDA sang một văn phạm phi ngữ cảnh
Giáo viên hướng dẫn: Hà Chí Trung
Sinh viên thực hiện: Phùng Chí Hiếu
Lớp: Tin Học 6B
Khoa: Công Nghệ Thông Tin.
Trường: Học Viện Kỹ Thuật Quân Sự
Chuyển từ một NPDA sang một văn
phạm phi ngữ cảnh.
I.Lý thuyết:
Bổ đề 7.1 : Với mọi npda luôn có một npda tương ứng thỏa mãn hai điều
kiệu sau:
1.Chỉ có 1 trạng thái kết thúc và npda kết thúc khi stack rỗng.
2.Mọi chuyển trạng thái đều có dạng:
δ(qi,a,A)={c1,c2, ,cn}
trong đó:
ci={qj,λ) (7.5)
hoặc:
ci=(qj,BC) (7.6)
tức là 1 di chuyển hoặc tăng hoặc giảm stack 1 ký hiệu đơn
Bây giờ ta sẽ đi vào chứng minh bổ đề 7.1 bằng cách xây dựng một NPDA tương
đương thỏa mãn 2 điều kiện trên.
-Điều kiện 1:
Giả sử một NPDA có nhiều hơn một trạng thái kết thúc qi,qj,qk Ta chuyển hết
tất cả các trạng thái kết thúc qj,qk về trạng thái kết thúc qi khi stack rỗng. Điều
này tương đương với việc thêm các chuyển dịch delta như sau vào δ(qj, λ,z)-
>(qi,z),
δ(qj,λ,z)->(qk,z), với qi là trạng thái kết thúc đầu tiên và qj, qk là các trạng thái
kết thúc còn lại. Sau đó ta gán lại cho qj, qk thành các trạng thái không kết thúc.
Điều kiện 1 đã thỏa.

- Với các chuyển dịch (7.5) ta sẽ sinh ra luật sinh tương ứng:
(qiAqj)->a.
- Còn với các chuyển dịch có dạng (7.6) thì sẽ có tập luật sinh:
(qiAqj)->a(qjBql)(qlCqk) trong đó ql và qk là những trạng thái có thể lấy
được trong tập Q (q0 qn).
- Cuối cùng ta lấy (q0zqf) là biến bắt đầu của văn phạm với qf là biến kết
thúc đơn của NPDA.
*Bước cuối cùng của thao tác này là loại bỏ những luật sinh vô dụng. Các bước
như sau:
B1: Đầu tiên ta tạo một tập biến hữu dụng BHD là những biến (qiAqj) có dạng:
(qiAqj)->a.
B2: Đối với những luật sinh (qiAqj)->a(qjBql)(qlCqk) với (qiAqj) là biến không thuộc
tập biến hữu dụng BHD nhưng (qjBql),(qlCqk) thuộc BHD thì thêm (qiAqj) vào.
B3: Lặp bước 2 cho đến khi không thể thêm phần tử nào vào được.
B4:Đối với mỗi luật sinh (qiAqj)->a(qjBql)(qlCqk) mà (qiAqj) hoặc (qjBql) hoặc
(qlCqk) không thuộc tập BHD thì bỏ loại bỏ luật sinh đó (thực ra chỉ cần xét (qiAqj)
có thuộc tập BHD không thôi vì nếu (qjBql) và (qlCqk) đều thuộc BHD thì (qiAqj)
cũng thuộc tập này).
Như thế ta được Văn phạm G tương đương với NPDA M đã cho.
II.Cài đặt:
Việc cài đặt chương trình thực chất là biến những bước chơ bản trên thành
code:
Lớp NPDA: Dựa vào các thông số của NPDA, làm nó thỏa mãn điều kiện 1 và 2
(bao gồm 7.5 và 7.6 nếu nó chưa thỏa) và chuyển nó sang Văn phạm bằng
phương thức toVP.
Q: Số trạng thái tối đa của npda
Xichma: Các ký tự gõ nhập
Gama: Các ký tự chứa trong stack
Delta: Hàm chuyển
V: Văn phạm sinh

for (int i=0; i<dcnt; i++) {
String tam=delta.get(i);
//neu thoa dieu kien
if (tam.endsWith(",~)")) //dang 1 (7.5)
continue;
if (tam.substring(tam.lastIndexOf(",")).length()==4) //dang 2 (7.6)
continue;
//Khong thoa man
delta.remove(i);
dcnt ;
i ;
//Truong hop thay doi 1 ky tu tren dinh stack (ko thay doi so ky tu trong
stack)
if (tam.substring(tam.lastIndexOf(",")).length()==3) {
//Tao them 1 trang thai trung gian.
q_++;
//Lay ham chuyen dich
String tam2=tam.substring(0,tam.indexOf(">>"));
//Lay trang thai can chuyen den
String tam3=tam.substring(tam.indexOf(">>"));
String tam4=tam3.substring(2,tam3.indexOf(","));
//Lay bien can thay the
String bien=tam3.substring(tam3.indexOf(",")+1,tam3.length()-1);
delta.add(tam2+">>(q"+q_+","+bien+bien+")");
delta.add("d(q"+q_+",~,"+bien+")>>"+tam4+",~)");
continue;
}
//Truong hop thay tren dinh stack nhieu hon 2 ky tu (them nhieu hon 1 ky
tu vao stack)
if (tam.substring(tam.lastIndexOf(",")).length()>=4) {

kq.setT(xichma+"~");
//Lam NPDA thoa dieu kien 1
this.thoadieukien1();
//Lam NPDA thoa dieu kien 2
this.thoadieukien2();
//Doi voi cac ham delta
for (int i=0; i<delta.size(); i++) {
String tam=delta.get(i);
if (tam.endsWith(",~)")) { //Ham delta o dang 7.5
//Lay qi
String qi=tam.substring(2,tam.indexOf(","));
//Lay qj
String tam2=tam.substring(tam.indexOf(">>")+2);
String qj=tam2.substring(1,tam2.indexOf(","));
//Lay ky tu chuyen a
String kta=String.valueOf(tam.charAt(tam.indexOf(",")+1));
//Lay bien dinh Stack A
String bentrai_npda=tam.substring(0,tam.indexOf(">>"));
String bienA=bentrai_npda.substring(bentrai_npda.lastIndexOf(",")+1,
bentrai_npda.lastIndexOf(")"));
String vetrai_ls="("+qi+bienA+qj+")";
String vephai_ls[]=new String[1];
vephai_ls[0]=kta;
kq.addP(vetrai_ls, vephai_ls);
continue;
}
//Cac truong hop con lai la ham delta o dang 7.6
//se duoc them vao o vong lap sau (cho de nhin)
}
//Vong lap them cac truong hop o 7.6

for (int i=0; i<=q_; i++)
if (F[i]) {
luu=i;
break;
}
kq.S="(q0zq"+luu+")";
return kq;
}
}
Lớp luật sinh luatsinh: Mô tả cấu trúc cơ bản của 1 luật sinh gồm 2 vế trái, phải
với vế trái là 1 biến và vế phải là một tập thuộc (V
∪
T)*.
public class luatsinh {
public String vetrai="";
public ArrayList<String> vephai=new ArrayList();
}
Lớp văn phạm VP: Văn phạm được sinh ra là văn phạm tồn tại với những luật
sinh vô dụng. Ở đây có phương thức loại bỏ những luật sinh vô dụng và được
văn phạm rút gọn tương đương
public class VP {
public String T="";
public ArrayList<String> V=new ArrayList();
public String S="";
public ArrayList<luatsinh> P=new ArrayList();

public VP() {}
public void setT(String T) {
this.T=T;
}

String bien=ls.vetrai;
//bien do nam trong tap roi thi bo qua
if (bienhuudung.contains(bien)) continue;
//neu la bien huu dung thi them vao
if ((bienhuudung.contains(ls.vephai.get(1)))&&
(bienhuudung.contains(ls.vephai.get(2)))) {
flag=true;
bienhuudung.add(bien);
}
}
if (!flag) break;
}
//Loai bo cac luat sinh vo dung
//Cac luat sinh goi la vo dung khi ve ben phai trai
//hoac ve ben phai ton tai bien vo dung
for (int i=luu; i<P.size(); i++) {
luatsinh ls=P.get(i);
//neu ve ben trai la bien vo dung
if (!bienhuudung.contains(ls.vetrai)) {
P.remove(i);
i ;
continue;
}
//neu ve ben phai la bien vo dung
if ((!bienhuudung.contains(ls.vephai.get(1)))
||(!bienhuudung.contains(ls.vephai.get(2)))) {
P.remove(i);
i ;
continue;
}