Giáo trình Lý thuyết tính toán - Bài 1: Tổng quan - Nguyễn Ngọc Tú

pdf 29 trang huongle 1700
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết tính toán - Bài 1: Tổng quan - Nguyễn Ngọc Tú", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_ly_thuyet_tinh_toan_bai_1_tong_quan_nguyen_ngoc_t.pdf

Nội dung text: Giáo trình Lý thuyết tính toán - Bài 1: Tổng quan - Nguyễn Ngọc Tú

  1. LÝ THUYẾT TÍNH TỐ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
  2. Khái niệm căn bản  Ngơn ngữ (languages)  Văn phạm (grammar)  Ơtơmát (automata)
  3. 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ữ 4 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  (+ = * {})
  5. 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ữ 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) n n L2 = {a b | n 0} = {, ab, aabb, }
  7. 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. Ngôn Ngữ 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}
  9. 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. Ngôn Ngữ 10 Bao đĩng sao (Star-closure): * 0 1 2 L = L  L  L Bao đĩng dương (Positive closure): + 1 2 L = L  L
  11. 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.
  12. 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 L0 = { } L = 1LL 2 3 L nlần
  13. 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 14 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 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.
  15. 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 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)
  17. 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 18 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 19 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 20 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 21 Ví dụ 4: G1 = ({A, S}, {a, b}, S, P1) P1: S aAb |  A aAb |  n n L(G1) = {a b | n 0} G và G1 là tương đương
  22. Văn Phạm 22 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 23 Một mô hình trừu tượng của máy tính số: Input file Control unit Storage Output
  24. Automat 24 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).
  25. 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.
  26. 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.
  27. VD  Dùng văn phạm mơ tả danh hiệu của Pascal.  ,  | | ,  a z | A Z  0 9
  28. VD  Dùng accepter mơ tả danh hiệu của Pascal Letter 1 2 Digit Letter or digit 3 Letter or digit
  29. 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]