{2} | a | |
5 | {2} | a |
6 | {2} | $ |
Có thể bạn quan tâm!
-
Chương trình dịch - 20 -
Chương trình dịch - 21 -
Chương trình dịch - 22 -
Chương trình dịch - 24 -
Chương trình dịch - 25 -
Chương trình dịch - 26
Xem toàn bộ 224 trang tài liệu này.
Bảng BT 2.18b1
Ta có q F = {2} {2, 4} = {2} . Vậy automat đoán nhận được từ w = bbbaaa$
2) w = bbaaab$
q = -closure((q,c)) | c | |
khởi tạo | {0, 1, 3} | b |
1 | {1, 2, 3, 4} | b |
2 | {1, 2, 3, 4} | a |
3 | {2} | a |
4 | {2} | a |
5 | {2} | b |
6 | | $ |
Bảng BT 2.18b2
Ta có q F = {2, 4} = . Vậy automat không đoán nhận được từ w = bbaaab$.
c) Ngôn ngữ đoán nhận bởi M N(M) = (b*(ab)a*)b+
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M D = < Q‟, ‟, ‟, q‟0, F‟ >. Trong đó:
- ‟ = {a, b};
- q‟0 = ε-closure(0) = {0, 1, 3} = A; Q‟ = {A};
- Xác định Q‟ và ‟
Đánh dấu T | ai | B = ε-closure((T, ai)) | Bsung vào Q‟ | Bsung vào ‟ | |
Kt | {0, 1, 3} = A | A | |||
1 | A | a | {2} = B | B | ‟(A, a) = B |
b | {1, 2, 3, 4} = C | C | ‟(A, b) = C |
B | a | {2} = B | ‟(B, a) = B | ||
b | | ||||
3 | C | a | {2} = B | ‟(C, a) = B | |
b | {1, 2, 3, 4} = C | ‟(C, b) = C |
Bảng BT 2.18d
- Xác định F‟ = {B, C}
2.19. Lời giải tóm tắt
a) M =
+ Q = {0, 1, 2, 3, 4, 5, 6};
= {a, b};
+ q0 = 0;
+ F = {
a | b | | |
0 | {1, 3} | ||
1 | {2} | ||
2 | {2} | {5} | |
3 | {4} | ||
4 | {5} | {3, 4} | |
5 | {6} | ||
6 |
Bảng BT 2.19a
b) Dùng giải thuật đoán nhận từ vị bằng automat
Automat M thuộc dạng NFA vì 0 Q, ta có (0, ) = {1, 3}.
+ w = aaaaab
q = -closure((q,c)) | c | |
khởi tạo | {0, 1, 3, 4} | a |
1 | {2, 5} | a |
{2, 5} | a | |
3 | {2, 5} | a |
4 | {2, 5} | a |
5 | {2, 5} | b |
6 | {6} | $ |
Bảng BT 2.19b1
Ta có q F = {6} {6} = {6} . Vậy automat đoán nhận được từ w = aaaaab.
+ w = bbbbab
q = -closure((q,c)) | c | |
khởi tạo | {0, 1, 3, 4} | b |
1 | {3, 4} | b |
2 | {3, 4} | b |
3 | {3, 4} | b |
4 | {3, 4} | a |
5 | {5} | b |
6 | {6} | $ |
Bảng BT 2.19b2
Ta có q F = {6} {6} = {6} . Vậy automat đoán nhận được từ w = bbbbab.
c) Ngôn ngữ đoán nhận bởi M
L(M) = (a+b* a)b
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M D = < Q‟, ‟, ‟, q‟0, F‟ >. Trong đó:
- ‟ = {a, b};
- q‟0 = ε-closure(0) = {0, 1, 3, 4} = A; Q‟ = {A};
- Xác định Q‟ và ‟
Đánh dấu T | ai | B = ε-closure((T, ai)) | Bsung vào Q‟ | Bsung vào ‟ | |
Kt | {0, 1, 3, 4} = A | A | |||
1 | A | a | {2, 5} = B | B | ‟(A, a) = B |
b | {3, 4} = C | C | ‟(A, b) = C | ||
2 | B | a | {2, 5} = B | ‟(B, a) = B | |
b | {6} = D | D | ‟(B, b) = D | ||
3 | C | a | {5} = E | E | ‟(C, a) = E |
b | {3, 4} = C | ‟(C, b) = C | |||
4 | D | a | | ||
b | | ||||
5 | E | a | | ||
b | {6} = D | ‟(E, b) = D |
Bảng BT 2.19d
- Xác định F‟ = {D}
2.20. Lời giải tóm tắt
a) M =
+ Q = {A, B, C, D};
= {0, 1};
+ q0 = A;
+ F = {D
0 | 1 | | |
A | {A, B} | {B} | |
B | {C} | {B} | {C} |
C | {D} | {D} | |
D | {A} |
Bảng BT 2.20a
Automat M thuộc dạng NFA vì A Q, ta có (A, ) = {B}.
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
q = -closure((q,c)) | c | |
khởi tạo | {A, B, C, D} | 1 |
1 | {A, B, C, D} | 1 |
2 | {A, B, C, D} | 1 |
3 | {A, B, C, D} | 1 |
4 | {A, B, C, D} | 1 |
5 | {A, B, C, D} | 0 |
6 | {A, B, C, D} | $ |
Bảng BT 2.20b1
Ta có q F = {A, B, C, D}{D} = {D} . Vậy automat đoán nhận được từ w = 111110.
+ w = 111111
q = -closure((q,c)) | c | |
khởi tạo | {A, B, C, D} | 1 |
1 | {A, B, C, D} | 1 |
2 | {A, B, C, D} | 1 |
3 | {A, B, C, D} | 1 |
4 | {A, B, C, D} | 1 |
5 | {A, B, C, D} | 1 |
6 | {A, B, C, D} | $ |
Bảng BT 2.20b2
Ta có q F = {A, B, C, D} {D} = {D} . Vậy automat đoán nhận được
từ
w = 111111.
c) Ngôn ngữ đoán nhận bởi M
L(M) = (1* (1)1* (0)(1))+ = 1*0*
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M D = < Q‟, ‟, ‟, q‟0, F‟ >. Trong đó:
- ‟ = {0, 1};
- q‟0 = ε-closure(0) = {A, B, C, D} = q0; Q‟ = {q0};
- Xác định Q‟ và ‟
Đánh dấu T | ai | B = ε-closure((T, ai)) | Bổ sung vào Q‟ | Bổ sung vào ‟ | |
Kt | {A, B, C, D} = q0 | q0 | |||
1 | q0 | 0 | {A, B, C, D} = q0 | ‟(q0, 0) = q0 | |
1 | {A, B, C, D} = q0 | ‟(q0, 1) = q0 |
Bảng BT 2.20d
- Xác định F‟ = {q0}
2.21. Lời giải tóm tắt
a) - M =
+ Q = Q = {0, 1, 2, 3, 4};
= {a, b};
+ q0 = 0;
+ F = 4;
+ :
a | b | | |
0 | {1} | {3} | |
1 | {1} | {2} | |
2 | {4} | {1} | |
3 | {4} | {3} | |
4 | {4} |
Bảng BT 2.21a
- Automat M thuộc dạng NFA vì 0Q, ta có (0, ) = {3}.
b) Dùng giải thuật đoán nhận từ vị bằng automat
+ w = bbbaaaa
q = -closure((q,c)) | c | |
khởi tạo | {0, 3} | b |
1 | {3} | b |
2 | {3} | b |
3 | {3} | a |
4 | { 4} | a |
5 | {4} | a |
6 | {4} | a |
7 | {4} | $ |
Bảng BT 2.21b1
Ta có q F = {4} {4} = {4} . Vậy automat đoán nhận được từ w = bbbaaaa.
+ w = aaaabba
q = -closure((q,c)) | c | |
khởi tạo | {0, 3} | a |
1 | {1, 4} | a |
2 | {1, 4} | a |
3 | {1, 4} | a |
4 | {1, 4} | b |
5 | {1, 2} | b |
6 | {1, 2, 4} | a |
7 | {1, 4} | $ |
Bảng BT 2.21b2
Ta có q F = {1, 4} {4} = {4} . Vậy automat đoán nhận được từ w = aaaabba.
c) Chỉ ra ngôn ngữ đoán nhận bởi M L(M) = ((a a* b+ b) b* a) a*
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M D = < Q‟, ‟, ‟, q‟0, F‟ >. Trong đó:
- ‟ = {a, b};
- q‟0 = ε-closure(0) = {0, 3} = A; Q‟ = {A};
- Xác định Q‟ và ‟
Đánh dấu T | ai | B = ε-closure((T, ai)) | Bsung vào Q‟ | Bsung vào ‟ | |
Kt | {0, 3} = A | A | |||
1 | A | a | {1, 4} = B | B | ‟(A, a) = B |
b | {3} = C | C | ‟(A, b) = C | ||
2 | B | a | {1, 4} = B | ‟(B, a) = B | |
b | {1, 2} = D | D | ‟(B, b) = D | ||
3 | C | a | {4} = E | E | ‟(C, a) = E |
b | {3} = C | ‟(C, b) = C | |||
4 | D | a | {1} = G | G | ‟(D, a) = G |
b | {1, 2, 4} = H | H | ‟(D, b) = H | ||
5 | E | a | {4} = E | ‟(E, a) = E | |
b | | ||||
6 | G | a | {1} = G | ‟(G, a) = G | |
b | {1, 2} = D | ‟(G, b) = D | |||
7 | H | a | {1, 4} = B | ‟(H, a) = B | |
b | {1, 2, 4} = H | ‟(H, b) = H |
Bảng BT 2.21d
- Xác định F‟ = {B, E, H}
2.22. Lời giải tóm tắt a) r = 0(0 + 1)* 0+
+ Phân tích r
- Ta có r = r1 r2; r1= 0(0 + 1)*; r2= 0+.
- r1 = r3 r4; r3 = 0; r4 = (0 + 1)*.
- r4 = (r5 )* ; r5= (0 + 1).
- r5 = r6 + r7 ; r6 = 0; r7 = 1.