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

4) Viết biểu thức chính quy biểu diễn cho L(G).

Từ đồ thị của M, sử dụng giải thuật heuritic suy ra: r = 0*( (1 0(10)*0(00)* )1*(0 1)

2.38. 1) G = (N, T, P, S):

- N= {S, A, B, C};

- T = {a, b, c};

- P = {S → aA | bB| aC | b| c; A → aA | b; B → aC | aA | a | b | ε; C → bC| bB | a

| b};

- S = S.

2) M = <Q, , , q0, F>:

- Q = {S, A, B, C, D};

-  = {a, b, c};

- :

+  (S, a) = {A, C};

+  (S, b) = {B, D};

+  (S, c) = {D};

+  (A, a) = {A};

+  (A, b) = {D};

+  (B, a) = {A, C, D};

+  (B, b) = {D};

+  (B, ε) = {D};

+  (C, a) = {D};

+  (C, b) = {B, C, D};

- q0 = S;

- F = {D} vì A → ε  P.

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

- q0 = S ;

- F = D;

- :

Q 

a	b	c	ε
S	{A, C}	{B, D}	{D}
A	{A}	{D}
B	{A, C, D}	{D}		{D}
C	{D}	{B, C, D}
D

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

• Ngôn ngữ hình thức - 25
• Ngôn ngữ hình thức - 26
• Ngôn ngữ hình thức - 27
• Ngôn ngữ hình thức - 29
• Ngôn ngữ hình thức - 30
• Ngôn ngữ hình thức - 31

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

- Biểu diễn M dưới dạng đồ thị (tự làm)

4) Viết biểu thức chính quy biểu diễn cho L(G).

Từ đồ thị của M, sử dụng giải thuật heuritic suy ra biểu thức chính quy

2.39. 1) Xác định các thành phần của G (tự làm)

2) Xây dựng automat hữu hạn M: L(G) = L(M)

- Xây dựng văn phạm tuyến tính phải G‟ đảo ngược của G

- Xây dựng FA M‟ tương ứng với G‟

- Xây dựng M‟ đảo ngược của M‟

3) Biểu diễn M dưới dạng đồ thị (tự làm)

4) Viết biểu thức chính quy biểu diễn cho L(G) (tự làm)

2.40. 1) Xác định các thành phần của G (tự làm)

2) Xây dựng automat hữu hạn M: L(G) = L(M)

- Xây dựng văn phạm tuyến tính phải G‟ đảo ngược của G

- Xây dựng FA M‟ tương ứng với G‟

- Xây dựng M‟ đảo ngược của M‟

3) Biểu diễn M dưới dạng đồ thị (tự làm)

4) Viết biểu thức chính quy biểu diễn cho L(G) (tự làm)

2.41. Sử dụng ứng dụng của bổ đề Bơm để chính minh.

2.42. Ta có: L = {02n | n là số nguyên dương}= (00)+

1) Các ngôn ngữ sau không là ngôn ngữ chính quy:

b) L = {0n1m0 n+m | m, n là số nguyên dương}

c) L = {0n | n là số nguyên tố}

2) Sử dụng ứng dụng của bổ đề Bơm để chính minh.

3. Bài tập chương 3

3.21. 1) S → aS | Sb | aSb | c

a) G = (N, T, P, S):

- N = {S};

- T = {a, b, c};

- P: S → aS | Sb | aSb | c;

- S = S.

b) Tập hợp các xâu trên bảng chữ cái  = {a, b, c}, mở đầu bằng ký tự a hoặc c, kết thúc bằng ký tự b hoặc c.

2) S → SS | a | b

a) Tương tự 1a) (tự làm)

b) Tập hợp các xâu trên bảng chữ cái  = {a, b}, mở đầu bằng kí tự a hoặc b, kết thúc bằng ký tự b hoặc b.

3) S → SaS | b

a) Tương tự 1a) (tự làm)

b) Tập hợp các xâu trên bảng chữ cái  = {a, b}, có độ dài là một số lẻ và có một ký tự a ở vị trí chính giữa của xâu.

4) S → aSS | b

a) Tương tự 1a) (tự làm)

b) Tập hợp các xâu trên bảng chữ cái  = {a, b}, mở đầu bằng ký tự a, kết thúc bằng ký tự b.

5) S → aA | bB| c; A → Sa; B → Sb

a) Tương tự 1a) (tự làm)

b) Tập hợp các xâu trên bảng chữ cái  = {a, b, c} gồm có các xâu có một trong các tính chất sau:

+ Chỉ có một ký tự c;

+ Mở đầu và kết thúc bằng ký tự a và đối xứng qua ký tự c;

+ Mở đầu và kết thúc bằng ký tự b và đối xứng qua ký tự c.

6) S → AB; A → Sc | a; B → dB | b

a) Tương tự 1a) (tự làm)

b) Tập hợp các xâu trên bảng chữ cái  = {a, b, c, d} có các tính chất sau:

+ Mở đầu bằng các ký tự a;

+ Ở giữa là ký tự d hoặc c;

+ Kết thúc bằng các ký tự b .

7) S → TT; T → aTa | bTb | c

a) Tương tự 1a) (tự làm)

b) Tập hợp các xâu trên bảng chữ cái  = {a, b, c} có một trong các tính chất sau:

+ Chỉ có một ký tự c;

+ Mở đầu và kết thúc bằng ký tự a và đối xứng qua ký tự c;

+ Mở đầu và kết thúc bằng ký tự b và đối xứng qua ký tự c;

