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

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


= -CLOSURE({A, B, D, E})

= {A, B, D, E};

- *(E, aaabbaaaa).

Áp dụng công thức δ*(q, wa) = ε-CLOSURE(δ(δ*(q, w), a)), ta có:

+ -CLOSURE(E) = δ*(E, ε) = {E, A, B};

+ -CLOSURE(δ({E, A, B}, a)) = {A, B, D, E};

+ -CLOSURE(δ({A, B, D, E}, a)) = {A, B, D, E};

+ -CLOSURE(δ({A, B, D, E}, a)) = {A, B, D, E};

+ -CLOSURE(δ({A, B, D, E}, b)) = {A, B, C, D, E};

+ -CLOSURE(δ({A, B, C, D, E}, b)) = {A, B, C, D, E};

+ -CLOSURE(δ({A, B, C, D, E}, a)) = {A, B, D, E};

+ -CLOSURE(δ({A, B, D, E}, a)) = {A, B, D, E};

+ -CLOSURE(δ({A, B, D, E}, a)) = {A, B, D, E};

*(E, aaabbaaaa) = {A, B, D, E}. 4)

- w = aabaaaaa


Bước

q = -closure((q,c))

c

khởi tạo

{A, B, E}

a

1

{A, B, D, E}

a

2

{A, B, D, E}

b

3

{A, B, C, D, E}

a

4

{A, B, D, E}

a

5

{A, B, D, E}

a

6

{A, B, D, E}

a

7

{A, B, D, E}

a

8

{A, B, D, E}

$

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

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

q F = {E} w = aabaaaaa L(M).


- w = aaaababbb.


Bước

q = -closure((q,c))

c

khởi tạo

{A, B, E}

a

1

{A, B, D, E}

a

2

{A, B, D, E}

a

3

{A, B, D, E}

a

4

{A, B, D, E}

b

5

{A, B, C, D, E}

a

6

{A, B, D, E}

b

7

{A, B, C, D, E}

b

8

{A, B, C, D, E}

b

9

{A, B, C, D, E}

$

q F = {E} w = aaaababbb L(M).

2.21. 1) - Biểu diễn M dưới dạng bảng:

+ q0 = q0 ;

+ F = q3;

+ :


Q

0

1

q0

{q0; q1}

{q2}

{q2}

q1

{q2}

{q1; q2; q3}


q2

{q2}

{q3}

{q3}

q3



{q0}


- Biểu diễn M dưới dạng đồ thị:

1

0 0 0 1  Start q 0 1 0 q 1 q 1 2 q 3 1   2 Automat M thuộc dạng NFA  vì  q 3 1

0 0 0

1

Start q0 1

0

q

1

q1 2 q3

1



2) Automat M thuộc dạng NFA vì q3 Q mà ( q3, ) = {q0}. 3) - + -CLOSURE(q0), = {q0, q2, q3};

+ -CLOSURE(q3) = {q0, q2, q3};

- + ( q3, 0) = ;

+ *( q3, 0) = -CLOSURE((-CLOSURE(q3), 0)) = -CLOSURE(({q0, q2, q3}, 0))

= -CLOSURE((q0, 0) ( q2, 0) ( q3, 0))

= -CLOSURE({q0, q1, q2})

= -CLOSURE(q0) -CLOSURE(q1) -CLOSURE( q2)

= {q0, q2, q3}{ q1}{q0, q2, q3}} = {q0, q1, q2, q3};

- *( q3, 0101011).

Áp dụng công thức δ*(q, wa) = ε-CLOSURE(δ(δ*(q, w), a)), ta có:


Bước

q = -closure((q,c))

c

khởi tạo

{q0, q2, q3}

0

1

{q0, q1, q2, q3}

1

2

{q0, q1, q2, q3}

0

3

{q0, q1, q2, q3}

1

4

{q0, q1, q2, q3}

0

5

{q0, q1, q2, q3}

1

6

{q0, q1, q2, q3}

1

7

{q0, q1, q2, q3}

$

*( q3, 0101011)={q0, q1, q2, q3}. 4) - w = 0001100;

Bước

q = -closure((q,c))

c

khởi tạo

{q0, q2, q3}

0

1

{q0, q1, q2, q3}

0

2

{q0, q1, q2, q3}

0

3

{q0, q1, q2, q3}

1

4

{q0, q1, q2, q3}

1

5

{q0, q1, q2, q3}

0

6

{q0, q1, q2, q3}

0

7

{q0, q1, q2, q3}

$

