Bài tập Lý thuyết Ngôn ngữ Hình thức và Automata

Trường ĐH Bách Khoa - Khoa CNTT - Người soạn: Hồ Văn Quân 1/5
BÀI TẬP LÝ THUYẾT NNHT&AUTOMATA
PHẦN NGÔN NGỮ CHÍNH QUI
1. Tìm các dfa cho các ngôn ngữ sau:
L
1
= {w ∈ {a, b}*: n
a
(w) mod 2 = 0, n
b
(w) mod 2 = 1}
L
2
= {w ∈ {0, 1}*: mỗi chuỗi 00 được theo ngay sau bởi một số 1}
L
3
= {tập tất cả các danh hiệu của Pascal}
Mô tả danh hiệu: bắt đầu bằng một kí tự chữ (a đến z, A đến Z) hoặc dấu gạch dưới
(_) sau đó là một chuỗi bất kỳ bao gồm các kí tự chữ, số (0 đến 9) và dấu gạch dưới.
L
4
= {tập tất cả các số nguyên của Pascal}
Mô tả số nguyên: 12, +12, -12
{tập tất cả các số thực của Pascal}
Mô tả số thực: 12.5, +12.5, -12.5, 12E3, +12E3, -12E3, 12E-3, +12E+3, -12E+3,
+12E3, -12E3, 12E-312.5, +12.5, -12.5, ... Có thể có bao nhiêu số 0 đi đầu đều được,
ví dụ: 012, 0012, +012, -012, 012.5, ... Có thể được viết dưới dạng khoa học như sau:
12E3, 12.5E3, +12.5E3, -12.5E3, 12.5E+3, 12.5E-3, -12.5E-3, ...
2. Tìm các dfa cho các tập sau trên Σ = {a, b} bao gồm:

L
14
= {kí hiệu thứ tư từ bên phải khác với kí hiệu trái nhất.}
5. Xây dựng một dfa mà chấp nhận các chuỗi trên {0, 1} nếu và chỉ nếu giá trị của chuỗi, được diễn
dịch như là biểu diễn nhị phân của một số nguyên, là bằng 0 trong modulo của 5. Chẳng hạn,
0101 và 1111, biểu diễn tương ứng các số nguyên 5 và 15, là được chấp nhận.
6. Tìm dfa chấp nhận ngôn ngữ sau trên {a, b}:
L
15
= {vwv: w ∈{a, b}
*
, v= 2};
7. Tìm các nfa cho các ngôn ngữ sau:
L
1
= {vwv
R
∈ {a, b}*: |v| = 2}
L
2
= {abab
n
: n ≥ 0} ∪ {aba
n
: n ≥ 0} (với điều kiện nfa có không nhiều hơn 5 trạng thái)
L
3
= {a
n
b


Bài tập Lý thuyết Ngôn ngữ Hình thức và Automata

Trường ĐH Bách Khoa - Khoa CNTT - Người soạn: Hồ Văn Quân 2/5
Dfa M
1
Dfa M
2
Dfa M
3
Dfa M
4a b
λ

a b
λ

a b
λ a b
λ
q
0
q
1

1
q
2

q
1

q
2
q
2
, q
0

q
1

q
2
q
2
q
0

q
1

q
1
, q


q
0
, q
2

q
2

q
3
q
3

q
3

q
0
, q
4
q
3
q
4

q
3

q

4

q
4

q
4
q
3
F = {q
0
} F = {q
2
}
F = {q
2
} F = {q
4
}
0
q
1
q
2

q
0
q
1
q
2

q
0
q
1
q
3

q
1

q
4
q
2

q
1

q
2
q
3
q
2
q
1
q
4
q
2
q
0
q
3

q
3

q
3

q
3

q
5
q
4

q
3

q
4

q
3
q
0

q
4

q
2
q
3

q
5

q
4
q
6

q
5


q
7q
7

q
7

q
7

q
6
q
4F = {q
1
, q
4
}

F = {q
5
}
M
6

0
1
0, 1
1
0, λ
q
0
q
1
q
2
M
7
a, b
a
a
λ
b
λ
q
0

q
1

q
3

q
5
q
4

q
6
q
3

b
M
6

b
b
a
b
b
b
b
b
a
a
a
a
a
q
0


a
a
b
A
B
F
D
C
G
E
M
8

0
1
0,1
0
0
1
1
0,1
0,1
q
0
q
1
q
2

q

L
3
= {w ∈ {0, 1}*: w bắt đầu bằng 0 kết thết bằng 1 và không chứa chuỗi con 00}
12. Tìm biểu thức chính qui cho các nfa sau:

Nfa M
1
Nfa M
2a B a b
q
0
q
1
q
1q
0
q
1
q
2


}

q
3

q
2

F = {q
3
}
13. Xây dựng các nfa và các dfa cho các BTCQ sau:
r
1
= aa* + aba*b*
r
2
= ab(a + ab)* (b + aa)
r
3
= ab*aa + bba*ab
r
4
= a*b(ab + b)*a*
r
5
= (ab* + a*b)(a + b*a)* b

