1
Ngôn ngữvà sựphân cấp Chomsky
Nội dung:
• Khái niệm ngôn ngữ
• Cách biểu diễn ngôn ngữ
•Văn phạm
• Sựphân lớp văn phạm
Chương 2:
2
Ký hiệu, bộchữcái, chuỗi
Ký hiệu (symbol): là một thực thểtrừu tượng mà ta
không định nghĩa được một cách hình thức
• Các chữcái a, b, c … hoặc các số1, 2, 3 …
Bộchữcái (alphabet):Σ
• Là một tập (không rỗng) các ký hiệu nào đó
• Bộchữcái Latin {A, B, C, …, a, b, c, …, z}
Chuỗi (string):một chuỗi (hay một từ- word) trên bộ
chữcái Σ
• Là một dãy hữu hạn các ký hiệu của Σ
• Một ký hiệu có thểxuất hiện nhiều lần
3
Chuỗi
Độ dài chuỗi: là sốcác ký hiệu tạo thành chuỗi
•|abca|= 4
Chuỗi rỗng:ký hiệu ε, là chuỗi không có ký hiệu nào
• |ε| = 0
Chuỗi con:chuỗi v là chuỗi con của w nếu v được tạo
bởi các ký hiệu liền kềnhau trong chuỗi w.
• Chuỗi 10 là chuỗi con của chuỗi 010001
Chuỗi tiền tố:là chuỗi con bất kỳnằm ở đầu chuỗi
Chuỗi hậu tố:là chuỗi con bất kỳnằm ởcuối chuỗi
• Chuỗi abc có các tiền tốa, ab, abc
• Chuỗi 0246 có các hậu tố6, 46, 246, 0246
4
Chuỗi
Chuỗi nối kết (ghép): là chuỗi được tạo thành bằng
cách viết chuỗi thứnhất, sau đó viết chuỗi thứhai, ...
• Nối ghép của chuỗi Long và Int là LongInt
• Nối kết của chuỗi rỗng: εw = wε= w (với mọi w)
→εlà đơn vịcủa phép nối kết
Chuỗi đảo ngược: của chuỗi w, ký hiệu wR, là chuỗi
w được viết theo thứtự ngược lại.
w = abcd →wR= dcba εR= ε
5
Ngôn ngữ(Languages)
Tổng quan vềngôn ngữ:
• Ngôn ngữtựnhiên: tiếng Việt, tiếng Anh, …
• Ngôn ngữlập trình: Pascal, C/C++, …
• Là tập hợp các câu theo cấu trúc quy định nào đó
• Biểu thịcác ý nghĩ, các sựkiện hay các khái niệm
• Bao gồm một tập các ký hiệu và các quy tắc để
vận dụng chúng