5) Operator +-*/**
6) delim blank | tab | newline ;
+
ws delim .
7) letter A | B | ...| Z | a | b |...| z ; digit 0 | 1 | ...| 9 ;
*
id (letter| _ ) (letter | digit | _ ) .
b) Xây dựng sơ đồ chuyển để nhận biết mỗi tthẻ từ.
Start
0,1,2,3,4,5,6,7,8,9
q0
q1
1) Digit:
digit
Start
q2
digit
q3
Digits:
Start
0,1,2,3,4,5,6,7,8,9
q0
q1
Start
q2
+, -
q3
2) Digit: sign:
sign
Start
q4
q5
digit
q6
digit
Digits:
Start
0
+,- ,1 digit 2
.
3
digit
4
3)
number:
digit
digit
4)
nums: Start
15 +,- ,16
digit
digit 17 .
digit
18
digit
19 E
20 +,- ,21
digit
digit 22
5) operator:
6)
delim:
*
Start
q0
Blank, tab, linenew
q1
Start
0
*
1
*
2
other
3
/
5
+
5
-
6
delim
Start
21
delim
23
Ws:
Start
q0
A,…,Z, a, …,z
q1
7) Letter:
Digit:
id:
Start
0,1,2,3,4,5,6,7,8,9
q2
q3
Start
9
letter
10
letter, digit
Hình BT 2.12 Các sơ đồ chuyển
2.13. Lời giải tóm tắt
a) – M =
+ Q = {q1, q2, q3, q4};
= {0, 1};
+ q0 = q1 ;
+ F = q4
0 | 1 | |
q1 | q2 | q2 |
q2 | q3 | q2 |
q3 | q4 | q4 |
q4 | q4 | q4 |
Có thể bạn quan tâm!
-
Chương trình dịch - 18 -
Chương trình dịch - 19 -
Chương trình dịch - 20 -
Chương trình dịch - 22 -
Chương trình dịch - 23 -
Chương trình dịch - 24
Xem toàn bộ 224 trang tài liệu này.
Bảng BT 2.13.
- Automat M là Automat hữu hạn đơn định; vì qQ và a, ta có:
(q, a) 1
b) 1) 1010101100$
q | c | |
khởi tạo | q1 | 1 |
1 | q2 | 0 |
2 | q3 | 1 |
3 | q4 | 0 |
4 | q4 | 1 |
5 | q4 | 0 |
6 | q4 | 1 |
7 | q4 | 1 |
8 | q4 | 0 |
9 | q4 | 0 |
10 | q4 | $ |
Bảng BT 2.13b1
Ta có q = q4 F. Vậy automat trên đoán nhận được từ w = 1010101100$.
2) 110011101$
q | c | |
khởi tạo | q1 | 1 |
1 | q2 | 1 |
2 | q2 | 0 |
3 | q3 | 0 |
4 | q4 | 1 |
5 | q4 | 1 |
6 | q4 | 1 |
7 | q4 | 0 |
8 | q4 | 1 |
9 | q4 | $ |
Bảng BT 2.13b2
Ta có q = q4 F. Vậy automat trên đoán nhận được từ w = 110011101$.
3) 000000000$
q | c | |
khởi tạo | q1 | 0 |
1 | q2 | 0 |
2 | q3 | 0 |
3 | q4 | 0 |
4 | q4 | 0 |
5 | q4 | 0 |
6 | q4 | 0 |
7 | q4 | 0 |
8 | q4 | 0 |
9 | q4 | $ |
Bảng BT 2.13b3
Ta có q = q4 F. Vậy automat trên đoán nhận được từ w = 000000000$. c) L(M) = (0+1)1*0(0+1)(0+1)*
2.14. Lời giải tóm tắt
a) M =
+ Q = {A, B, C, D};
= {0, 1};
+ q0 = A;
+ F = D
0 | 1 | |
A | {B} | {A, B} |
B | {B, C} | |
C | {D} | {C, D} |
D |
Bảng BT 2.14a
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ừ: Automat M là Automat hữu hạn không đơn định; vì AQ và 1 và
(A, 1) = {A, B} = 2 1.
+ w = 1110011$
Sử dụng giải thuật automat không đơn định NFA đoán nhận từ vị bằng bảng sau:
q = (q, c) | c | |
khởi tạo | A | 1 |
1 | {A, B} | 1 |
2 | {A, B} | 1 |
3 | {A, B} | 0 |
4 | {B, C} | 0 |
5 | {B, C, D} | 1 |
6 | {C, D} | 1 |
7 | {C, D} | $ |
Bảng BT 2.14b1
Ta có q F = {C, D} {D} = {D} . Vậy automat đoán nhận được từ w = 1110011$.
+ w = 100001110$
q = (q, c) | c | |
khởi tạo | A | 1 |
1 | {A, B} | 0 |
2 | {B, C} | 0 |
3 | {B, C, D} | 0 |
4 | {B, C, D} | 0 |
5 | {B, C, D} | 1 |
6 | {C, D} | 1 |
7 | {C, D} | 1 |
8 | {C, D} | 0 |
9 | {D} | $ |
Bảng BT 2.14b2
Ta có q F = {D} {D} = {D} . Vậy automat đoán nhận được từ w = 100001110$.
+ w = 111100000$
q = (q, c) | c | |
khởi tạo | A | 1 |
1 | {A, B} | 1 |
2 | {A, B} | 1 |
3 | {A, B} | 1 |
4 | {A, B} | 0 |
5 | {B, C} | 0 |
6 | {B, C, D} | 0 |
7 | {B, C, D} | 0 |
8 | {B, C, D} | 0 |
9 | {B, C, D} | $ |
Bảng BT 2.14b3
Ta có q F = {B, C, D} {D} = {D} . Vậy automat đoán nhận được từ w = 111100000$.
c) Chỉ ra ngôn ngữ đoán nhận bởi M N(M) =
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M DFA M‟ =
- q‟0 = {A} = q0;
- ‟ = {0,1};
- Xác định Q‟ và ‟
Đánh dấu T | ai | B = (T, ai) | Bổ sung vào Q‟ | Bổ sung vào ‟ | |
Kt | {A} = q0 | q0 | |||
1 | q0 | 0 | {B} = q1 | q1 | ‟(q0, 0) = q1 |
1 | {A, B}= q2 | q2 | ‟(q0, 1) = q2 | ||
2 | q1 | 0 | {B, C} = q3 | q3 | ‟(q1, 0) = q3 |
1 | | ||||
3 | q2 | 0 | {B, C} = q3 | ‟(q2, 0) = q3 | |
1 | {A, B}= q2 | ‟(q2, 1) = q2 | |||
4 | q3 | 0 | {B, C, D}= q4 | q4 | ‟(q3, 0) = q4 |
1 | {C, D}= q5 | q5 | ‟(q3, 1) = q5 | ||
5 | q4 | 0 | {B, C, D}= q4 | ‟(q4, 0) = q4 | |
1 | {C, D}= q5 | ‟(q4, 1) = q5 | |||
6 | q5 | 0 | {D}= q6 | q6 | ‟(q5, 0) = q6 |
1 | {C, D}= q5 | ‟(q5, 1) = q5 | |||
7 | q6 | 0 | | ||
1 | |
Bảng BT 2.14c
- Xác định F‟ = {q4, q5, q6}
2.15. Lời giải tóm tắt
a) M =
+ Q = {0, 1, 2, 3, 4, 5, 6};
= {a, b};
+ q0 = 0;
+ F = 6
a | b | |
0 | {3} | {1} |
1 | {2} | |
2 | {2} | {5} |
3 | {4} | |
4 | {3, 4, 5} | |
5 | {6} | |
6 |
Bảng BT 2.15a
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ừ: Automat M là Automat hữu hạn không đơn định; vì 4Q và b và
(4, b) = {3, 4, 5} = 3 1.
+ w = baaaabb$
Sử dụng giải thuật automat không đơn định đoán nhận w bằng bảng sau:
q = (q, c) | c | |
khởi tạo | 0 | b |
1 | {1} | a |
2 | {2} | a |
3 | {2} | a |
4 | {2} | a |
5 | {2} | b |
6 | {5} | b |
7 | {6} | $ |
Bảng BT 2.15b1