Ta có q F = {6} {6} = {6} . Vậy automat đoán nhận được từ w = baaaabb$.
+ w = aabbbab$
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 | a |
1 | {3} | a |
2 | {4} | b |
3 | {3, 4, 5} | b |
4 | {3, 4, 5, 6} | b |
5 | {3, 4, 5, 6} | a |
6 | {4} | b |
7 | {3, 4, 5} | $ |
Có thể bạn quan tâm!
- Chương trình dịch - 19
- Chương trình dịch - 20
- Chương trình dịch - 21
- Chương trình dịch - 23
- Chương trình dịch - 24
- Chương trình dịch - 25
Xem toàn bộ 224 trang tài liệu này.
Bảng BT 2.15b2
Ta có q F = {3, 4, 5} {6} = . Vậy automat không đoán nhận được từ w = aabbbab$.
+ w = aababbbb$
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 | a |
1 | {3} | a |
2 | {4} | b |
3 | {3, 4, 5} | a |
4 | {4} | b |
5 | {3, 4, 5} | b |
6 | {3, 4, 5, 6} | b |
7 | {3, 4, 5, 6} | b |
8 | {3, 4, 5, 6} | $ |
Bảng BT 2.15b3
Ta có q F = {3, 4, 5, 6} {6} = {6} . Vậy automat đoán nhận được từ w = aababbbb$.
c) Chỉ ra ngôn ngữ đoán nhận bởi M
N(M) = (ba+b aa(bba)* b) b = (ba+ aa(bba)* ) bb
d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M DFA M‟ = ‟,‟,q‟0,>:
- q‟0 = {A} = q0;
- ‟ = {a, b};
- Xác định Q‟ và ‟
Đánh dấu T | ai | B = (T, ai) | Bổ sung vào Q‟ | Bổ sung vào ‟ | |
Kt | {0} = A | A | |||
1 | A | a | {3} = B | B | ‟(A, a) = B |
b | {1}= C | C | ‟(A, b) = C | ||
2 | B | a | {4} = D | D | ‟(D, a) = D |
b | | ||||
3 | C | a | {2}= E | E | ‟(C, a) = E |
b | | ||||
4 | D | a | | ||
b | {3, 4, 5} = F | F | ‟(D, b) = F | ||
5 | E | a | {2}= E | ‟(E, a) = E | |
b | {5}= G | G | ‟(E, b) = G | ||
6 | F | a | {4} = D | ‟(F, a) = D | |
b | {3, 4, 5, 6} = H | H | ‟(F, b) = H | ||
7 | G | a | | ||
b | {6} = I | I | ‟(G, b) = I | ||
8 | H | a | {4} = D | ‟(H, a) = D | |
b | {3, 4, 5, 6} = H | ‟(H, b) = H | |||
9 | I | a | | ||
b | |
Bảng BT 2.15c
- Xác định F‟ = {H, I}.
2.16. Lời giải tóm tắt
a) - M = , , q0, F> trong đó:
+ Q = {q0, q1, q2, q3};
= {0, 1};
+ q0 = q0;
+ F = q3;
+ :
0 | 1 | | |
q0 | {q1} | {q1} | |
q1 | {q1, q2} | ||
q2 | {q2, q3} | {q1, q3} | |
q3 |
Bảng BT 2.16a
- Automat M thuộc dạng NFA vì q0 Q, ta có (q0, ) = {q1}.
b) Sử dụng giải thuật nhận biết từ vị bằng Automat 1) 00011111$
q = -closure((q,c)) | c | |
khởi tạo | {q0, q1} | 0 |
1 | {q1, q2, q3} | 0 |
2 | {q1, q2, q3} | 0 |
3 | {q1, q2, q3} | 1 |
4 | {q1, q2, q3} | 1 |
5 | {q1, q2, q3} | 1 |
6 | {q1, q2, q3} | 1 |
7 | {q1, q2, q3} | 1 |
8 | {q1, q2, q3} | $ |
Bảng BT 2.16b1
Ta có q F = {q1, q2, q3} {q3} = {q3} . Vậy automat đoán nhận được từ 00011111$.
2) 01111110$
q = -closure((q,c)) | c | |
khởi tạo | {q0, q1} | 0 |
1 | {q1, q2, q3} | 1 |
2 | {q1, q2, q3} | 1 |
3 | {q1, q2, q3} | 1 |
4 | {q1, q2, q3} | 1 |
5 | {q1, q2, q3} | 1 |
6 | {q1, q2, q3} | 1 |
7 | {q1, q2, q3} | 0 |
8 | {q1, q2, q3} | $ |
Bảng BT 2.16b2
Ta có q F = {q1, q2, q3} {q3} = {q3} . Vậy automat đoán nhận được từ 0111110$.
3) 000000001$
q = -closure((q,c)) | c | |
khởi tạo | {q0, q1} | 0 |
1 | {q1, q2, q3} | 0 |
2 | {q1, q2, q3} | 0 |
3 | {q1, q2, q3} | 0 |
4 | {q1, q2, q3} | 0 |
5 | {q1, q2, q3} | 0 |
6 | {q1, q2, q3} | 0 |
7 | {q1, q2, q3} | 0 |
8 | {q1, q2, q3} | 1 |
9 | {q1, q2, q3} | $ |
Bảng BT 2.16b3
Ta có q F = {q1, q2, q3} {q3} = {q3} . Vậy automat đoán nhận được từ 000000001$.
c) N(M) =0+1*(1+)
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(q0) = {q0, q1} = 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 | {q0, q1} = A | A | |||
1 | A | 0 | {q1, q2, q3} = B | B | ‟(A, 0) = B |
1 | | ||||
2 | B | 0 | {q1, q2, q3} = B | ‟(B, 0) = B | |
1 | {q1, q2, q3} = B | ‟(B, 1) = B |
Bảng BT 2.16d
- Xác định F‟ = {B}.
2.17. Lời giải tóm tắt
a) - M = , , q0, F> trong đó:
+ Q = {q0, q1, q2, q3};
= {0, 1};
+ q0 = q0;
+ F = q3;
+ :
0 | 1 | | |
q0 | {q0, q1} | {q1} | {q1} |
q1 | {q1, q2} | ||
q2 | {q3} | {q3} | |
q3 | {q1} |
Bảng BT 2.17a
- Automat M thuộc dạng NFA vì q0 Q, ta có (q0, ) = {q1}.
b) Sử dụng giải thuật nhận biết từ vị bằng Automat 1) 000101001$
q = -closure((q,c)) | c | |
khởi tạo | {q0, q1} | 0 |
1 | {q0, q1, q2, q3} | 0 |
2 | {q0, q1, q2, q3} | 0 |
3 | {q0, q1, q2, q3} | 1 |
4 | {q1, q3} | 0 |
5 | {q1, q2, q3} | 1 |
6 | {q1, q3} | 0 |
7 | {q1, q2, q3} | 0 |
8 | {q1, q2, q3} | 1 |
9 | {q1, q3} | $ |
Bảng BT 2.17b1
Ta có q F = {q1, q3} {q3} = {q3} . Vậy automat đoán nhận được từ 000101001$.
2) 01010100$
q = -closure((q,c)) | c | |
khởi tạo | {q0, q1} | 0 |
1 | {q0, q1, q2, q3} | 1 |
2 | {q1, q3} | 0 |
3 | {q1, q2, q3} | 1 |
4 | {q1, q3} | 0 |
5 | {q1, q2, q3} | 1 |
6 | {q1, q3} | 0 |
7 | {q1, q2, q3} | 0 |
8 | {q1, q2, q3} | $ |
Bảng BT 2.17b2
Ta có q F = {q1, q2, q3} {q3} = {q3} . Vậy automat đoán nhận được từ 01010100$
3) 0000000010$
q = -closure((q,c)) | c | |
khởi tạo | {q0, q1} | 0 |
1 | {q0, q1, q2, q3} | 0 |
2 | {q0, q1, q2, q3} | 0 |
3 | {q0, q1, q2, q3} | 0 |
4 | {q0, q1, q2, q3} | 0 |
5 | {q0, q1, q2, q3} | 0 |
6 | {q0, q1, q2, q3} | 0 |
7 | {q0, q1, q2, q3} | 0 |
8 | {q0, q1, q2, q3} | 1 |
9 | {q1, q3} | 0 |
10 | {q1, q2, q3} | $ |
Bảng BT 2.17b3
Ta có q F = {q1, q2, q3} {q3} = {q3} . Vậy automat đoán nhận được từ 0000000010$.
c) Ngôn ngữ đoán nhận bởi M N(N) = 0*(01)(0+(1))+
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(q0) = {q0, q1} = 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 | {q0, q1} = A | A | |||
1 | A | 0 | {q0, q1, q2, q3} = B | B | ‟(A, 0) = B |
1 | {q1} = C | C | ‟(A, 1) = C | ||
2 | B | 0 | {q0, q1, q2, q3} = B | ‟(B, 0) = B | |
1 | {q1, q3} = D | D | ‟(B, 1) = D | ||
3 | C | 0 | {q1, q2, q3} = E | E | ‟(C, 0) = E |
1 | |
D | 0 | {q1, q2, q3} = E | ‟(D, 0) = E | ||
1 | | ||||
5 | E | 0 | {q1, q2, q3} = E | ‟(E, 0) = E | |
1 | {q1, q3} = D | ‟(E, 1) = D |
Bảng BT 2.17d
- Xác định F‟ = {B, D, E}
2.18. Lời giải tóm tắt
a) M = , , q0, F> trong đó:
+ Q = {0, 1, 2, 3, 4};
= {a, b};
+ q0 = 0;
+ F = 4
a | b | | |
0 | {1, 3} | ||
1 | {2} | {1, 2} | |
2 | {2} | ||
3 | {3, 4} | ||
4 |
Bảng BT 2.18a
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 thuộc dạng NFA vì 0 Q, ta có (0, ) = {1, 3}.
1) w = bbbaaa$
q = -closure((q,c)) | c | |
khởi tạo | {0, 1, 3} | b |
1 | {1, 2, 3, 4} | b |
2 | {1, 2, 3, 4} | b |
3 | {1, 2, 3, 4} | a |