• Nếu A → β là luật sinh trong văn phạm G và α, γ là 2 chuỗi bất kỳ, thì khi áp dụng luật sinh A → β vào chuỗi αααα γγγγ ta sẽ thu ñược chuỗi αβγαβγαβγαβγ :
α γ ⇒⇒⇒⇒G αββββγ
• Văn phạm phi ngữ cảnh (CFG)
• Giả sử: α1 ⇒⇒⇒⇒G α2, α2 ⇒⇒⇒⇒G α3, ..., αm-1 ⇒⇒⇒⇒G αm, ta có:
• Giản lược văn phạm phi ngữ cảnh
α1 ⇒⇒⇒⇒ G αm
• Chuẩn hóa văn phạm phi ngữ cảnh
• Ta có: α ⇒⇒⇒⇒ G α với mọi chuỗi α • Thông thường, ta sẽ dùng ⇒⇒⇒⇒ và ⇒⇒⇒⇒ thay cho ⇒⇒⇒⇒G và ⇒⇒⇒⇒ G
• Các tính chất của văn phạm phi ngữ cảnh
cho CFG G(V, T, P, S)
∈∈∈∈
⇒⇒⇒⇒ G
(chuỗi w gồm toàn ký hiệu kết thúc và ñược dẫn ra từ S)
3
1
cây dẫn xuất (hay cây phân tích cú pháp) của một văn
là hệ thống gồm 4 thành phần • V : tập hữu hạn các biến (ký tự chưa kết thúc) • T : tập hữu hạn các ký tự kết thúc (V ∩ T = Ø) • P : tập hữu hạn các luật sinh dạng A → α α α α α∈ α∈ α∈ α∈ (V∪T • S : ký hiệu bắt ñầu của văn phạm
Q
y
ư
c :
• V: chữ in hoa (A, B, C, ..); T: chữ in thường (a, b, c, .., w, x, y..) • α, β, γ, .. biểu diễn chuỗi ký hiệu kết thúc và biến
í
(cid:4) u
V
phạm G(V, T, P, S) có ñặc ñiểm (1) Mỗi nút có một nhãn, là một ký hiệu ∈∈∈∈ (V ∪ T ∪ {ε} ) (2) Nút gốc có nhãn là S (ký hiệu bắt ñầu) (3) Nếu nút trung gian có nhãn A thì A ∈∈∈∈ V (4) Nếu nút n có nhãn A và các ñỉnh n1, n2, ..., nk là con của n theo thứ tự từ trái sang phải có nhãn lần lượt là X1, X2, ..., Xk thì A → X1X2...Xk là một luật sinh trong P (5) Nếu nút n có nhãn là ε thì n phải là nút lá và là nút con duy nhất của nút cha của nó
hay
S → AB A → aAa B → bBb
4
2
S → AB A → aA A → a B → bB B → b
d (cid:9) : G=({S, A, B}, {a, b}, P, S) với P gồm các luật sinh:
Printed with FinePrint - purchase at www.fineprint.com
xét văn phạm G({S, A}, {a, b}, P, S}, với P gồm:
một văn phạm phi ngữ cảnh G ñược gọi là văn phạm
S → aASa A → SbASSba
mơ hồ (ambiguity) nếu nó có nhiều hơn một cây dẫn xuất cho cùng một chuỗi w.
Một dẫn xuất của G:
S ⇒⇒⇒⇒ aAS ⇒ aSbAS ⇒ aabAS ⇒ aabbaS ⇒ aabbaa
xét văn phạm G với luật sinh:
S
1
E →→→→ E + E E * E (E) a
E
Với chuỗi
, ta có thể vẽ ñến 2 cây dẫn xuất khác nhau
E
S
a
A
3
2
4
E
E
E
E
A
a
S
b
6
5
8
7
+
E
E
E
E
a
a
a a +
b
11
10
9
ðiều này có nghĩa là biểu thức a + a * a có thể hiểu theo 2 cách khác
nếu G(V, T, P, S) là một CFG thì ⇒⇒⇒⇒ αααα nếu và chỉ
5
7
hoặc
nhau:
nếu có cây dẫn xuất trong văn phạm sinh ra αααα.
nếu tại mỗi bước dẫn xuất, luật sinh
ñược áp dụng vào biến bên trái nhất (phải nhất)
• Hoặc quy ñịnh rằng các phép cộng và nhân luôn ñược thực hiện theo thứ tự từ trái sang phải (trừ khi gặp ngoặc ñơn)
xét văn phạm G với luật sinh:
→→→→ →→→→ →→→→
E →→→→ E + T E * T T T →→→→ (E) a
• Các dẫn xuất khác nhau cho từ
:
• Hoặc quy ñịnh rằng khi không có dấu ngoặc ñơn ngăn cách thì phép nhân luôn ñược thực hiện ưu tiên hơn phép cộng
⇒⇒⇒⇒ ⇒⇒⇒⇒
⇒⇒⇒⇒ ⇒⇒⇒⇒
⇒⇒⇒⇒ ⇒⇒⇒⇒
⇒⇒⇒⇒
⇒⇒⇒⇒
E →→→→ E + T T T →→→→ T * F F F →→→→ (E) a
⇒⇒⇒⇒ ⇒⇒⇒⇒ ⇒⇒⇒⇒ ⇒⇒⇒⇒ ⇒⇒⇒⇒ ⇒⇒⇒⇒ ⇒⇒⇒⇒ ⇒⇒⇒⇒
⇒⇒⇒⇒ ⇒⇒⇒⇒ ⇒⇒⇒⇒ ⇒⇒⇒⇒
⇒⇒⇒⇒ ⇒⇒⇒⇒
⇒⇒⇒⇒
⇒⇒⇒⇒
• Dẫn xuất (a) là dẫn xuất trái nhất, (b) là dẫn xuất phải nhất • Các dẫn xuất tuy khác nhau, nhưng có cùng một cây dẫn xuất
6
8
a a a a
Printed with FinePrint - purchase at www.fineprint.com
l
i
i
i
i
t
t
(
)
k
k
ý
k
r
c
c
c
Cho CFG G(V, T, P, S) với L(G) ≠ Ø, có một CFG G'(V', T', P', S) tương ñương sao cho mỗi ∈∈∈∈ tồn tại ∈∈∈∈ ñể ⇒⇒⇒⇒
● Các ký hiệu không tham gia vào quá trình dẫn xuất ra chuỗi ký hiệu kết thúc ● Luật sinh dạng A →→→→ B (làm kéo dài chuỗi dẫn xuất)
3 7 , , ) b á b h ô d h h ú h 9 o u u & n g n ac n
i
l
i
l
t
í
(cid:16)
c
v
y
v
c
ư
ư
m
m
,
Begin
⇒⇒⇒⇒ g
'
l
(
)
V
O
l
i
i
t
k
k
(cid:16)
:
c
y
s
s
c
v
ư
m
'
i
(
)
{
*
}
V
O
N
;
:
w
m
A→→→→ w
w∈∈∈∈ T
l
(
V
V
N
O
w
'do
A '≠≠≠≠
) While begin
'
'
l
(
)
(cid:12) (cid:17) (cid:19) ă h b (cid:15) h ô h (cid:2) h h o n (cid:10) n p n (cid:10) n n g u n n g (cid:5) (cid:26) 1 d h ô ñ à ñ h (cid:2) h ô (cid:28) ă (cid:2) ă h n n a n g n g n n g n n g a n (cid:5) =∅∅∅∅ ; 2 e v = h p (cid:10) 3 d e
V
V
N
O
;
:
w
'
'
l
l
(
)
)
*
}
V
V
V
O
N
O
:
w
'∪∪∪∪ {
A
A→→→→ αααα v
i αααα ∈∈∈∈ (
end;
'
'
(
)
4 d e = 5 d d e = T∪∪∪∪ O
V
V
N
;
:
w
9
11
6 e =
• Mỗi biến và mỗi ký hiệu kết thúc của văn phạm ñều xuất hiện trong dẫn xuất của một số chuỗi trong ngôn ngữ • Không có luật sinh A →→→→ B (với A, B ñều là biến) ● Nếu ngôn ngữ không chấp nhận chuỗi rỗng ε thì không cần luật sinh A →→→→ ε .
End;
i
l
i
i
t
t
)
(
k
ý
k
[
r
c
c
c
ư
một ký hiệu X ñược gọi là có ích nếu có một dẫn xuất
⇒⇒⇒⇒ αααα β β β β ⇒⇒⇒⇒
ñể
∪∪∪∪
∪∪∪∪
Cho CFG G(V, T, P, S), ta có thể tìm ñược CFG G'(V', T', P', S) tương ñương sao cho mỗi ∈∈∈∈
tồn tại αααα ββββ ∈∈∈∈
với α, β là các chuỗi bất kỳ và w ∈∈∈∈ T*.
i
i
í
k
ý
\ ] 3 , ) h b ñ 9 h ô d ñ b á b u o u n a n n g & Z
c
c
c
c
m
⇒⇒⇒⇒ αααα ββββ
⇒⇒⇒⇒ c
h h " ó h ó 2 ñ (cid:31) ñ o u
• X phải dẫn ra chuỗi ký hiệu kết thúc • X phải nằm trong dẫn xuất từ S
• ðặt V' = {S} ; T' = Ø • Nếu A ∈ V' và A → αααα 1 αααα 2............αααα nlà các luật sinh trong P thì
➢ Thêm các biến của αααα 1 αααα 2 ..., α..., α..., α..., α nvào
➢ Thêm các ký hiệu kết thúc của αααα 1 αααα 2 ..., α..., α..., α..., α nvào
• Lặp lại cho ñến khi không còn biến hoặc ký hiệu kết thúc nào ñược thêm vào nữa
12
10
Printed with FinePrint - purchase at www.fineprint.com
loại bỏ luật sinh ε trong văn phạm sau: S → AB A → aA ε B → bB ε
B
c
ư
➢
xét văn phạm
i. A → ε ⇒⇒⇒⇒ A ∈∈∈∈ Nullable ii. B → ε ⇒⇒⇒⇒ B ∈∈∈∈ Nullable iii.S → AB ⇒⇒⇒⇒ S ∈∈∈∈ Nullable
(cid:4) 1: xác ñịnh tập biến rỗng Nullable
B
S → A A → aBb | ε B → A | cB | cC C → AC | BCD D → ab
c
ư
➢
• Áp d(cid:17)ng b(cid:18) ñ(cid:20) 1: V' = {S, A, B, D}
: xây dựng tập luật sinh P' S → AB Aε εB A → aA aε B → bB bε
2 (cid:4)
C
ý: văn phạm G' không chấp nhận chuỗi rỗng ε như văn phạm G.
• Áp d(cid:17)ng b(cid:18) ñ(cid:20) 2: V' = {S, A, B} S → A A → aBb | ε B → A | cB
13
15
ðể G' tương ñương G, ta cần thêm luật sinh S → ε vào G'.
S → A A → aBb | ε B → A | cB D → ab
h ú
l
i
l
i
t
(
)
s
l
i
l
i
t
(
)
s
A → B
A → ε
Mỗi CFL không chứa ε ñược sinh ra bởi CFG không có ký hiệu vô ích, không có luật sinh ε hoặc luật sinh ñơn vị.
Cho CFG G(V, T, P, S) và L là ngôn ngữ sinh ra bởi G. Khi ñó L – {ε} là ngôn ngữ sinh ra bởi CFG G'(V, T, P', S) không có ký hiệu vô ích và không có luật sinh ε.
ñặt L=L(G) là CFL không chứa ε và ñược sinh ra bởi văn
) b (cid:0) h ) o & u n b (cid:0) h o & u n
B
c
ư
➢
phạm G(V, T, P, S). Theo ñịnh lý 3, ta có thể loại bỏ tất cả luật sinh ε trong G.
ðể loại bỏ luật sinh ñơn vị, ta xây dựng tập P' mới theo giải thuật:
(cid:4) 1: xác ñịnh tập biến rỗng Nullable
i. A → ε ⇒⇒⇒⇒ A ∈∈∈∈ Nullable ii.B → X1X2...Xn, ∀∀∀∀Xi ∈ Nullable⇒⇒⇒⇒ B ∈∈∈∈ Nullable
B
c
ư
F
r (mỗi biến A ∈∈∈∈ V)
➢
i
B
: xây dựng tập luật sinh P'
Với mỗi luật sinh A → X1X2...Xn trong P, ta xây dựng luật sinh
Tính ∆A = { B B ∈∈∈∈ V và A ⇒⇒⇒⇒ *B } ;
d o o 2 (cid:4) e g n
A → α1α2...αn với ñiều kiện:
r (mỗi biến B ∈∈∈∈ ∆A)
r (mỗi luật sinh B → α thuộc P)
I
16
14
f (B → α không là luật sinh ñơn vị) t Thêm luật sinh A → α vào P'
E
F d o o F d o o h e n
i. Nếu Xi ∉ Nullable thì αi = Xi ii. Nếu Xi ∈ Nullable thì αi = Xi ε iii. Không phải tất cả αi ñều bằng ε
n d ;
Printed with FinePrint - purchase at www.fineprint.com
tìm văn phạm có dạng CNF tương ñương văn phạm sau:
S → A ABA A → aA a B B → bB b
loại bỏ luật sinh ñơn vị trong văn phạm E →→→→ E + T T T →→→→ T * F F F →→→→ (E) a
B
c
ư
Ta có: ∆E = {E, T, F} ⇒⇒⇒⇒ thêm vào P' các luật sinh
E →→→→ E + T T * F (E) a
S → aA a bB b ABA A → aA a bB b B → bB b
(cid:4) 1: ∆s = {S, A, B} , ∆A = {A, B} , ∆B = {B}
B
c
ư
Tương tự:
phải > 1:
∆T = {T, F} ⇒⇒⇒⇒ thêm vào P' : T →→→→ T * F (E) a ∆F = {F} ⇒⇒⇒⇒ thêm vào P' : F →→→→ (E) a
19
17
S → CaA a CbB b ABA A → CaA a CbB b B → CbB b Ca → a Cb → b
(cid:4) 2: thay a bằng Ca và b bằng Cb trong các luật sinh có ñộ dài vế
B
c
ư
một ngôn ngữ phi ngữ cảnh bất kỳ không chứa ε ñều
→ CaA a CbB b A 1
ñược sinh ra bằng một văn phạm nào ñó mà các luật sinh có dạng A →→→→ BC hoặc A →→→→ a, với A, B, C là biến và a là ký hiệu kết thúc.
giả sử CFL L=L(G) với CFG G(V, T, P, S)
(cid:4) 3: thay thế các luật sinh có ñộ dài vế phải > 2:
B
c
ư
➢
• Áp dụng ñịnh lý 4.4 ñể loại bỏ luật sinh ñơn vị và ε
(cid:4) 1: thay thế tất cả các luật sinh có ñộ dài vế phải là 1
B
c
ư
➢ có chứa ký hiệu kết thúc
A → CaA a CbB b B → CbB b Ca → a Cb → b 1 →
A → X1X2...Xi...Xn
A → X1X2...Ca...Xn Ca → a
a
(cid:4) 2: thay thế tất cả luật sinh có ñộ dài vế phải lớn hơn 1 và
B
c
ư
➢ hiệu chưa kết thúc
A → B1B2...Bm (m>2)
18
20
A → B1 D1 D1 → B2 D2 ... Dm-2 → Bm-1 Bm
(cid:4) 3: thay thế các luật sinh mà vế phải có nhiều hơn 2 ký
Printed with FinePrint - purchase at www.fineprint.com
l
i
i
i
j
t
t
t
t
t
t
t
ì
(
)
(
)
A
r
y
c
c
s
c
y
s
c
(cid:1)
i→ A
i γ t
→ A
Begin (1) for k := 1 to m do begin (2) (3)
for j := 1 to k-1 do for Mỗi luật sinh dạng A
α do j
k
begin
(4)
for Tất cả luật sinh A
→ β do
Cho G(V, T, P, S) là một CFG, ñặt A → α1Bα2 là luật sinh trong P và B → β1β2 βr là các B - luật sinh; văn phạm G1(V, T, P1, S) thu ñược từ G bằng cách loại bỏ luật sinh A → α1Bα2 và thêm vào luật sinh A → α1β1α2α1β2α2............α1βrα2 tương ñương G
j
, , , h h á (cid:0) h h h h h > a u n p a a o o
i
i
l
t
(
)
(5) Thêm luật sinh A
r
v
y
m
α
(6) Loại bỏ luật sinh A
→ βα; k → A k
j
end;
(7)
for Mỗi luật sinh dạng A
α do → A k k
begin
; → αB k k
(9) Loại bỏ luật sinh A
→ α và B (8) Thêm các luật sinh B k α → A k k
ðặt G(V, T, P, S) là CFG; A → Aα1Aα2............Aαr là tập các A – luật sinh có A là ký hiệu trái nhất của vế phải (luật sinh ñệ quy trái). ðặt A → β1β2 βs là các A - luật sinh còn lại; G1(V ∪ {B}, T, P1, S) là CFG ñược tạo thành bằng cách thêm biến mới B vào V và thay các A - luật sinh bằng các luật sinh dạng:
(10)
end; for Mỗi luật sinh A
(1 ≤ i ≤ s)
(11) Thêm luật sinh A
do → β trong ñó β không bắt ñầu bằng A k k → βB k
k
A → βi A → βiB
B → αi B → αiB (1 ≤ i ≤ r)
21
23
end;
end;
Thì ta có G1 tương ñương G, hay L(G) = L(G1)
mỗi CFL bất kỳ không chứa ε ñược sinh ra bởi một CFG
tìm văn phạm có dạng GNF cho văn phạm G sau:
) d ù b ă h ñ 9 á o n g & n p & q u
i
i
c
c
mà mỗi luật sinh có dạng A → aα với A là biến, a là ký hiệu kết thúc và α là một c
A1 → A2A1 A2A3 A2 → A3A1 a A3 → A2A2 b
ðặt G là CFG sinh ra CFL không chứa ε
(cid:8) (cid:17) h á b u n (có thể rỗng)
B
c
ư
B
c
ư
B
c
ư
B
c
ư
B
c
ư
là ký hiệu bắt ñầu. ðặt V = {A1, A2, ..., Am}
B
c
ư
A
A
A
A
(cid:4) (cid:4) (cid:4) (cid:4) (cid:4) 1: xây dựng G' có dạng CNF tương ñương G 2: ñổi tên các biến trong G' thành A1, A2, ..., Am (m ≥1 ) với A1 1: G thỏa CNF 2: ta có V = {A1, A2, A3} 3: ta cần sửa ñổi luật sinh A3 → A2A2 (cid:4)
i
i
t
• Áp dụng bổ ñề 3: A3 → A3A1A2 aA2 2 a
t)
1 3 (cid:2) h (cid:11) 3 →→→→ A 2 b g u
)
B
c
ư
)
B
c
ư
22
24
• Áp dụng bổ ñề 4, ta thu ñược tập luật sinh: A1 → A2A1 A2A3 A2 → A3A1 a A3 → aA2 b aA2B bB B → A1A2 A1A2B
3: thay thế luật sinh sao cho nếu Ai → Ajγ thì j > i • Nếu j i), Ai → aγ hoặc Bk → γ với γ ∈ (V ∪ {B1,B2, ...,Bi-1})* (cid:26) (cid:14) á b ñ 3 d (cid:4) (cid:9) p n g (cid:26) (cid:14) b ñ 3 (cid:4) 4: thay thế các Ai – luật sinh về ñúng dạng ( 5: thay thế các Bk – luật sinh về ñúng dạng (
Printed with FinePrint - purchase at www.fineprint.com
B
c
ư
CFL ñóng với phép hợp, phép kết nối và phép bao ñóng
Kleen.
B → A1A2 A1A2B
CFL không ñóng với phép giao
CFL không ñóng với phép lấy phần bù
A3→ aA2 b aA2B bB A2→ aA2A1 bA1 aA2BA1 bBA1 a A1→ aA2A1A1 bA1A1 aA2BA1A1 bBA1A1 aA1 aA2A1A3 bA1A3 aA2BA1A3 bBA1A3 aA3
(cid:4) 4: A3 ñã có dạng chuẩn. Thay thế A3 vào A2 : (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
B
c
ư
(cid:4) 5: thay thế các Bk – luật sinh
B → aA2A1A1A2 bA1A1A2 aA2BA1A1A2 bBA1A1A2 aA1A2 aA2A1A3A2 bA1A3A2 aA2BA1A3A2 bBA1A3A2 aA3A2 aA2A1A1A2B bA1A1A2B aA2BA1A1A2B bBA1A1A2B aA1A2B
aA2A1A3A2B bA1A3A2B aA2BA1A3A2B bBA1A3A2B aA3A2B
25
27
cho L là một CFL bất kỳ, tồn tại một số n chỉ phụ thuộc
vào L sao cho nếu z ∈ L và |z| ≥ n thì ta có thể viết z=uvwxy sao cho: |vx| ≥ 1, |vwx| ≤ n và ∀i ≥ 0 ta có uviwxiy ∈ L
chứng minh một ngôn ngữ không là CFL
chứng minh L = {aibici | i ≥ 1} không là CFL
• Giả sử L là CFL, khi ñó tồn tại số n theo bổ ñề bơm • Xét chuỗi z = anbncn, |z| ≥ n, ta có thể viết z=uvwxy thỏa bổ ñề • Ta có: vx ∈ anbncn, |vx| ≤ |vwx| ≤ n nên vx không thể chứa cả ký hiệu a và c (vì giữa a và c có n ký hiệu b) • Do |vx| ≥ 1 và trong uvwxy chứa số ký hiệu a, b, c bằng nhau: Nếu vx có chứa ký hiệu a (và không chứa ký hiệu c) thì chuỗi uv0wx0y ∉ L vì có số ký hiệu c lớn hơn số ký hiệu a Nếu vx không chứa ký hiệu a thì chuỗi uv0wx0y ∉ L vì có số ký hiệu b (hoặc c) nhỏ hơn số ký hiệu a
26
(cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
![Bài giảng Tin học cơ bản 2 [Mới nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250814/kimphuong1001/135x160/41591755162280.jpg)
![Bài giảng Tin học đại cương Trường Đại học Tài chính – Marketing [Mới nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250806/kimphuong1001/135x160/15131754451423.jpg)
![Bài giảng Tin học căn bản: Chương 2 - Microsoft Word [Mới Nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250730/kimphuong1001/135x160/44421753847945.jpg)
![Đề thi cuối học kì 2 môn Cấu trúc dữ liệu và giải thuật [kèm đáp án/mới nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20251014/lakim0906/135x160/89711760416179.jpg)
