Bài tập otomat hữu hạn đơn định có lơi giải năm 2024

8 Bai tap Tich phan mat - deo đề cập sơ lược về véctơ pháp tuyến của mặt cong trong không gian, cùng kỹ

• 6 Bai tap tich phan 3 lop - deo đề cập sơ lược về véctơ pháp tuyến của mặt cong trong không gian, cùng kỹ
• Tổng hợp câu hỏi đã fix

Related documents

• De thi va dap an Giai tich 1 de so 1 ky 1 nam hoc 2019 2020 – UET
• Giải đề GT1 cuối kì CLC kì 1 - 2019
• Đề cương môn GT1 - đề thi và đề cương giải tích 1 năm 2021-2022 trường đại học công nghệ - VNU
• BT Dao Ham Rieng - good slide for students
• Gh - good slide for students
• Mang-may-tinh 04-2-congestion-control-cuuduongthancong

Preview text

BÀI TẬP BÀI 4. SỰ ĐOÁN

NHẬN NGÔN NGỮ

1. Mô tả bằng lời các xâu

trong các tập chính quy

sau:

a) 10; b) 100*;

c) 111001; d)

(100)*;

e) (001); f)

(01)(01)*00;

2. Xâu 1011 có thuộc các

tập chính quy cho dưới đây

không?

a) 101; b)

0*(1011)*;

c) 1(01)1; d)

1*01(01);

e) (10*(11))*; f)

1(00)(11);

tiếp sau bởi ba hoặc nhiều

hơn số 0.

c) Tập các xâu hoặc không

có số 1 nào đứng trước một

số 0 hoặc không có số 0 nào

đứng trước một số 1.

d) Tập các xâu chứa một

xâu các số 1 sao cho số các

số 1 bằng 2 môđun 3, được

tiếp theo bởi một số chẵn

các số 0.

4. Dựng một ôtômát hữu

hạn tất định đoán nhận các

tập sau từ I*, với I là một

chữ cái.

a) ; b) {}; c) {a}

với aI.

hữu hạn không tất định

đoán nhận các tập sau:

a) 01; b) (011)*;

c) 01001.

8. Dựng một ôtômát hữu hạn không tất định đoán nhận các ngôn

ngữ được sinh bởi văn phạm chính quy

G= (V,T,S,P), trong đó V={0,1,S,A,B},

T={0,1}, S là ký hiệu xuất phát và tập P các sản xuất là:

a) S→0A, S→1B, A→0, B→0;

b) S→1A, S→0, S→, A→0B, B→1B, B→1;

c) S→1B, S→0A, S→0, A→1A, A→0B, A→1, A→0, B→1.

Trong các bài tập 9 – 11, hãy dựng một văn phạm G=(V,T,S,P)

sinh ra ngôn ngữ được đoán nhận bởi máy hữu hạn trạng thái đã

cho.

9. 0,

Xuất phát 0 0,

1

10.

1 0 Xuất phát 0

1 0

11.

Xuất phát 1 1

0 0 1 0

0,

12. Chứng tỏ rằng một ôtômát hữu hạn ấy dựng từ một văn phạm

chính quy trong phần chứng minh định lý 2 đoán nhận tập được

sinh bởi văn phạm đó.

13. Chứng minh rằng văn phạm chính quy được xây dựng từ một

ôtômát hữu hạn trong phần chứng minh của định lý 2 sẽ sinh ra

tập được đoán nhận bởi ôtômát đó.

S 0 S S 2

S 0

S 3

S

S

S 2

S

S

Bài tập

1. Mô tả bằng lời các xâu trong các tập chính quy sau: a) 10; b) 100*; c) 111001; d) (100); e) (001)*; f) (01)(01)*00;
2. Xâu 1011 có thuộc các tập chính quy cho dưới đây không? a) 101; b) 0*(1011); c) 1(01)1; d) 101(01); e) (10*(11)); f) 1(00)(11)*; g) (10)1011; h) (100)(010)1.
3. Dùng các biểu thức chính quy biểu diễn các tập sau a) Tập các xâu có một hoặc nhiều hơn số 0 được tiếp sau bởi số 1. b) Tập các xâu có hai hoặc nhiều hơn ký hiệu được tiếp sau bởi ba hoặc nhiều hơn số 0.
4. Tìm một ôtômát hữu hạn đoán nhận. a) {,0); b) {0,11}; c) {0,11,000}.
5. Dùng các cách dựng được mô tả trong phần chứng minh của định lý Kleene, tìm một ôtômát hữu hạn không tất định đoán nhận các tập sau: a) 01; b) (011)*;

3. Tập các xâu hoặc không có số 1 nào đứng trước một số 0 hoặc không có số 0 nào đứng trước một số 1. d) Tập các xâu chứa một xâu các số 1 sao cho số các số 1 bằng 2 môđun 3, được tiếp theo bởi một số chẵn các số 0. 4. Dựng một ôtômát hữu hạn tất định đoán nhận các tập sau từ I*, với I là một chữ cái. a) ; b) {}; c) {a} với aI. 5*. Chứng minh rằng, nếu A là một tập chính quy thì tập tất cả các xâu đảo ngược AR của các xâu trong A cũng sẽ là chính quy.

10.

1 0 Xuất phát 0

1 0

11.

Xuất phát S 0 1 S 1

S 2

S

S

3. 01001.

1. Dựng một ôtômát hữu hạn không tất

định đoán nhận các ngôn ngữ được sinh bởi văn phạm chính quy

G= (V,T,S,P), trong đó V={0,1,S,A,B},

T={0,1}, S là ký hiệu xuất phát và tập P các sản xuất là:

1. S→OA, S→1B, A→0, B→0;

2. S→1A, S→0, S→, A→0B, B→1B,

B→1;

3. S→1B, S→0, A→1A, A→0B,

A→1, A→0, B→1.

Trong các bài tập 9 – 11, hãy dựng một

văn phạm G=(V,T,S,P) sinh ra ngôn ngữ được đoán nhận bởi máy hữu hạn

trạng thái đã cho. 9. 0, Xuất phát 0 0,

1

16*. Một kỹ thuật quan trọng để chứng minh một tập nào đó là không chính quy được gọi là bổ đề bơm (pumping). Bổ đề bơm phát biểu rằng nếu M=(S,I,f,s 0 ,F) là một ôtômát hữu hạn tất định và nếu x là một xâu thuộc

0 0 1 0

0, 12. Chứng tỏ rằng một ôtômát hữu hạn ấy dựng từ một văn phạm chính quy trong phần chứng minh định lý 2 đoán nhận tập được sinh bởi văn phạm đó. 13. Chứng minh rằng văn phạm chính quy được xây dựng từ một ôtômát hữu hạn trong phần chứng minh của định lý 2 sẽ sinh ra tập được đoán nhận bởi ôtômát đó. 14. Chứng tỏ rằng mỗi một ôtômát hữu hạn tất định đều tương đương với một ôtômát khác có tính chất là trạng thái xuất phát của nó không bao giờ được tái ngộ. 15*. Cho M=(S, I, f,s 0 ,F) là một ôtômát hữu hạn tất định. Chứng tỏ rằng ngôn ngữ được đoán nhận bởi M, tức L(M), là vô hạn nếu và chỉ nếu có một từ x được đoán nhận bởi M có l(x)≥S. 17*. Chứng tỏ rằng tập {02n 1 nn=0,1,2,,, } là không chính quy. bạn có thể dùng bổ đề bơm cho trong bài tập 16*. 18*. Chứng tỏ rằng tập {0n