Trang chủ / Ngôn Ngữ Hình Thức

Ngôn ngữ hình thức - 13


- :

(A, a) = {A, B}; (A, b) = {B}; (B, a) = {D, E}; (B, b) ={C, E};

(C, a) = {D, E} ; (C, b) = {D}; (D, a) = {C}; (D, b) = {E}; (E, a) = {E}.

1) Hãy biểu diễn M dưới dạng:

- Bảng;

- Đồ thị.

2) Automat M thuộc dạng nào, vì sao?.

3) Tính: - (A, aaabbaaaa);

- (C, abaabba);

4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?:

- w = aabaaaaa;

- w = aaaababbb.

2.19. Cho Automat hữu hạn: M = <Q, , , q0, F> trong đó:

- q0 = 0 ;

- = a, b, c;

- Q = 0, 1, 2, 3;

- F = 3;

- :

(0, a) = {0,1}; (0, b) = {2}; (0, c) = {2}; (1, a) = {1, 2};

(1, b) = {1, 2, 3}; (2, a) = {3}; (2, b) = {2, 3}; (2, c) = {3};

(3, a) = {3}; (3, b) = {2}; (3, c) = {3}.

1) Hãy biểu diễn M dưới dạng:

- Bảng;

- Đồ thị.

2) Automat M thuộc dạng nào, vì sao?.

3) Tính: - (1, aaabbaaaabc);

- (0, cabaabba);

4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?:

- w = caabaaabca;


- w = aaaabbbc.

2.20. Cho Automat hữu hạn: M = <Q, , , q0, F> trong đó:

- q0 = A ;

- = a, b;

- Q = A, B, C, D, E;

- F = E;

- :

(A, a) = {A, B}; (A, b) = {B}; (A, ) = {B}; (B, a) = {D, E};

(B, b) ={C, E}; (C, a) = {D, E} ; (C, b) = {D}; (D, b) = {D, E};

(E, a) = {E}; (E, ) = {A}.

1) Hãy biểu diễn M dưới dạng:

- Bảng;

- Đồ thị.

2) Automat M thuộc dạng nào, vì sao?.

3) Tính:

- -CLOSURE(A), -CLOSURE(E);

- (A, a) và *(A, a);

- (E, a) và *(E, a);

- *(E, aaabbaaaa).

4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?:

- w = aabaaaaa;

- w = aaaababbb.

2.21. Cho Automat hữu hạn: M = <Q, , , q0, F> trong đó:

- q0 = q0;

- = 0, 1;

- Q = q0; q1; q2; q3;

- F = q3;

- :

(q0,0) = {q0; q1}; ( q0, 1) = {q2}; (q0, ) = {q2};


(q1, 0) = {q2}; ( q1, 1) = {q1; q2; q3}; (q2, 0) = {q2};

(q2, 1) = {q3} ; (q2, ) = {q3}; ( q3, ) = {q0}.

1) Hãy biểu diễn M dưới dạng:

- Bảng;

- Đồ thị.

2) Automat M thuộc dạng nào, vì sao?.

3) Tính:

- -CLOSURE(q0), -CLOSURE(q3);

- (q3, 0) và *(q3, 0);

- *( q3, 0101011).

4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?:

- w = 0001100;

- w = 1110010.

2.22. Cho Automat hữu hạn: M = <Q, , , q0, F> được biểu diễn dưới dạng bảng như sau:

- q0 = q0;

- F = q3;

- :


Q

0

1

q0

{q1; q2}

{q1}

q1

{q1; q2; q3}

{q3}

q2

{q1; q2}

{q3}

q3

{q1}

{q2; q3}

Có thể bạn quan tâm!

Xem toàn bộ 254 trang tài liệu này.

Ngôn ngữ hình thức - 13


1) Nêu đầy đủ các thành phần của M.

2) Biểu diễn M dưới dạng đồ thị.

3) Automat M thuộc dạng nào, vì sao?.

4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?:


- w = 0011111;

- w = 0000010.

2.23. Cho Automat hữu hạn: M = <Q, , , q0, F> được biểu diễn dưới dạng đồ thị như sau:

Start

0

a

1

b

2

b

3

b

a

b a a a


1) Nêu đầy đủ các thành phần của M.

2) Biểu diễn M dưới dạng bảng.

3) Automat M thuộc dạng nào, vì sao?.

4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?:

- w = bbbbbbb;

- w = bbbaaab.

2.24. Cho Automat hữu hạn: M = <Q, , , q0, F> được biểu diễn dưới dạng bảng như sau:

- q0 = q0;

- F = q3;

- :


Q

0

1

q0

{q2; q3}

{q1}

{q2}

q1

{q1; q2}



q2

{q1; q2}

{q2; q3}


q3

{q1}

{q2; q3}

{q0}


1) Nêu đầy đủ các thành phần của M.

2) Biểu diễn M dưới dạng đồ thị.