3.22. 1) Tập hợp các xâu đọc xuôi đọc ngược như nhau (đối xứng) trên bộ chữ cái Σ = {0,1}: S 0S01S1.

2) Tập hợp chuỗi các dấu ngoặc đúng trong biểu thức số học: E  E + E  E *E  E-E  E/E  (E) id.

3) Tập hợp {aibicj | i, j ≥ 0}

S AB; AaAb| ; B cB| .

4) Tập hợp {ambn | m, n > 0}

S AB; AaA| a; BbB| b.

5) Tập hợp {aicaj | i, j ≥ 0}

S AcB; AaA| a; BaB| a.

6) Tập hợp {ajbjcidi | i, j ≥ 1}

S AB; AaAb| ab; BcBd| cd

3.23. Theo định nghĩa ngôn ngữ sinh bởi văn phạm G là L(G) = {w T* S * w}.

1) - Lấy w  L(G  S * w  w T*. Các dẫn xuất từ S 1 bước chỉ có thể sử dụng một trong hai luật sinh là S  aAb |  nên dẫn xuất đó chỉ có thể là S  aAb hoặc S .

+ Nếu S  = w = anbn với n = 0  w {anbn  n  0}.

+ Nếu S  aAb thì ở các bước tiếp theo (nếu có – giả sử n -1 bước) chỉ có thể sử dụng luật sinh A  aAb  S n anAbn và ở bước suy dẫn cuối cùng để sinh ra được wT* thì buộc phải sử dụng luật sinh A  S n+1 anbn = w với n > 0 

w {anbn  n  0}.

- Lấy w {anbn  n  0} w = anbn  n  0.

+ Nếu n = 0  w =  S  = w nhờ luật sinh S .

+ Nếu n > 0  w = anbn  n > 0  S  aAb n-1 anAbn  anbn = w nhờ áp dụng 1 lần luật sinh S  aAb, n-1 lần luật sinh A  aAb, 1 lần luật sinh A .

 S n+1 w.

Vậy L(G) = {anbn  n  0}. Tương tự ta chứng minh được

2) L(G) = {ambn | m, n > 0}

3) L(G) = {aibicjdk | i, j, k ≥ 1} 3.24. 1) L(G) = {(ab)n(ba)n | n ≥0}

2) L(G) = {(01)m(abc)n | m > 0; n ≥ 0}

3) L(G) = {(01)m(abc)n | m, n ≥ 0}

3.25. 1) - Dẫn xuất trái nhất

S  aB  aaBB  aaaBBB  aaabSBB  aaabbABB  aaabbaBB

 aaabbabB  aaabbabbS  aaabbabbbA  aaabbabbba

- Dẫn xuất phải nhất

S  aB  aaBB  aaBbS  aaBbbA  aaBbba  aaaBBbba

 aaaBbSbba  aaaBbbAbba  aaaBbbabba  aaabbabbba

2) Cây dẫn xuất trái nhất, cây dẫn xuất phải nhất ra xâu w.

S

S

a

B

a B

a

B

B

a B B

B

a B b

a B B b S

S

S

b b b A

b A a

a

b b b A

S

b A a a

Cây dẫn xuất trái nhất

3.26. 1) Tự làm

2) Vẽ cây dẫn xuất sinh ra các xâu vào sau:

a) (a + b) / c

b) a × (b - c) E T

Cây dẫn xuất phải nhất

E T

T / F

F c

( E )

E + T

T * F

F ( E )

a E - T

T F T F

F b F c b)

a a) b

c) a – (b × c / d)

E

E - T

T F

F ( )

a T

T / F

T * F d

F c

b

c)

3.27. 1) Chứng tỏ văn phạm này là văn phạm nhập nhằng (mơ hồ).

Xét xâu w = abab, tồn tại hai dẫn xuất trái nhất cùng dẫn xuất ra w. Đó là:

- S  aSbS  abSaSbS  abaSbS  ababS  abab

- S  aSbS  abS  abaSbS  ababS  abab

2) Xây dựng dẫn xuất trái nhất, phải nhất và cây dẫn xuất tương ứng cho xâu abab.

- Dẫn xuất trái nhất:

S  aSbS  abS  abaSbS  ababS  abab

- Dẫn xuất phải nhất:

S  aSbS  aSb  a bSaS b  a bS ab  a ba b

- Cây dẫn xuất tương ứng:

S S

a S b S



a S b S



a S b S



a S b S



Cây dẫn xuất trái nhất sinh ra xâu abab Cây dẫn xuất phải nhất sinh ra xâu abab

3.28. 1) Văn phạm đã cho là nhập nhằng (mơ hồ).

Xét câu lệnh là xâu: IF b THEN IF b THEN a ELSE a; có hai dẫn xuất trái nhất tương ứng là:

S

if b then S

if b then S

else S

S

Và

if b then S

a a

else S

if b then S a

a

2) Văn phạm không nhập nhằng tương đương với văn phạm đã cho là: S  S1  S2  a;

S1  If b then S1 else S1  a;

S2 → If b then S  If b then S1 else S2.

3.29. 1) Văn phạm là nhập nhằng (mơ hồ).

Vì  w = a-a*a T có 2 dẫn xuất trái nhất. Đó là:

1. E  S - S  a - S  a - S * S  a - a * S  a - a * a

2. S  S * S  S - S *S  a - S * S  a - a * S  a - a * a Và có hai cây dẫn xuất trái nhất tương ứng là:

S

-

S

S

S

*

S

S

S

* S

S

a

S -

a a a

a a

a) b)