- Xây dựng Automat đoán nhận r5 =(r7)*
2
a
3
Start
Có thể bạn quan tâm!
-
Kỹ Thuật Sử Dụng Automat Để Phân Tích Từ Vựng -
Mô Tả Quá Trình Đoán Nhận Xâu -
Biểu Diễn Automat Bằng Đồ Thị -
Vị Trí, Chức Năng, Nhiệm Vụ Của Giai Đoạn Phân Tích Cú Pháp -
Minh Họa Một Cây Phân Tích Cú Pháp -
A, B, C. Mô Tả Quá Trình Phân Tích Xâu W = Cad
Xem toàn bộ 224 trang tài liệu này.
0
1
6
7
4
b
5
Hình 2.24. Automat đoán nhận r5 = (a+b)*
Thực hiện tương tự với r6 = a; r3 = r5 r6; r4 = b; r1 = r3 r4; r2 = b; r = r1 r2. Thu được kết quả như hình sau:
2
a
3
Start
0
1
6
7
a
8
b
9
b
10
4
b
5
Hình 2.25. Automat đoán nhận r=(a b)*abb
CÂU HỎI VÀ BÀI TẬP CHƯƠNG 2
2.1. - Nêu các khái niệm: thẻ từ, trị từ vựng, mẫu từ vựng; cho ví dụ.
- Nêu các phương pháp biểu diễn thẻ từ; cho ví dụ minh họa.
2.2. Nêu vị trí, chức năng, nhiệm vụ của giai đoạn phân tích từ vựng.
2.3. Nêu các kỹ thuật đọc chương trình nguồn sử dụng buffer.
2.4. Nêu giải thuật nhận biết từ vị bằng automat đơn định DFA. Chạy ví dụ minh họa
2.5. Nêu giải thuật nhận biết từ vị bằng automat không đơn định NFA. Chạy ví dụ minh họa.
2.6. Nêu giải thuật nhận biết từ vị bằng automat không đơn định NFA. Chạy ví dụ minh họa.
2.7. Nêu giải thuật biến đổi automat không đơn định NFA về automat đơn định DFA đoán nhận cùng một ngôn ngữ. Cho ví dụ minh họa.
2.8. Nêu giải thuật biến đổi automat không đơn định NFA về automat đơn định DFA đoán nhận cùng một ngôn ngữ. Cho ví dụ minh họa.
2.9. Nêu giải thuật Thomson để xây dựng một automat đoán nhận một biểu thức chính quy. Cho ví dụ minh họa.
2.10. Hãy xác định các trị từ vựng và chỉ ra các token trong các đoạn chương trình Pascal sau:
function max2 (i, j : integer) : integer;
{ Trả về số nguyên lớn hơn trong 2 số i và j } begin
If i > j then max2 : = i
else max2 : = j;
end;
2.11.
Hãy xác định các trị từ vựng và chỉ ra các token trong các đoạn chương trình Pascal sau:
PROGRAM GPTB2;
VAR a,b,c,x1,x2: real; FUNCTION Delta: real;
Begin
Delta:= Sqr(b) - 4*a*c; End;
PROCEDURE Ptb2;
VAR r: real; {r la bien cuc bo} BEGIN
BEGIN
r := Sqrt (delta); x1 := (-b-r)/(2*a);
x2 := (-b+r)/(2*a); END;
END;
(* than chuong trinh *) BEGIN
REPEAT
Write(„a=‟); readln(a); UNTIL a<>0 ;
Write(„b=‟); readln(b);
Write(„c=‟); readln(c); If (delta < 0) Then
Writeln ( „PT vo nghiem‟); If delta = 0 Then
Writeln ( „PT co nghiem kep x1 = x2 =‟,x1:1:2); If delta > 0 Then
Begin
Ptb2;
Writeln ( „PT co 2 nghiem: x1=‟,x1:1:2,‟x2=‟,x2:1:2); Writeln ( „x2 = ‟, x2:1:2);
End;
Readln;
END.
2.12. Trong ngôn ngữ lập trình bậc cao Pascal, cho một số thẻ từ được phát biểu bằng lời như sau:
1) Số nguyên không dấu là một xâu bắt đầu bằng một số, sau đó là không, một hoặc nhiều các chữ số.
2) Số nguyên là một xâu bắt đầu bằng phần dấu, sau đó là một số nguyên không dấu; phần dấu là dấu + hoặc dấu - hoặc không có ký tự nào.
3) Số thực dấu phảy tĩnh là một xâu bắt đầu bằng phần dấu; sau đó là phần nguyên rồi đến phần thập phân; phần thập phân có thể có, có thể không; nếu có phần thập phân thì hai phần này phân cách nhau bởi dấu chấm. Phần nguyên và phần thập phân là một số nguyên không dấu
4) Số thực dấu phảy động là một xâu bắt đầu bằng một số nguyên, tiếp đến là dấu chấm, sau đó là một số nguyên không dấu, tiếp theo là phấn mũ. Phần mũ bắt đầu bằng ký tự E, tiếp đến là một số nguyên.
5) Các toán tử số học là một trong các phép toán +, -, *, / , **
6) Khoảng trắng là một hoặc nhiều ký tự trống hoặc dấu tab hoặc dấu xuống dòng.
7) Tên là một xâu các ký tự, bắt đầu bằng một chữ cái; sau đó là không, một hoặc nhiều các chữ cái hoặc chữ số. Có thể thay chữ cái hoặc chữ số bằng dấu gạch dưới.
a) Hãy biểu diễn mỗi thẻ từ trên bằng biểu thức chính quy và chỉ ra thẻ từ, mẫu từ vựng, trị từ vựng của mỗi từ đó.
b) Xây dựng sơ đồ chuyển để nhận biết mỗi token trên.
2.13. Cho Automat M:
Start
1
q10
0 1
q2 q3
0, 1
q4
0
1
Hình BT 2.13
a) Hãy xác định các thành phần của automat M. Automat trên thuộc loại nào? tại sao?
b) Sử dụng giải thuật nhận biết từ vị bằng Automat tương ứng với M; Kiểm tra xem M có nhận biết được các từ vị sau không?
1) 1010101100$
2) 110011101$
3) 000000000$
c) Chỉ ra ngôn ngữ đoán nhận bởi M
2.14. Cho Automat M
1
0
1
A
0
1
0
Start
B
0
C
1
D
Hình bt 2.14
a) Nêu các thành phần của M
b) Dùng giải thuật đoán nhận từ vị tương ứng với automat trên để đoán nhận các từ:
+ w = 1110011$
+ w = 100001110$
+ w = 111100000$
c) Chỉ ra ngôn ngữ đoán nhận bởi M
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M
2.15. Cho Automat M
a
b
1
a
2
b
Start
0
b
a
b
5
6
3
a
4
b
b
Hình BT 2.15
a) Nêu các thành phần của M
b) Dùng giải thuật đoán nhận từ vị tương ứng với automat trên để đoán nhận các từ:
+ w = baaaabb$
+ w = aabbbab$
+ w = aababbbb$
c) Chỉ ra ngôn ngữ đoán nhận bởi M
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M
2.16. Cho Automat M.
Start
q0
0
q10
q2
1
q
3
1
0
Hình BT 2.16
a) Hãy xác định các thành phần của automat M. Automat trên thuộc loại nào? tại sao?
b) Sử dụng giải thuật nhận biết từ vị bằng Automat tương ứng với M; Kiểm tra xem M có nhận biết được các từ vị sau không?
1) 00011111$
2) 01111110$
3) 000000001$
c) Chỉ ra ngôn ngữ đoán nhận bởi M
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M
2.17. Cho Automat M.
Start
1
0
q0 0 q1
0 0
1
q2 q3
Hình BT 2.17
a) Hãy xác định các thành phần của automat M. Automat trên thuộc loại nào? tại sao?
b) Sử dụng giải thuật nhận biết từ vị bằng Automat tương ứng với M; Kiểm tra xem M có nhận biết được các từ vị sau không?
1) 000101001$
2) 01010100$
3) 0000000010$
c) Chỉ ra ngôn ngữ đoán nhận bởi M
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M
2.18. Cho Automat M
b
a
1
a
b
2
Start
0
b
3
b
4
Hình BT 2.18
a) Nêu các thành phần của M
b) Dùng giải thuật đoán nhận từ vị tương ứng với automat trên để đoán nhận các từ:
1) w = bbbaaa$
2) w = bbaaab$
c) Chỉ ra ngôn ngữ đoán nhận bởi M
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M
2.19. Cho Automat M
a
1
a
2
Start
0
b
a
5
6
3
4
b
b
Hình BT 2.19
a) Nêu các thành phần của M
b) Dùng giải thuật đoán nhận từ vị tương ứng với automat trên để đoán nhận các từ:
+ w = aaaaab
+ w = bbbbab
c) Chỉ ra ngôn ngữ đoán nhận bởi M
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M
2.20. Cho Automat M
1
Start
A
1
1
B
0
C
1
D
Hình BT 2.20
a) Nêu các thành phần của M
b) Dùng giải thuật đoán nhận từ vị tương ứng với automat trên để đoán nhận các từ:
+ w = 111110
+ w = 111111
c) Chỉ ra ngôn ngữ đoán nhận bởi M
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M
2.21. Cho Automat M
a
1
b
2
Start
b
0
3
a
4
a
a
a) Nêu các thành phần của M
b
Hình BT 2.21
b) Dùng giải thuật đoán nhận từ vị tương ứng với automat trên để đoán nhận các từ:
+ w = bbbaaaa
+ w = aaaabba
c) Chỉ ra ngôn ngữ đoán nhận bởi M
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M