Bài giảng Lý thuyết tính toán: Bài 01 - Nguyễn Ngọc Tú

Mời các bạn cùng tìm hiểu một số khái niệm cơ bản về ngôn ngữ; văn phạm; ô tô mát; các phép toán trên ngôn ngữ;... được trình bày cụ thể trong "Bài giảng Lý thuyết tính toán: Bài 01" do Nguyễn Ngọc Tú biên soạn.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết tính toán: Bài 01 - Nguyễn Ngọc Tú LÝ THUYẾT TÍNH TOÁN INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA) Bài 01. Tổng Quan GV: Nguyễn Ngọc TúTIN331 Tu.NguyenNgoc@hoasen.edu.vnKhái niệm căn bản Ngôn ngữ (languages) Văn phạm (grammar) Ôtômát (automata)Ngôn ngữ Ngôn ngữ là gì?  Các từ điển định nghĩa ngôn ngữ một cách không chính xác là một hệ thống thích hợp cho việc 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 qui tắc để vận dụng chúng. Định nghĩa trên chưa đủ và chính xác xây dựng một định nghĩa toán học cho khái niệm ngôn ngữ Ngoân Ngöõ4  Baûng chöõ caùi (Alphabet): Moät taäp khaùc roãng (troáng) höõu haïn caùc kyù hieäu  = {a, b}  Chuoãi (String): daõy höõu haïn caùc kyù hieäu töø  w = abaaa : chuoãi roãng (empty string) *: Taäp taát caû caùc chuoãi treân  (+ = *  {})Ngoân Ngöõ Chuỗi (string), w  Là một dãy hữu hạn các kí hiệu từ bảng chữ cái. Ví dụ  Với Σ = {a, b}, thì abab và aaabbba là các chuỗi trên Σ. Qui ước  Với một vài ngoại lệ, chúng ta sẽ sử dụng các chữ cái thường a, b, c, . . . cho các phần tử của Σ còn các chữ cái u, v, w, . . . Cho các tên chuỗi. Ngoân Ngöõ6  Ngoân ngöõ: moät taäp con L cuûa *  Caâu: moät chuoãi trong L  Ví duï 1:  = {a, b} * = {, a, b, aa, ab, ba, bb, aaa, ...} L1 = {a, aa, aab} (Ngoân ngöõ höõu haïn) L2 = {anbn | n  0} = {, ab, aabb, ...}Ngoân Ngöõ Kết nối (concatenation), wv w = a1a2 ...an và v = b1b2...bm là chuỗi: wv = a1a2 ...anb1b2...bm Ðảo (reverse), wR  Ðảocủa chuỗi w = a1a2 ...an là chuỗi: wR= an...a2a1 Ngoân Ngöõ8  Keát noái ngoân ngöõ (Language concatenation): L1L2 = {xy | xL1, yL2} Ln = L L ... L (n laàn) L0 = {}  Ví duï 2: L = {anbn | n  0}  L2 = {anbnambm | n  0, m  0}Ngoân NgöõCho chuỗi w = uv Tiếp đầu ngữ (prefix) u được gọi là tiếp đầu ngữ của w Tiếp vĩ ngữ (suffix) v được gọi lá tiếp vĩ ngữ của w Chiều dài của chuỗi w Là số kí hiệu trong chuỗi, và được kí hiệu là |w| Chuỗi trống (empty string) Là chuỗi không có kí hiệu nào, thường được kí hiệu là  Ngoân Ngöõ10  Bao đóng sao (Star-closure): L* = L0  L1  L2 ...  Bao đóng dương (Positive closure): L+ = L1  L2 ...Ngôn ngữNgôn ngữ Là một tập con của Σ*, hay nói cách khác là một tập bất kỳ các câu trên bộ chữ cái.Ví dụ Cho Σ = {a, b} Σ* = {λ, a, b, aa, ab, ba, bb, aaa, aab, ...} Tập {a, aa, aab} là một ngôn ngữ trên Σ. Nó là một ngôn ngữ hữu hạn. Tập L = {anbn : n ≥ 0} cũng là một ngôn ngữ trên Σ. Nó là một ngôn ngữ vô hạn.Các phép toán trên ngôn ngữ Bù (complement), L  Bù của ngôn ngữ L trên bảng chữ cái Σ, được kí hiệu là: L = Σ* - L Kết nối, L1L2  Cho 2 ngôn ngữ L1, L2. Kết nối của 2 ngôn ngữ L1, L2 là: L1L2= { xy : x ∈ L1, y ∈ L2 } Lũy thừa, Ln  Lũy thừa bậc n của L, kí hiệu là Ln, là việc kết nối L với chính nó n lần L0 = { } L =1 LL2 3 L nlaànCác phép toán trên ngôn ngữ Ví dụ  Cho L = {anbn : n ≥ 0}, thì L2 = {anbnambm: n ≥ 0 , m ≥ 0} Bao đóng-sao (star-closure) của L  Kíhiệu là L* và được định nghĩa là L* = L0 ∪ L1∪ L2∪ ... Bao đóng dương (positive closure) của L  Kíhiệu là L+ L+ = L1∪ L2∪ L3∪ ... Vaên Phaïm14  Moät vaên phaïm (grammar) cuûa moät ngoân ngöõ töï nhieân (natural language) cho chuùng ta bieát moät caâu cuï theå coù ñöôïc caáu taïo toát hay khoâng.     a | the Các từ điển định nghĩa văn phạm một cách  boy | dog không chính xác là một tập các qui tắc về cấu  runs | walks tạo từ và các qui tắc về cách liên kết các từ lại thành câu. Văn phạmCác câu “a boy runs” và “the dog walks” là có dạngđúng“, tức là được sinh ra từ các luật của văn phạm.Định nghĩa 1.1 Văn phạm G được định nghĩa như là một bộ bốn G = (V, T, S, P) V: tập các kí hiệu không kết thúc (nonterminal symbol), còn được gọi là các biến (variable), T: tập các kí hiệu kết thúc (terminal symbol), S ∈ V: được gọi là biến khởi đầu (start variable), đôi khi còn được gọi là kí hiệu mục tiêu, P: tập hữu hạn các luật sinh (production), Văn phạm16  Vaên phaïm hình thöùc (Formal grammar): ...