1/41
Vănphạm và ngôn ngữ sinh văn
phạm
• Định nghĩa ngôn ngữ hình thức
• Định nghĩavănphạm, ngôn ngữ sinh văn
phạm và phân loạivănphạmcủa
Chomsky
•Mộtsố thuật toán thường gặptrênlớpvăn
phạm
2/41
Định nghĩangônngữ hình thức
•Bảng chữ cái
•Xâukýtự
• Ngôn ngữ
3/41
Ngôn ngữ hình thức
Bảng chữ cái
•Cho∑ là mộttậphữuhạn, khác rỗng các
ký hiệu nào đómàtagọilàbảng chữ cái.
Mỗiphầntử trong ∑đượcgọilàmộtkýtự
•Vídụ∑={a,b,c,d,….,y}
∑={1,2,3} ;
4/41
Xâu ký tự
•Làmột dãy các ký tự trong bảng chữ cái ∑
đượcviếtliền nhau
• Độ dài xâu: là số ký tự trong xâu đó
•Vídụ∑={a,b,c} . s= “baccba” là mộtxâu
trên bảng chữ cái ∑. Xâu s có độ dài bằng
6
•Xâurỗng: là xâu không có ký tự nào, độ

dạng aÆb, a, b là các từ trên từđiển đầy đủ
8/41
Vănphạm và ngôn ngữ sinh bởi
vănphạm
• Định nghĩavănphạm:
– Định nghĩa2: ChoG= < ∑,∆,I,R > là mộtvăn
phạm, mộtxâux= αaβ. S = αbβđượcgọilà
dẫnxuấttrựctiếptừ xâu x nếutaápdụng
quy tắc(luật) aÆb. Ký hiệulàx╞ s.
– Định nghĩa3: DãycácxâuD = (w
0
,w
1
,….,w
k
)
đượcgọilàmộtdẫnxuấtcủaxâuw
k
từ w
0
nếu
w
i
╞ w
i+1
với i=0...k-1. Số k đượcgọilàđộ dài
củadẫnxuất. Ký hiệulàw
0
|- w
k

Ngôn ngữ sinh bởivănphạm
Ví dụ
•ChoG= < ∑,∆,I,R > với ∑={a,b} , ∆ = {I},
R= {I Æ aIb, IÆab}; L(G) =?.
– Chúng ta thấyrằng L(G)={a
n
b
n
| n€N, n>=1}
–Thậtvậydẫnxuất đầy đủ là
» D= {I,aIb,…. ,a
n
b
n
}
11/41
Vănphạm
Ví dụ
•ChoG=< ∑,∆,I,R > trong đó ∑={a,b},
∆={A,B,I}, I là ký hiệuxuất phát và
R={IÆAba, AÆ BB, BÆab,ABÆb}.
12/41
Phân loạivănphạm
• Nhóm 0: Vănphạmngữ cấu
• Nhóm 1: Vănphạmcảmngữ cảnh
• Nhóm 2: Vănphạm phi ngữ cảnh
• Nhóm 3: Vănphạm chính quy
13/41
Phân loạivănphạm
Vănphạmngữ cấu