Trang chủ / Tài liệu miễn phí / Tập Bài Giảng

Chương trình dịch - 22


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:


Bước

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!

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

Chương trình dịch - 22

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:


Bước

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à ‟


Bước

Đá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;

+ :


{}

Q

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$

Bước

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$


Bước

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$


Bước

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à ‟


Bước

Đá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;

+ :


{}

Q

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$

Bước

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$


Bước

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$


Bước

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à ‟


Bước

Đá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





4

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




Q {}

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$


Bước

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

Xem tất cả 224 trang.

Ngày đăng: 28/06/2022
Trang chủ Tài liệu miễn phí