3) Automat M thuộc dạng nào, vì sao?.



4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?:

- w = 0000000;

- w = 11100111.

2.25. Cho Automat hữu hạn: M = <Q, , , q0, F> được biểu diễn dưới dạng đồ thị

như sau: a



b

1

a

2

Start

0

a

3

4

b


1) Nêu đầy đủ các thành phần của M.

2) Biểu diễn M dưới dạng bảng.

3) Automat M thuộc dạng nào, vì sao?.

4) Sử dụng giải thuật kiểm tra các từ sau có thuộc ngôn ngữ L(M) không?:

- w = bbbbabb;

- w = abababa.

2.26. Cho Automat NFA M:


Start

q1

0

q2

0

q3

1 0 1


0


1) Chuyển M về dạng DFA D tương đương.

2) Biểu diễn D dưới dạng đồ thị.

2.27. Cho Automat NFA M:

1


Start

q1

0

q2

0

q3

1

q4

0

0


1) Chuyển M về dạng DFA D tương đương.

2) Biểu diễn D dưới dạng bảng.

2.28. Cho Automat NFA M.


Start

q1

0

q2

0

q3

1

q4


0


bảng. thị.

1) Hãy chuyển NFA M về dạng NFA M‟ tương đương và biểu diễn M‟ dưới dạng


2) Hãy chuyển NFA M‟ về dạng DFA D tương đương và biểu diễn D dưới dạng đồ

2.29. Cho Automat NFA M.

1

Start

q1

0

q2

0

q3

1

q4

0

0

bảng. thị.

1) Hãy chuyển NFA M về dạng NFA M‟ tương đương và biểu diễn M‟ dưới dạng


2) Hãy chuyển NFA M‟ về dạng DFA D tương đương và biểu diễn D dưới dạng đồ

2.30. Cho các Automat có sơ đồ chuyển trạng thái như sau:


Start

A

1

B

0

1

0

C

0 1

0

Start A 0 B

1

C


a) b)



1) Cho biết biểu thức chính quy tương ứng với mỗi sơ đồ.

2) Các Automat trên thuộc loại nào.

3) Xây dựng DFA tương ứng với mỗi sơ đồ.

2.31. Cho Σ = {0, 1, 2, 3}. Viết biểu thức chính quy của các ngôn ngữ trên Σ sau:

1) Tập hợp các xâu: Mở đầu bằng một ký tự 0, tiếp theo là một ký tự 1 hoặc 2, cuối cùng là dãy một hoặc nhiều ký tự 3.

2) Tập hợp các xâu: Mở đầu bằng một dãy ký tự 3, tiếp theo là dãy các ký tự 0 hoặc 1 hoặc 2.

3) Tập hợp các xâu: Mở đầu là dãy các ký tự 0 hoặc 1, kết thúc là dãy các ký tự 2 hoặc 3.

2.32. Cho các biểu thức chính quy:

a) 0(0 + 1)* 0+

*

b) ((0+ 1) 0(0 + 1))+

c) (1+ 0)00 (0* + 1+)

*

d) (a + ba + aab) (ε + a)+

1) Mô tả (bằng lời) ngôn ngữ được biểu diễn bằng mỗi biểu thức trên.

2) Xây dựng NFAε tương đương với mỗi biểu thức trên.

2.33. Cho các FA được biểu diễn dưới dạng đồ thị như sau:


1)

b

M1

Start 0 a 1b

a

2 b 3 a b a a  1 a 2 Start 0 b  3 b 4 b 2 M 2 a Xác định các thành phần của mỗi 1

2 b 3

a

b

a

a

1

a

2

Start

0

b

3

b

4

b

2) M2


a) Xác định các thành phần của mỗi FA trên.

b) Hãy biểu diễn mỗi FA trên dưới dạng bảng.

c) Xây dựng văn phạm tuyến tính phải tương đương với mỗi FA trên.

d) Xây dựng văn phạm tuyến tính trái tương đương với mỗi FA trên.

e) Tìm biểu thức chính quy tương đương với mỗi FA.

2.34. Cho các NFA được biểu diễn dưới dạng bảng như sau: a) - :

Q

a

b

0

{0, 1}

{1}


1

{2}

{2}


2

{2, 3}



3

{3}

{3}

{0}


- q0 = 0;

- F = {3}.

b) - :


Q

a

b

0

{1, 3}

{1}

{1}

1

{2}

{1, 2}


2

{3}


{3}

3





- q0 = 0;

- F = { 3}.

1) Xây dựng văn phạm tuyến tính phải tương đương với mỗi FA trên.

2) Xây dựng văn phạm tuyến tính trái tương đương với mỗi FA trên.

3) Tìm biểu thức chính quy tương đương với mỗi NFA trên.

..... Xem trang tiếp theo?
⇦ Trang trước - Trang tiếp theo ⇨

Ngày đăng: 16/07/2022