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

, q
1
q
2

q
1

q
2
q
2
, q
0

q
1

q
2
q
2
q
0

q
1

q
1

2

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
}


q
0
q
1
q
2

q
0
q
1
q
2

q
0
q
1
q
3

q
1

q
4
q
2

q

2
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

5
q
3

q
4

q
3
q
0

q
4

q
2
q
3

q
5

q
4
q
6

q
5

1
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

1
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
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


(Ghi chú : chng hn nu w có cha 000 thì xem nh chui con 00 xut hin đn 2 ln.)
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
r

: 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
l

:
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
PHN NGÔN NG PHI NG CNH

(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
1

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
A → BAa A → BBa

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
(w) ≤ n

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
= aabbbb

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
k

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
= {a

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