1
: M
2
: 17. Sử dụng bổ đề bơm để chứng minh các ngôn ngữ sau là không chính qui:
L
1
= {a
2n
b
l
: n ≥ 0, l ≥ n + 2}
L
2
= {a
n
b
l
c
k
: n = l+1 hoặc l ≠ k + 2}
18. Áp dụng tính đóng của họ NNCQ đối với các phép toán để chứng minh ngôn ngữ sau đây là
không chính qui:
L
1
= {a
n
b

2
:
a
b
a
a, b
a
b
b b
p
0

p
1

p
2

b
b
a a
q
0
q
2
q
1
Bài tập Lý thuyết Ngôn ngữ Hình thức và Automata

Trường ĐH Bách Khoa - Khoa CNTT - Người soạn: Hồ Văn Quân 4/5

b
(w)}
L
5
= {a
n
b
m
: 2n ≤ m ≤ 3n}
20. Hãy sử dụng phương pháp phân tích cú pháp vét cạn để phân tích các chuỗi w
1
, w
2
sau có được
sinh ra bởi văn phạm sau hay không:
w
1
= aababb, w
2
= abababb.
S → aSb|SS|aA
A → aAa|bAb|a|b.
21. Hãy phân tích cú pháp cho các chuỗi w sau trên các văn phạm G tương ứng. Trình bày dẫn xuất
trái nhất nếu chuỗi thuộc văn phạm
G
1
: S → aAS | bBS | λ (1, 2, 3)
A → aAA | b (4, 5)
B → bBB | a (6, 7)
w

loại 1; việc loại bỏ luật sinh-đơn vị có thể sinh ra luật sinh vô dụng loại 2; việc loại bỏ luật sinh vô
dụng loại 1 có thể sinh ra luật sinh vô dụng loại 2.
25. Hãy loại bỏ đồng thời các luật sinh-rỗng, luật sinh-đơn vị, luật sinh-vô dụng của văn phạm sau:
S → aABC D → b|bS
A → λ E → cEF
B → λ F → d|dF.
C → AB|D|aE
26. Hãy biến đổi các văn phạm sau sang các văn phạm có dạng chuẩn Greibach tương đương:
G
1
: S → BAbABa G
2
: S → SAa
A → aAb A → SbASa
B → bBaAa
27. Sử dụng giải thuật CYK để xác định các chuỗi w
1
= abab, w
2
= abaa có được sinh ra bởi các văn
phạm tương ứng G
1
, G
2
sau đây hay không, nếu có hay đưa ra các dẫn xuất trái nhất cho chúng:
G
1
: S → ABBB G
2
: S → AB

b
m
: 2n ≤ m ≤ 3n} w
3
= aabbbbb
Bài tập Lý thuyết Ngôn ngữ Hình thức và Automata

Trường ĐH Bách Khoa - Khoa CNTT - Người soạn: Hồ Văn Quân 5/5
L
4
= {w: n
a
(w) = n
b
(w) + 2} w
4
= abaaba
L
5
= {w: n
a
(w) = 2n
b
(w)} w
5
= abbaaa
L
6
= {w: 2n
b


G
1
: S → aAS | bBS | λ (1, 2, 3)
A → aAA | b (4, 5)
B → bBB | a (6, 7)
w
1
= abba, w
2
= bbaaab
G
2
: S → aS | bXaS (1, 2)
X → aXbX | bXaX | λ (3, 4, 5)
w
1
= abaab, w
2
= baaab
31. Hãy xây dựng các dpda cho các ngôn ngữ sau và tìm các dãy chuyển hình trạng để chấp nhận các
chuỗi được cho tương ứng ở bên cạnh.
L
1
= {a
n
b
2n
: n ≥ 0} w
1

= {w: n
a
(w) = n
b
(w)} w
1
= abbaab
L
2
= {w: n
a
(w) > n
b
(w)} w
2
= abbaaba
L
3
= L(a*ba) ∪ L(abbb*) w
3
= abbb
34. Hãy xét xem các ngôn ngữ cho sau đây có PNC hay không. Nếu không hãy sử dụng bổ đề bơm
cho NNPNC để chứng minh.
L
1
= {a
n
b
j
c

: n + j ≤ k + l}
L
3
= {a
n
b
j
c
k
: n < j, n ≤ k ≤ j} L
7
= { a
n
b
j
a
k
b
l
: n ≤ k, j ≤ l}
L
4
= {w: n
a
(w) < n
b
(w) < n
c
(w)} L
8

n
b
j
: j ≤ n ≤ 2j - 1}
L
4
= L(G) với G được cho như sau:
E → T|E + T
T → F|T * F
F → I|(E)
I → a|b|c
36. Cho văn phạm G sau. Hãy phân tích cú pháp cho các chuỗi w
1
= (a+b*c)*a và w
2
= (a + b)*+c
theo phương pháp Earley.
G:
E → T|E + T F → I|(E)
T → F|T * F I → a|b|c