Bài giảng Lý thuyết tính toán - Bài 01. Tổng Quan

GV: Nguyễn Ngọc Tú [email protected] Bài 01. Tổng Quan LÝ THUYẾT TÍNH TỐN INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA) TIN331 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 tốn học cho khái niệm ngơn ngữ 4 Ngôn Ngữ  Bảng chữ cái (Alphabet): Một tập khác rỗng (trống) hữu hạn các ký hiệu  = {a, b}  Chuỗi (String): dãy hữu hạn các ký hiệu từ  w = abaaa : chuỗi rỗng (empty string) *: Tập tất cả các chuỗi trên  (+ = *  {}) Ngô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. 6  Ngôn ngữ: một tập con L của *  Câu: một chuỗi trong L  Ví dụ 1:  = {a, b} * = {, a, b, aa, ab, ba, bb, aaa, ...} L1 = {a, aa, aab} (Ngôn ngữ hữu hạn) L2 = {a nbn | n  0} = {, ab, aabb, ...} Ngôn Ngữ Ngô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  Ðảo của chuỗi w = a1a2 ...an là chuỗi: wR= an...a2a1 8  Kết nối ngôn ngữ (Language concatenation): L1L2 = {xy | xL1, yL2} Ln = L L ... L (n lần) L0 = {}  Ví dụ 2: L = {anbn | n  0}  L2 = {anbnambm | n  0, m  0} Ngôn Ngữ Ngô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à  10  Bao đĩng sao (Star-closure): L* = L0  L 1  L2 ...  Bao đĩng dương (Positive closure): L+ = L1  L2 ... Ngôn Ngữ 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 tố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 L = 1 2 3 L LL L0 = { } nlần Các phép tố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∪ ... 14 Văn Phạm  Một văn phạm (grammar) của một ngôn ngữ tự nhiên (natural language) cho chúng ta biết một câu cụ thể có được cấu tạo tốt hay không.     a | the  boy | dog  runs | walks Các từ điển định nghĩa văn phạm một cách khơng chính xác là một tập các qui tắc về cấu 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), 16  Văn phạm hình thức (Formal grammar): G = (V, T, S, P) V: tập hữu hạn các biến (variables) T: tập hữu hạn các ký hiệu kết thúc (terminal symbols) SV: biến khởi đầu (start variable) P: tập hữu hạn các luật sinh (productions) Văn phạm 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. 18 Văn Phạm  Các luật sinh: x  y x(VT)+ y(VT)*  Chuỗi w = uxv dẫn xuất ra z = uyv w  z (dẫn xuất trực tiếp) w1  * wn (w1  w2  ...  wn | w1 = wn) w1  + wn (ít nhất một luật sinh được áp dụng) 19 Văn Phạm  Ngôn ngữ được sinh bởi: G = (V, T, S, P) là: L(G) = {wT* | S * w}  Dẫn xuất câu (derivation): S  w1  w2  ...  wn  wL(G)  Dạng câu (sentential forms): S, w1, w2, ..., wn (chứa các biến) 20 Văn Phạm  Ví dụ 3: G = ({S}, {a, b}, S, P) P: S  aSb S   S  aSb  aaSbb  aabb aabb: câu aaSbb: dạng câu L(G) = {anbn | n  0} 21 Văn Phạm  Ví dụ 4: G1 = ({A, S}, {a, b}, S, P1) P1: S  aAb |  A  aAb |  L(G1) = {a nbn | n  0} G và G1 là tương đương 22 Văn Phạm  Ví dụ 5: G2 = ({S}, {a, b}, S, P2) P2: S  SS S   S  aSb S  bSa L(G2) = {w | na(w) = nb(w)} 23 Automat Một mô hình trừu tượng của máy tính số: Control unit Input file Output Storage 24 Automat Thiết bị đầu vào (input file): là nơi mà các chuỗi nhập (input string) được ghi lên, và được ơtơmát đọc nhưng khơng thay đổi được nội dung của nĩ. Nĩ được chia thành các ơ (cells, squares), mỗi ơ giữ được một kí hiệu. Cơ cấu nhập (input mechanism): là bộ phận cĩ thể đọc input file từ trái sang phải, một kí tự tại một thời điểm. Nĩ cũng cĩ thể dị tìm được điểm kết thúc của chuỗi nhập (eof, #). Bộ nhớ tạm (temporary storage): là thiết bị bao gồm một số khơng giới hạn các ơ nhớ (cell), mỗi ơ cĩ thể giữ một kí hiệu từ một bảng chữ cái (khơng nhất thiết giống với bảng chữ cái ngõ nhập). Ơtơmát cĩ thể đọc và thay đổi được nội dung của các ơ nhớ lưu trữ (storage cell). Dựa vào hoạt động của ơtơmát, cĩ đơn định hay khơng: cĩ hai loại ơtơmát. Ơtơmát đơn định (deterministic automata): là ơtơmát trong đĩ mỗi di chuyển (move) được xác định duy nhất bởi cấu hình hiện tại. Sự duy nhất này thể hiện tính đơn định. Ơtơmát khơng đơn định (non-deterministic automata): là ơtơmát mà tại mỗi thời điểm nĩ cĩ một vài khả năng lựa chọn để di chuyển. Việc cĩ một vài khả năng lựa chọn thể hiện tính khơng đơn định. Dựa vào kết quả xuất ra của ơtơmát: cĩ hai loại ơtơmát. Accepter: là ơtơmát mà đáp ứng ở ngõ ra của nĩ được giới hạn trong hai trạng thái đơn giản “yes” hay “no”. "Yes" tương ứng với việc chấp nhận chuỗi nhập, "no" tương ứng với việc từ chối, khơng chấp nhận, chuỗi nhập. Transducer: là ơtơmát tổng quát hơn, cĩ khả năng sinh ra các chuỗi kí tự ở ngõ xuất. Máy tính số là một transducer điển hình. VD  Dùng văn phạm mơ tả danh hiệu của Pascal.  ,  | |  ,  a .. z | A .. Z  0 .. 9 VD  Dùng accepter mơ tả danh hiệu của Pascal Letter Letter or digit 1 2 Digit 3 Letter or digit VD Một văn phạm đơn giản của ngơn ngữ Pascal [prog] ::= [prog header] [var part] [stat part] [prog header] ::= program [id] ( input , output ) ; [var part] ::= var [var dec list] [stat part] ::= begin [stat list] end . [var dec list] ::= [var dec] | [var dec list] [var dec] [var dec] ::= [id list] : [type] ; [stat list] ::= [stat] | [stat list] ; [stat] [stat] ::= [assign stat] [assign stat] ::= [id] := [expr]