q F = { q3} w = 0001100 L(M).


- w = 1110010.


Bước

q = -closure((q,c))

c

khởi tạo

{q0, q2, q3}

1

1

{q0, q1, q2, q3}

1

2

{q0, q1, q2, q3}

1

3

{q0, q1, q2, q3}

0

4

{q0, q1, q2, q3}

0

5

{q0, q1, q2, q3}

1

6

{q0, q1, q2, q3}

0

7

{q0, q1, q2, q3}

$

q F = {q3} w = 1110010 L(M).

2.22. 1) M = <Q, , , q0, F> trong đó:

- Q = q0, q1, q2, q3;

- = 0, 1;

- q0 = q0 ;

- F = q3;

- :

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

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

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

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

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


Start q00

0

0 0 q 1 0 0 1 1 q 2 1 q 3 1 0 1 0 3 Automat M thuộc dạng NFA vì  q 0  Q và  0 2

0

0

q10

0 1

1

q2 1 q3


1 0, 1

0


3) Automat M thuộc dạng NFA vì q0 Q và 0, ta có (q0, 0) = {q1; q2}= 2 > 1.

4) - w = 0011111


Bước

q = (q,c)

c

khởi tạo

q0

0

1

{q1; q2}

0

2

{q1; q2; q3}

1

3

{q2; q3}

1

4

{q2; q3}

1

5

{q2; q3}

1

6

{q2; q3}

1

7

{q2; q3}

$

q F = {q3} w = 0011111 L(M).

- w = 0000010.


Bước

q = (q,c)

c

khởi tạo

q0

0

1

{q1; q2}

0

2

{q1; q2; q3}

0

3

{q1; q2; q3}

0

4

{q1; q2; q3}

0

5

{q1; q2; q3}

1

6

{q2; q3}

0

7

{q1; q2}

$

q F = w = 0000010 L(M).

2.23. 1) M = <Q, , , q0, F> trong đó:

- Q = 0, 1, 2, 3;

- = a, b;

- q0 = 0 ;

- F = 3;

- :


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

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

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

(1, a) = {1, 3};

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

M = <Q, , , q0, F> trong đó:

- q0 = 0 ;

- F = 3;

- :


Q

a

b

0

{1}

{0, 1}

1

{1}

{2}

2

{3}

{3}

3

{1, 3}



3) Automat M thuộc dạng NFA vì 3 Q và a, ta có (3, a) = {1; 3}= 2 > 1.

4) - w = bbbbbbb


Bước

q = (q,c)

c

khởi tạo

0

b

1

{0; 1}

b

2

{0; 1; 2}

b

3

{0; 1; 2; 3}

b

4

{0; 1; 2; 3}

b

5

{0; 1; 2; 3}

b

6

{0; 1; 2; 3}

b

7

{0; 1; 2; 3}

$

q F = {3} w = bbbbbbb L(M).



- w = bbbaaab.


Bước

q = (q,c)

c

khởi tạo

0

b

1

{0; 1}

b

2

{0; 1; 2}

b

3

{0; 1; 2; 3}

a

4

{1; 3}

a

5

{1; 3}

a

6

{1; 3}

b

7

{2}

$

q F = w = bbbaaab L(M).

2.24. 1) M = <Q, , , q0, F> trong đó:

- Q = q0, q1, q2, q3;

- = 0, 1;

- q0 = q0 ;

- F = q3;

- :

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

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

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

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

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

0


0, 1

1

0

0


Start

q0

1

q1

0,

0

q2

1

q3

0

1


3) Automat M thuộc dạng NFA vì q3 Q mà ( q3, ) = {q0}. 4) - w = 00000000;

Bước

q = -closure((q,c))

c

khởi tạo

{q0, q2}

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}

$

q F = {q3} w = 00000000 L(M).

- w = 11100111


Bước

q = -closure((q,c))

c

khởi tạo

{q0, q2}

1

1

{q1, q2, q3}

1

2

{q0, q1, q2, q3}

1

3

{q0, q1, q2, q3}

0

4

{q0, q1, q2, q3}

0

5

{q0, q1, q2, q3}

1

6

{q0, q1, q2, q3}

0

7

{q0, q1, q2, q3}

$

q F = {q3} w = 1110010 L(M).

2.25. 1) M = <Q, , , q0, F> trong đó:

- Q = 0, 1, 2, 3, 4;

- = a, b;

- q0 = 0 ;

- F = 2, 4;

- :

(0, a) = {3}; (0, b) = {0}; (0, ) = {1}

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