Bài giảng Tin học: Chương 2 - Võ Huỳnh Trâm

Bài giảng "Tin học - Chương 2: Ngôn ngữ và sự phân cấp Chomsky" cung cấp cho người học các kiến thức: 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. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Tin học: Chương 2 - Võ Huỳnh Trâm là số các ký hiệu tạo thành chuỗi • abca = 4 ký hiệu , là chuỗi không có ký hiệu nào • Khái niệm ngôn ngữ • |ε| = 0 • Cách biểu diễn ngôn ngữ chuỗi v là chuỗi con của w nếu v ñược tạo • Văn phạm 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 0 001 • Sự phân lớp văn phạm là chuỗi con bất kỳ nằm ở ñầu chuỗi 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 1 • Chuỗi 0246 có các hậu tố 6, 46, 246, 0246 3 là một thực thể trừu tượng mà ta là chuỗi ñược tạo thành bằng không ñịnh nghĩa ñược một cách hình thức cách viết chuỗi thứ nhất, sau ñó viết chuỗi thứ hai, ... • Các chữ cái a, b, c … hoặc các số 1, 2, 3 … •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à một tập (không rỗng) các ký hiệu nào ñó → ε là ñơn vị của phép nối kết • Bộ chữ cái Latin {A, B, C, …, a, b, c, …, z} của chuỗi w, ký hiệu wR, là chuỗi một chuỗi (hay một từ - word) trên bộ w ñược viết theo thứ tự ngược lại. chữ cái Σ •w = abcd → wR = dcba εR = ε • 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 2 4 Printed with FinePrint - purchase at www.fineprint.com • Ngôn ngữ tự nhiên: tiếng Việt, tiếng Anh, … L = Σ* - L • 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 ñó L1L2 = {w1w2 | w1 ∈ L1 và w2 ∈ L2} trên bộ chữ cái Σ1 ∪ Σ2 • Biểu thị các ý nghĩ, các sự kiện hay các khái niệm • LLL…LL = L (kết nối i lần trên cùng ngôn ngữ L) i • Bao gồm một tập các ký hiệu và các quy tắc ñể • L = {ε} 0 vận dụng chúng 5 7 Một ngôn ngữ (hình thức) L là một thành lập một ngôn ngữ của các ký hiệu từ một bộ chữ cái Σ nào ñó. bằng cách kết nối các chuỗi (với số lượng bất kỳ) các Ø và {ε} cũng ñược coi là ngôn ngữ chuỗi của một ngôn ngữ L cho trước Ø ≠ {ε} và {Ø} ≠ {ε}
Bao ñóng Kleene: L* = ∪ Li ∞ i 0 Σ Σ + = ∞ i
Bao ñóng dương (positive): L* = ∪ L ● Σ* : tập hợp tất cả các chuỗi con, kể cả chuỗi rỗng i 1 = ε, sinh ra từ bộ chữ cái Σ. L = L*L = LL* L* = L ∪ {ε} + + ● Σ+ : tập hợp tất cả các chuỗi con, ngoại trừ chuỗi rỗng ε, sinh ra từ bộ chữ cái Σ. ...