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

Chia sẻ: Nguyễn Thị Huyền | Ngày: | Loại File: PDF | Số trang:29

Thêm vào BST

Báo xấu

92
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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.vn
Khá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àn
Cá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ïm 14  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ạm Cá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ạm 16  Vaên phaïm hình thöùc (Formal grammar): G = (V, T, S, P) V: taäp höõu haïn caùc bieán (variables) T: taäp höõu haïn caùc kyù hieäu keát thuùc (terminal symbols) SV: bieán khôûi ñaàu (start variable) P: taäp höõu haïn caùc luaät sinh (productions)
Văn phạm  Qui ước:  Các kí tự chữ hoa A, B, C, D, E và S biểu thị các biến; S là kí hiệu khởi đầu trừ phi được phát biểu khác đi.  Các kí tự chữ thường a, b, c, d, e, các kí số, các chuỗi in đậm biểu thị các kí hiệu kết thúc (terminal).  Các kí tự chữ hoa X, Y, Z biểu thị các kí hiệu có thể là terminal hoặc biến.  Các kí tự chữ thường u, v, w, x, y, z biểu thị chuỗi các terminal.  Các kí tự chữ thường Hi Lạp α, β, γ biểu thị chuỗi các biến và các terminal.
Vaên Phaïm 18  Caùc luaät sinh: xy x(VT)+ y(VT)*  Chuoãi w = uxv daãn xuaát ra z = uyv w  z (daãn xuaát tröïc tieáp) w1 * wn (w1  w2  ...  wn | w1 = wn) w1 + wn (ít nhaát moät luaät sinh ñöôïc aùp duïng)
Vaên Phaïm 19  Ngoân ngöõ ñöôïc sinh bôûi: G = (V, T, S, P) laø: L(G) = {wT* | S * w}  Daãn xuaát caâu (derivation): S  w1  w2  ...  wn  wL(G)  Daïng caâu (sentential forms): S, w1, w2, ..., wn (chöùa caùc bieán)
Vaên Phaïm 20  Ví duï 3: G = ({S}, {a, b}, S, P) P: S  aSb S S  aSb  aaSbb  aabb aabb: caâu aaSbb: daïng caâu L(G) = {anbn | n  0}