Đồ án Automata và NNHT
Contents
I. Đặt vấn đề
Mục đích của bài toán:
Từ 1 NPDA cho trước viết chương trình biến đổi NPDA đó về văn phạm phi
ngữ cảnh( CFG) sao cho CFG đó sinh ra ngôn ngữ được chấp nhận bởi NPDA đã
cho.
Các vấn đề mà đề tài cần giải quyết:
1
Đồ án Automata và NNHT
- Từ 1 NPDA cho trước ta đưa về 1 NPDA tương đương chỉ có 1 trạng thái kết
thúc và NPDA kết thúc khi stack rỗng. (1)
- Đưa tất cả các hàm chuyển về dạng:
δ(q
i
,a, A) (q
j
, λ) , hoặc: (2)
δ(q
i
,a, A) (q
j
, BC)
- Sau đó chuyển NPDA về văn phạm phi ngữ cảnh (CFG).
II. Cơ sở lý thuyết
Bổ đề 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:
δ(q
i

tất cả các trạng thái kết thúc q
j
, q
k
về trạng thái kết thúc q
i
khi stack rỗng. Điều
này tương đương với việc thêm các chuyển dịch lamda như sau vào δ(q
j
, λ, z) ->
( q
i
, z), δ( q
k
, λ, z) -> (q
i
, z), với q
i
là trạng thái kết thúc đầu tiên và q
j
, q
k
là
các trạng thái kết thúc còn lại. Sau đó ta gán lại cho q
j
, q
k
thành các trạng thái
không kết thúc. Điều kiện 1 đã thỏa.
2

chuyển sang q
t
.
δ(q
t
, λ, B)->(q
j
, λ) //Từ q
t
, không cần nhận ký tự nào từ ngõ nhập và
đỉnh Stack lúc này là B. Ta bỏ đi 1 ký tự B.
Như thế, 2 bước chuyển trạng thái này tương đương với bước chuyển trạng thái
δ(q
i
, a, A)->(q
j
, B).
*Đối với các chuyển dịch có dạng:
δ(q
i
, a, A) -> (q
j
, BCDE) tức là thay thế A trên đỉnh Stack thành BCDE ( số phần
tử trên đỉnh Stack tăng thêm nhiều hơn 1) ta cũng tạo một trạng thái q
t
trung gian
mới. Sau đó dùng trạng thái q
t
này để làm bước trung gian để thay thế A bằng
chuỗi BCDEF. Các bước thực hiện lần lược như sau:

phạm.
3
Đồ án Automata và NNHT
- Với các chuyển dịch (7.5) ta sẽ sinh ra luật sinh tương ứng:
(q
i
A q
j
) -> a
- Còn với các chuyển dịch có dạng (7.6) thì sẽ có tập luật sinh:
(q
i
A q
j
) -> a(q
j
B q
l
)(q
l
C q
k
)
trong đó q
l
và q
k
là những trạng thái có thể lấy được trong tập Q = {q
0
, ,q

) (q
l
C q
k
) với (q
i
A q
j
) là biến
không thuộc tập BHD nhưng (q
j
B q
l
), (q
l
C q
k
) thuộc BHD thì thêm (q
i
A q
j
) 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 (q
i
A q
j
) -> a(q
j
B q

k
) đều thuộc
BHD thì (q
i
A q
j
) 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.
III. Cấu trúc chương trình
III.1. Cấu trúc chương trình
- Lớp NPDA bao gồm các thành phần cơ bản của 1 NPDA (q_max, xichma,
gama, delta, qst, z, F) trong đó: q_max là số trạng thái lón nhất của NPDA,
xichma là tập ký tự kết thúc, gama là tập ký tự của stack, delta là các hàm
chuyển, qst là trạng thía bắt đầu, z là ký tự khởi đầu stack, F là mảng bool xác
định 1 trạng thái thuộc NPDA có là trạng thái kết thúc hay không. Trong lớp ta
xây dựng các phương thức đưa 1 NPDA bất kỳ về 1 NPDA tương đương thỏa
mãn điều kiện (1), (2) cụ thể là các phương thức thoadieukien1(),
4
Đồ án Automata và NNHT
thoadieukien2(), 1 phương thức chuyển NPDA thành văn phạm phi ngữ cảnh
(CFG) cụ thể là phương thức toVP().
- Lớp VP bao gồm các thành phần cơ bản của 1 CFG (T,V, S, P) trong đó T là
tập cá ký tự kết thúc, V là tập các ký tự chưa kết thúc, S là ký tự bắt đầu, P là
tập các luật sinh. Trong lớp ta xây dựng các phương thức sau: setT() để cài đặt
tập ký tự kết thúc, addV() để thêm vào các ký tự chưa kết thúc, addP() để
thêm các luật sinh cho văn phạm, loaiboluatsinhvodung() để loại bỏ các luật
sinh vô dụng trong CFG.
- Lớp luatsinh để tạo 1 đối tượng luật sinh cho văn phạm, gồm có vetrai và
vephai lần lượt là vế trái và vế phải của 1 luật sinh.
- Xây dựng 1 form có tên NPDA_CFG nhằm hiển thị các thông tin của NPDA

}
//Chuyen NPDA ve 1 NPDA thoa dieu kien 1
public void thoadieukien1()
{
for (int i = 0; i < q_max; i++)
//Tim trang thai ket thuc dau tien
if (F[i])
{
//Chuyen cac trang thai ket thuc con lai sang trang thai ket thuc dau tien
for (int j = i + 1; j < q_max; j++)
if (F[j])
{
delta.Add("d(q" + j + ",~,z)>>(q" + i + ",z)");
F[j] = false;
}
break;
}
}
//Thoa dieu kien 2
public void thoadieukien2()
{
int dcnt = delta.Count;
for (int i = 0; i < dcnt; i++)
{
string tam = delta[i].ToString();
//Neu thoa dieu kien
if (tam.EndsWith(",~)")) //dang 1 (7.5)
continue;
if (tam.Substring(tam.LastIndexOf(",")).Length == 4) //dang 2 (7.6)
continue;

string tam3 = tam.Substring(tam.LastIndexOf(">")+1);
string tam4 = tam3.Substring(0, tam3.IndexOf(",")-1);
//Lay danh sach bien can thay the
string dsbien =tam3.Substring(tam3.IndexOf(",") + 1,tam3.Length - tam3.IndexOf(',') - 2);
//Lay 2 ky tu cuoi
string tam5 = dsbien.Substring(dsbien.Length - 2);
delta.Add(tam2 + ">>(q" + q_max + "," + tam5 + ")");
dsbien = dsbien.Substring(0, dsbien.Length - 1);
while (true)
{
if (dsbien.Length <= 2)
break;
//Lay 2 ky tu cuoi
tam5 = dsbien.Substring(dsbien.Length - 2);
//Them lan luot cac ham chuyen trang thai vao
delta.Add("d(q" + q_max + ",~," + tam5.Substring(1)+")>>(q"+q_max+","+tam5+ ")");
dsbien = dsbien.Substring(0, dsbien.Length - 1);
}
delta.Add("d(q"+ q_max +",~,"+dsbien.Substring(1) + ")>>" + tam4 + "," + dsbien + ")");
continue;
}
}
}
9
Đồ án Automata và NNHT
public VP toVP()
{
//Phương thức chuyển sang văn phạm
VP kq = new VP();
//Gan tap ky tu ket thuc

}
//Vong lap them cac truong hop o 7.6
for (int i = 0; i < delta.Count; i++)
{
string tam = delta[i].ToString();
if (!tam.EndsWith(",~)"))
{
//Ham delta o dang 7.6
//Lay qi
string qi = tam.Substring(2, tam.IndexOf(",")-2);
//Lay qj
string tam2 = tam.Substring(tam.LastIndexOf(">") + 1);
10
Đồ án Automata và NNHT
string qj = tam2.Substring(1, tam2.IndexOf(",")-1);
//Lay ky tu chuyen a
string kta = tam.Substring(tam.IndexOf(",") + 1, 1);
//Lay bien dinh Stack A
string bentrai_NPDA = tam.Substring(0, tam.LastIndexOf(">")-1);
string bienA = bentrai_NPDA.Substring(bentrai_NPDA.LastIndexOf(",") + 1,
bentrai_NPDA.LastIndexOf(")") - bentrai_NPDA.LastIndexOf(",")-1);
//Lay 2 ky tu bien ben phai NPDA
string haibien = tam.Substring(tam.LastIndexOf(",") + 1, tam.Length -
tam.LastIndexOf(",")-1);
string vetrai_ls = "(" + qi + bienA + qj + ")";
for (int k = 0; k < q_max; k++)
for (int l = 0; l < q_max; l++)
{
string[] vephai_ls = new string[3];
vephai_ls[0] = kta;

public ArrayList P = new ArrayList(); //P:Tập các luật sinh
//Contructor cho lop VP
public VP()
{
}
public void setT(string T)
{
this.T = T;
}
public void addV(string V_)
{
if (!this.V.Contains(V_))
this.V.Add(V_);
}
public void addP(string vetrai, string[] vephai)
{
luatsinh tam = new luatsinh();
tam.vetrai = vetrai;
//Add 1 bien vao V
addV(vetrai);
for (int i = 0; i < vephai.Length; i++)
{
//Neu la 1 bien thi add vao V
if (vephai[i].StartsWith("("))
addV(vephai[i]);
tam.vephai.Add(vephai[i]);
}
P.Add(tam);
}
public void loaiboluatsinhvodung()

//Neu la bien huu dung thi them vao
if ((bienhuudung.Contains(ls.vephai[1])) && (bienhuudung.Contains(ls.vephai[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.Count; i++)
{
luatsinh ls = P[i] as luatsinh;
if(ls==null)
{
throw new Exception("ls khong phai la luatsinh");
}
//Neu ve ben trai la bien vo dung
if (!bienhuudung.Contains(ls.vetrai))
{
P.RemoveAt(i);
i ;
continue;
}
//Neu ve ben phai la bien vo dung
if ((!bienhuudung.Contains(ls.vephai[1])) || (!bienhuudung.Contains(ls.vephai[2])))
{
P.RemoveAt(i);

{
NPDA npda = new NPDA();
public NPDA_CFG()
14
Đồ án Automata và NNHT
{
InitializeComponent();
}
private void btnBrowse_Click(object sender, EventArgs e)
{
OpenFileDialog ofd = new OpenFileDialog();
ofd.Title = "Open File";
ofd.InitialDirectory = @"D:\";
ofd.Filter = "Text file(*.txt)|*.txt|All files(*.*)|*.*";
if (ofd.ShowDialog() == DialogResult.OK)
{
txtPath.Text = ofd.FileName;
}
FileStream stream = new FileStream(txtPath.Text, FileMode.Open, FileAccess.Read);
StreamReader reader=new StreamReader(stream,Encoding.Unicode);
txtSoTrangThaiMax.Text = reader.ReadLine();
txtTapKyTuKetThuc.Text = reader.ReadLine();
txtTapKyTuStack.Text = reader.ReadLine();
txtTTBatDau.Text = reader.ReadLine();
txtKyTuKhoiDauStack.Text = reader.ReadLine();
txtTapTTKetThuc.Text = reader.ReadLine();
rtxtHamChuyen.Text="";
while (!reader.EndOfStream)
{
npda.delta.Add(reader.ReadLine());

for (int i = 0; i < vp.V.Count; i++)
{
string str = vp.V[i] as string;
if (str == null)
{
throw new Exception("str khong phai la string");
}
rtxtCFG.Text += (str + " ");
}
rtxtCFG.Text += "\n";
rtxtCFG.Text += "S: " + vp.S.ToString() + "\n\n";
rtxtCFG.Text += "P: \n";
for (int i = 0; i < vp.P.Count; i++)
{
luatsinh ls = vp.P[i] as luatsinh;
if (ls == null)
{
throw new Exception("ls khong phai la luatsinh");
}
rtxtCFG.Text += ls.ToString() + "\n";
}
}
}
16
Đồ án Automata và NNHT
VI. Tài liệu tham khảo
1. Slide bài giảng của giảng viên TS.Hà Chí Trung
2. Automat & NNHT của giảng viên Võ Minh Phổ_Tài liệu word
3. GT_Automat &NNHT của DHBK TPHCM_Tài liệu PDF
4. Website http:\\ congdongcviet.com.vn