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

R
= 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
6
Ngôn ngữ (Languages)
Một ngôn ngữ (hình thức) L là một tập hợp các chuỗi
của các ký hiệu từ một bộ chữ cái Σ nào đó.
Σ* và Σ
+
:
●
Σ* : tập hợp tất cả các chuỗi con, kể cả chuỗi rỗng
ε, sinh ra từ bộ chữ cái Σ.
●
Σ

∈ L
1
và w
2
∈ L
2
} trên bộ chữ cái Σ
1
∪ Σ
2
•
LLL…LL = L
i
(kết nối i lần trên cùng ngôn ngữ L)
•
L
0
= {ε}
Các phép toán trên ngôn ngữ
L