Lý thuyết ngôn ngữ

Lý Thuyết Ngôn Ngữ
Giới thiệu
Môn học này nghiên cứu về hai lý thuyết cơ sở trong lĩnh vực khoa học máy tính – đó là ngôn ngữ hình thức và ôtômát.
Lý thuyết ngôn ngữ hình thức là lý thuyết nền tảng cho việc thấu hiểu khái niệm về ngôn ngữ nói chung
Lý thuyết ôtômát là lý thuyết cơ bản cho việc nghiên cứu các mô hình tự động
Môn học này làm tiền đề cho việc học môn chương trình dịch.
Khối lượng và cấu trúc môn học
Số đơn vị học trình 3
Tổng số tiết 45. Lý thuyết: 36 tiết. Bài tập: 7 tiết. Kiểm tra: 2 tiết
Nội dung
Chương 0: Bổ túc toán
Chương 1: Ngôn ngữ hình thức và văn phạm
Chương 2: Automat hữu hạn và biểu thức chính qui
Chương 3: Lớp các ngôn ngữ phi ngữ cảnh
Chương 4: Automat đẩy xuống
Yêu cầu kiến thức
Nhập môn tin học, Toán rời rạc.
Chương 1: Ngôn ngữ hình thức và văn phạm
I/ Tổng quan về ngôn ngữ
Bảng chữ cái(alphabet) là một tập hữu hạn hoặc vô hạn các ký hiệu.
Vd: - Bộ chữ cái Latinh {A, B, C, ... , Z, a, b, c, ... , z}
- Bộ chữ số thập phân {0, 1, 2, ... , 9}
Từ (word) là một dãy các ký hiệu thuộc bảng chữ cái (Từ còn được gọi là chuỗi)
Vd: - , 0, 1011, 00010, ... là các từ trên bộ chữ cái  = {0, 1}
Độ dài của một từ w, ký hiệu |w| là số các ký hiệu tạo thành từ w.
Vd: Từ abca có độ dài là 4 , ký hiệu : |abca | = 4
Ngôn ngữ (Languages)
Định nghĩa: một ngôn ngữ (hình thức) L là một tập hợp các chuỗi của một bộ chữ cái  nào đó.
Tập hợp chứa chuỗi rỗng (ký hiệu {}) và tập hợp rỗng  cũng được coi là ngôn ngữ. Chú ý rằng hai ngôn ngữ đó là khác nhau: ngôn ngữ  không có phần tử nào trong khi ngôn ngữ {} có một phần tử là chuỗi rỗng .
Tập hợp tất cả các chuỗi con kể cả chuỗi rỗng trên bộ chữ cái cố định , ký hiệu là * cũng là một ngôn ngữ. Mọi ngôn ngữ trên bộ chữ cái  đều là tập con của *. Ngoài ra tập hợp tât cả các chuỗi sinh ra từ bộ chữ cái , ngoại trừ chuỗi rỗng , được ký hiệu là +. Dễ thấy:
+ = * - {} hay * = + + {}
Vd :  = {0, 1} thì * = {, 0, 1, 00, 01, 10, 11, 000, ...}
+ = {0, 1, 00, 01, 10, 11, 000, ...}
Các phép toán trên ngôn ngữ

Từ các ngôn ngữ có trước, ta có thể thu được các ngôn ngữ mới nhờ áp dụng các phép toán trên ngôn ngữ.
L1 = {ab, bc}; L2 = {12, 34, ab}
Phép hợp L1  L2 = {ab, bc, 12, 34}
Phép giao L1  L2 = {ab}
Phép đối xứng: L1 = {ba,cb}

Các phép toán trên ngôn ngữ (tiếp)

Một ngôn ngữ L trên một bộ chữ cái  là một tập con của tập *.
Làm thế nào để biểu diễn ngôn ngữ?
Ngôn ngữ hữu hạn biểu diễn chúng bằng cách liệt kê tất cả các chuỗi thuộc vào chúng.
Vd: L1 = {}, L2 = { a, ba, aaba, bbbbb }

Ngôn ngữ là vô hạn không thể liệt kê tất cả các chuỗi thuộc ngôn ngữ được
Trong trường hợp đơn giản thì ngôn ngữ được biểu diễn thông qua một phát biểu hay một tân từ.
Vd: L3 = { ai  i là một số nguyên tố }
L4 = { ai bj  i  j  0 }
II/ Vấn đề biểu diễn ngôn ngữ

Văn phạm là một cơ chế cho phép sản sinh ra mọi chuỗi của ngôn ngữ.
ôtômát cơ chế cho phép đoán nhận một chuỗi bất kỳ có thuộc ngôn ngữ hay không.
Cách biểu diễn ngôn ngữ tổng quát
III. Văn phạm và sự phân lớp văn phạm
3.4. Văn phạm tương đương
Hai văn phạm sinh ra cùng một ngôn ngữ thì gọi là tương đương.
G1 tương đương G2  L (G1) = L (G2)

3.5. Sự phân loại văn phạm theo Chomsky
(Dựa trên các tập luật sinh để phân loại văn phạm)
1) Văn phạm loại 0: Một văn phạm không cần thỏa mãn ràng buộc nào trên tập các luật sinh được gọi là văn phạm loại 0 hay còn được gọi là văn phạm không hạn chế (Unrestricted Grammar)
2) Văn phạm loại 1
Mọi luật sinh dạng    và thỏa mãn  thì G là văn phạm loại 1 hoặc còn được gọi là văn phạm cảm ngữ cảnh CSG (Context-Sensitive Grammar).Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ cảm ngữ cảnh (CSL).
3) Văn phạm loại 2
Mọi luật sinh có dạng A   với A là một biến đơn (A  ∆) và   (∑  ∆)* thì G là văn phạm loại 2 hoặc còn được gọi là văn phạm phi ngữ cảnh CFG (Context-Free Grammar).
Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ phi ngữ cảnh (CFL)
4) Văn phạm loại 3
Mọi luật sinh dạng A  wB hoặc A  w với A, B là các biến đơn thuộc ∆. w là chuỗi ký hiệu kết thúc thuộc ∑ (có thể rỗng);
G là văn phạm loại 3 hay còn được gọi là văn phạm chính quy RG (Regular Grammar).
Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ chính quy (RL).

Chứng minh khẳng định sau:
Ký hiệu : L0, L1, L2, L3 là các lớp ngôn ngữ sinh ra bởi các văn phạm loại 0, 1, 2, 3 tương ứng. Ta có : L3  L2  L1  L0 và các bao hàm thức này là nghiêm ngặt.

3.6. Một số ví dụ về văn phạm
vd1. Xét văn phạm G :
V = {S, B, C}, T = {a, b, c} và tập P = {S  aSBC, S  aBC
CB  BC, aB ab, bB  bb, bC  bc, cC  cc }
Đây là văn phạm loại 1.
vd2. Xét văn phạm G :
V = {S}, T = {a, b} và tập P = {S  aSb, S  ab }
Đây là văn phạm loại 2.
vd3.  Xét văn phạm G :
V = {S, A}, T = {a, b} và tập P = { S  aS, S  aA, A  bA
A  b }
Đây là văn phạm loại 3 (chính qui)
Lưu ý: văn phạm loại 3 thì vế phải chứa không quá 1 ký hiệu chưa kết thúc
Bài tập
Dạng 1: Cho ngôn ngữ, xây dựng văn phạm phi ngữ cảnh.
Có hai bước:
b1: Phân tích cấu trúc của các từ thuộc vào ngôn ngữ
b2: Xây dựng văn phạm dựa trên các phân tích

Vd1. Cho bảng chữ cái  = {a, b, c, d, f}. Hãy xây dựng văn phạm phi ngữ cảnh sinh các ngôn ngữ sau:
a. L = {x  ∑ * | x bắt đầu bằng từ con abbb, kết thúc bởi từ con ccd, chứa từ con abbcd và x có độ dài chẳn}
IV/ CƠ CHẾ ÔTÔMÁT
4.1. Định nghĩa ôtômát
Ôtômát là cơ chế có khả năng đoán nhận ngôn ngữ. Với một chuỗi bất kỳ, sau một số bước làm việc, ôtômát sẽ cho câu trả lời chuỗi đó có thuộc ngôn ngữ hay không.
Để có được quá trình tự động như vậy, con người thường phải lập trình sẵn cho nó một “lộ trình” thực hiện, và các máy chỉ cần họat động theo đúng lộ trình này. Một trong số những máy tự động này điển hình mạnh nhất có thể nói chính là máy tính số ngày nay. Tuy hoạt động theo kiểu “máy”, song thực chất mỗi bước làm việc của ôtômát là một sự thay thế ký hiệu, nghĩa là một bước dẫn xuất như đã nói ở trên.
 
Chương II/ ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY
I. ÔTÔMÁT HỮU HẠN (FA : Finite Automata)
Ôtômát hữu hạn FA là một mô hình tính toán của hệ thống với sự mô tả bởi các input và output. Tại mỗi thời điểm, hệ thống có thể được xác định ở một trong số hữu hạn các cấu hình nội bộ gọi là các trạng thái (states). Mỗi trạng thái của hệ thống thể hiện sự tóm tắt các thông tin liên quan đến những input đã chuyển qua và xác định các phép chuyển kế tiếp trên dãy input tiếp theo.
Ôtômát hữu hạn (FA) được chia thành 2 loại: đơn định (DFA) và không đơn định (NFA).
DFA có khả năng nhận dạng ngôn ngữ dễ dàng hơn NFA, nhưng thay vào đó thông thường kích thước của nó lại lớn hơn so với ôtômát hữu hạn không đơn định tương đương.

Ôtômát hữu hạn đơn định - DFA (Deterministic Finite Automata)

Định nghĩa
 Một cách hình thức ta định nghĩa ôtômát hữu hạn đơn định là bộ gồm năm thành phần (Q, , , q0, F), trong đó :
. Q là tập hợp hữu hạn các trạng thái.
.  là bộ chữ cái nhập hữu hạn.
.  là hàm chuyển ánh xạ từ Q    Q, tức là (q, a) là một trạng thái được cho bởi phép chuyển từ trạng thái q trên ký hiệu nhập a.
. q0  Q là trạng thái bắt đầu
. F  Q là tập các trạng thái kết thúc
Sơ đồ chuyển
Một đồ thị có hướng, gọi là sơ đồ chuyển (transition diagram) tương ứng với một DFA như sau: các đỉnh của đồ thị là các trạng thái của DFA; nếu có một đường chuyển từ trạng thái q đến trạng thái p trên input a thì có một cung nhãn a từ đỉnh q đến đỉnh p trong sơ đồ chuyển.
vd:.
 






Trạng thái khởi đầu q0 nhãn "Start".Trạng thái kết thúc q0, được chỉ ra bằng hai vòng tròn.
Ta vẽ DFA như là bộ điều khiển hữu hạn, với mỗi trạng thái thuộc Q, DFA đọc một chuỗi các ký hiệu a từ  viết trên băng (như hình vẽ).





Trong một lần chuyển, DFA đang ở trạng thái q đọc ký hiệu nhập a trên băng, chuyển sang trạng thái được xác định bởi hàm chuyển (q, a), rồi dịch đầu đọc sang phải một ký tự. Nếu (q, a) chuyển đến một trong những trạng thái kết thúc thì DFA chấp nhận chuỗi được viết trên băng input phía trước đầu đọc, nhưng không bao gồm ký tự tại vị trí đầu đọc vừa dịch chuyển đến. Trong trường hợp đầu đọc đã dịch đến cuối chuỗi trên băng, thì DFA mới chấp nhận toàn bộ chuỗi trên băng.

Ngôn ngữ được chấp nhận bởi DFA
 Một chuỗi x được chấp nhập bởi ôtômát hữu hạn M (Q, , , q0, F) nếu (q0, x) = p với p  F. Ngôn ngữ được chấp nhận bởi M, ký hiệu L(M) là tập hợp:
  L(M) = { x   (q0, x)  F }
VD. Một DFA được xác định bởi M (Q, , , q0, F) với Q = {q0, q1, q2, q3},  = {0, 1}, F = {q0} và hàm chuyển  như sau:

Giả sử chuỗi w = 110101 được nhập vào M.
Ta có tập hợp các trạng thái chuyển sau:
(q0, 1) = q1, (q1, 1) = q0, (q0, 0) = q2, (q2, 1) = q3
(q3, 0) = q1, (q1, 1) = q0  F
(Hay (q0, 110101) = (q1, 10101) = (q0, 0101) = (q2, 101) = (q3, 01) = (q1, 1) = q0  F)
Vậy 110101 thuộc L(M). Ta có thể chứng minh rằng L(M) là tập mọi chuỗi có số chẵn số 0 và số chẵn số 1.
Nhận xét :
Một cách tổng quát, ta thấy tập Q của DFA thể hiện các trạng thái lưu trữ của ôtômát trong quá trình đoán nhận ngôn ngữ, và như vậy khả năng lưu trữ của ôtômát là hữu hạn. Mặt khác, hàm chuyển  là hàm toàn phần và đơn trị, cho nên các bước chuyển của ôtômát luôn luôn được xác định một cách duy nhất. Chính vì hai đặc điểm này mà DFA mô tả như trên được gọi là ôtômát hữu hạn đơn định.
Ôtômát hữu hạn không đơn định - NFA (Nondeterministic Finite Automata)
Xét một dạng sửa đổi mô hình DFA để chấp nhận không, một hoặc nhiều hơn một phép chuyển từ một trạng thái trên cùng một ký hiệu nhập. Mô hình mới này gọi là ôtômát hữu hạn không đơn định (NFA). Chú ý rằng có thể xem ôtômát hữu hạn đơn định - DFA (hay gọi tắt là FA) là một trường hợp đặc biệt của NFA, trong đó mỗi trạng thái chỉ có duy nhất một phép chuyển trên mỗi ký hiệu nhập.
Định nghĩa
 Một cách hình thức ta định nghĩa ôtômát hữu hạn không đơn định NFA là một bộ 5 thành phần (Q, , , q0, F) trong đó Q, , q0 và F có ý nghĩa như trong DFA, nhưng  là hàm chuyển ánh xạ từ Q    2Q.(Tập hợp tất cả các tập hợp con của tập A được gọi là tập lũy thừa (power set) của A và xác định bởi 2Q.Giả sử A = { 1, 2, 3 }Thì 2A = { , {1 }, {2 }, {3}, {1, 2}, {2, 3}, {3, 1}, {1, 2, 3} }
Sơ đồ chuyển
Ngôn ngữ được chấp nhận bởi NFA
Ngôn ngữ L(M), với M là ôtômát hữu hạn không đơn định NFA (Q, , , q0, F) là tập hợp :
L(M) = {w  (q0, w) có chứa một trạng thái trong F }
VD. Xét NFA M ({q0, q1, q2, q3, q4}, {0, 1}, , q0, {q2, q4}) với hàm chuyển như sau :
Xét chuỗi nhập w = 01001.
Ta có : (q0, 0) = {q0, q3}
(q0, 01) = ((q0, 0),1) = ({q0, q3},1) = (q0, 1)   (q3, 1) = {q0, q1}
 
Tương tự , ta có thể tính :
(q0, 010) = {q0, q3}
(q0, 0100) = {q0, q3, q4}
và (q0, 01001) = {q0, q1, q4}
Do q4  F nên w  L (M).

Câu hỏi: 1) Nêu sự khác biệt cơ bản giữa DFA và NFA
2) Để đoán nhận chuỗi thì dùng ôtomát nào thì dễ dàng hơn
Sự tương đương giữa DFA và NFA
ĐỊNH LÝ 3.1 : Nếu L là tập được chấp nhận bởi một NFA thì tồn tại một DFA chấp nhận L.
VD. Cho NFA M ({q0, q1}, {0, 1}, , q0, {q1}) với hàm chuyển  như sau : (q0, 0) = {q0, q1}, (q0,1) = {q1}, (q1, 0) = ,(q1, 1) = {q0, q1}
 Ta xây dựng DFA tương đương M’ (Q’, {0, 1}, ’, [q0], F’) chấp nhận L(M) như sau :
Q’ : chứa tất cả các tập con của {q0, q1}, vậy Q’ = {[q0], [q1], [q0, q1], }
Hàm chuyển ’ :Vì (q0, 0) = {q0, q1} nên ’([q0], 0) = [q0, q1]
’([q0], 1) = [q1], ’([q1], 0) = , ’([q1], 1) = [q0, q1],
’(, 0) = ’(, 1) =  ,
Cuối cùng : ’([q0, q1],0) = [q0, q1]. ( vì ({q0, q1},0) = (q0, 0)  (q1, 0) = {q0, q1}   = {q0, q1})
’([q0, q1], 1) = [q0, q1] ( vì ({q0, q1},1) = (q0, 1)  (q1, 1) = {q1}  {q0, q1} = {q0, q1})
Tập trạng thái kết thúc (chứa các phần tử của Q’ mà có mặt q1) F’ = {[q1], [q0, q1]}
Nhận xét :
- Otomat M đơn định khi và chỉ khi trong bảng chuyển của nó không có vị trí nào chứa quá 1 trạng thái thuộc S.
- Otomat M đầy đủ khi và chỉ khi mọi vị trí của bảng chuyển đều chứa ít nhất một trạng thái thuộc Q.
Câu hỏi: Rõ ràng là dạng định là đơn giản hơn và cũng thõa mãn khả năng đoán nhận một ngôn ngữ nhưng tại sao ta lại phải để ý đến dạng không đơn định.
- Trong một số các bài toán mang tính chọn lựa, có nhiều hướng giải quyết (nhiều cách đi) như trong các chương trình trò chơi (games) thì thông thường hướng giải quyết tốt nhất (cách đi tốt nhất) là không biết trước được, nhưng có thể tìm thấy được bằng cách sử dụng chiến lược tìm kiếm quay lui (back-tracking). Nếu chưa phải là hướng tốt nhất, ta phải quay về điểm quyết định cuối cùng trước đó và thử khảo sát theo một hướng khác. Một giải thuật mô phỏng quá trình tìm kiếm quay lui này là một giải thuật không đơn định.
- Trong một số bài toán thì việc xây dựng một NFA có vẻ tự nhiên và đơn giản hơn việc tìm một DFA cho chúng.
- Thuật toán không đơn định dùng để mô phỏng và có vẻ gần gũi với ngôn ngữ tự nhiên hơn.
Bài tập

Bt1: Xây dựng DFA sinh ra ngôn ngữ L được mô tả như sau
L = {x   * | x có độ dài chẵn}. Bảng chữ cái  = {0,1}
Gợi ý: DFA = (Q, , , q0, F). Cần xác định từng thành phần của atomat.
-Tìm Q = {q0, q1} .  = {0,1}
Phân tích để xác định  và F.
Ta có (q0,0) = q1; (q0,1) = q1; (q1,0) = q0; (q1,1) = q0;
F = {q0}
Sơ đồ chuyển
L = {x   * | x bắt đầu bằng một đoạn gồm toàn ký hiệu 1, đoạn này có độ dài lẻ, kết thúc bằng một đoạn gồm toàn ký hiệu 0, đoạn này có độ dài chẵn, còn độ dài từ x là chẵn}. Bảng chữ cái  = {0,1,2}..
Gợi ý:
Phân tích thô: x thuộc L suy ra x có dạng: x = 12t+1y02s+2 (s,t = 0,1,2,...)
y  * và y không bắt đầu bằng ký hiệu 1, không kết thúc bằng ký hiệu 0, |y| là lẻ.
Phân tích mịn: -Trường hợp |y| = 1 thì y = 2
nếu |y|>=3 thì có thể biểu diễn dưới dạng y =azb với z   * ;
|z| = lẻ. a  {0,2}; b  {1,2}.
khi đó x có dạng x = 12t+1azb02s+2 (s,t = 0,1,2,...); z   * ;
|z| = lẻ. a  {0,2}; b  {1,2}. Hoặc x = 12t+1202s+2
Bt2: Xây dựng DFA sinh ra ngôn ngữ L được mô tả như sau
Sơ đồ chuyển
Kết quả
Tập trạng thái Q = {q0, q1, q2, q3, q4, q5, q6}
Bảng chữ cái  = {0,1,2}
Ký hiệu khởi đầu q0
Tập trạng thái kết thúc F = {q6}
Hàm chuyển  :
Bt3: Chuyển đỏi NFA sang DFA
 II. BIỂU THỨC CHÍNH QUY (RE : Regular Expressions)
Các phép toán trên ngôn ngữ
1) Phép hợp (union) : A  B = {x  x A hoặc x B}
2) Phép giao (intersection) : A  B = {x  x A và x B}
3) Phép trừ (difference) : A B = {x  x A nhưng x B}
4) Tích Đecac : A  B = {(a,b)  a A và bB}
5) Tập hợp tất cả các tập hợp con của tập A được gọi là tập lũy thừa (power set) của A và xác định bởi 2A.
Vd : Cho A = {1, 2} và B = {2, 3}
Ta có : A  B = {1, 2, 3}
A  B = {2}
A B = {1}
A  B = {(1, 2 ), (1, 3), (2, 2), (2, 3)}
2A = {, {1}, {2}, {1, 2}}
8)Phép bao đóng (closure) :
 Bao đóng (Kleene) của ngôn ngữ L, ký hiệu L* được định nghĩa là hợp của mọi tập tích trên L :
L* = L0  L1  L2  .......
Trong đó L0 = {}
Li = LLi-1 với i >=1
Bao đóng dương (positive) của ngôn ngữ L, ký hiệu L+ được định nghĩa là hợp của mọi tích dương trên L :
 Chú ý rằng : L+ = LL* = L*L
L* = L+  {}
 VD: Cho ngôn ngữ L = { a, ba } thì
L2 = LL = { aa, aba, baa, baba}
L3 = LL2 = { aaa, aaba, abaa, ababa, baaa, baaba, babaa, bababa}
L* = { , a, ba, aa, aba, baa, baba, aaa, aaba, abaa, ababa, baaa, baaba, babaa, bababa … }
Lớp ngôn ngữ được chấp nhận bởi một ôtômát hữu hạn được gọi là lớp ngôn ngữ chính qui.
Lớp ngôn ngữ được chấp nhận bởi một ôtômát hữu hạn cũng có thể được mô tả thông qua một dạng biểu thức ngắn gọn và súc tích gọi là biểu thức chính quy.
2.1. Định nghĩa
 Cho  là một bộ chữ cái. Biểu thức chính quy trên  và các tập hợp mà chúng mô tả được định nghĩa một cách đệ quy như sau:
1)  là biểu thức chính quy ký hiệu cho tập rỗng
2)  là biểu thức chính quy ký hiệu cho tập {}
3) a  , a là biểu thức chính quy ký hiệu cho tập {a}
4) Nếu r và s là các biểu thức chính quy ký hiệu cho các tập hợp R và S thì (r + s), (rs) và ( r*) là các biểu thức chính quy ký hiệu cho các tập hợp R  S, RS, R* tương ứng.
Trong khi viết biểu thức chính quy ta có thể bỏ bớt các dấu ngoặc đơn với lưu ý rằng thứ tự ưu tiên của các phép toán xếp theo thứ tự giảm dần là: phép bao đóng, phép nối kết, phép hợp.
VD: Biểu thức ((0(1*)) + 1) có thể viết là 01*+ 1.
Một số biểu thức chính quy ký hiệu cho các ngôn ngữ :
00 là biểu thức chính quy biểu diễn tập {00}.
(0+1)* ta có (0+1) = {0,1} và L* = {0,1}*. L1 = L = {0,1};
L2 = LL = {00,01,10,11};
L3 = L L2 = {000,001,010,011,100,101,110,111} vv
L* = L0  L1  L2  ....... = ký hiệu cho tập hợp tất cả các chuỗi số 0 và số 1, kể cả chuỗi rỗng = {, 0, 1, 00, 01, 10, 11, 010, 011, 0010 ... }
(0+1)*00(0+1)* ký hiệu cho tập hợp tất cả các chuỗi 0,1 có ít nhất hai số 0 liên tiếp.
= {00, 000, 100, 0000, 0001, 1000, 1001, 011001, ... }

(1+10)* ký hiệu cho tất cả các chuỗi 0, 1 bắt đầu bằng số 1 và không có hai số 0 liên tiếp = {, 1, 10, 11, 1010, 111, 101010, ... }
(0+)(1+10)* ký hiệu cho tất cả các chuỗi không có hai số 0 liên tiếp = {, 0, 01, 010, 1, 10, 01010, 0111, ... }
(0+1)*011 ký hiệu cho tất cả các chuỗi 0, 1 tận cùng bởi 011.
= {011, 0011, 1011, 00011, 11011, ... }
0*1*2* ký hiệu cho tất cả các chuỗi có một số bất kỳ các số 0, theo sau là một số bất kỳ số 1 và sau nữa là một số bất kỳ số 2.
= {, 0, 1, 2, 01, 02, 12, 012, 0012, 0112, ... }
00*11*22* ký hiệu cho tất cả các chuỗi trong tập 0*1*2* với ít nhất một trong mỗi ký hiệu. 00*11*22* có thể được viết gọn thành 0+1+2+
2.2. Một số tính chất đại số của biểu thức chính quy
1. r + s = s + r 2. r + r = r
3. r + (s+t) = (r+s) + t 4. r (st) = (rs) t
5. r (s+t) = rs + rt 6. (r+s) t = rt + st
7. r =  r = r 8. r = r = 
9. r +  = r 10.* = 
11. ( + r)* = r* 12.r + r* = r*
13. ( r* )* = r* 14. ( r* s* )* = (r+s)*
 
Trong đó, ta có r = s có nghĩa là L(r) = L(s).
Bài tập
Cho bảng chữ cái {a,b,c}.
Viết biểu thức chính qui biểu diễn ngôn ngữ mà các từ có chứa ký tự đầu là ab.
Giải: R = ab(a+b+c)*
2. Viết biểu thức chính qui biểu diễn ngôn ngữ mà các từ có chứa ký tự thứ 2 từ phía bên phải là a hoặc b, không được là c.
(a+b+c)*(a+b)(a+b+c)
3. Viết biểu thức chính qui biểu diễn ngôn ngữ
L = {anbm |n >=4; 0<=m<=3}
Giải: R = aaaaa*(+b+bb+bbb)
Chương 3: Lớp các ngôn ngữ phi ngữ cảnh
I. Văn phạm phi ngữ cảnh (CFG : context free grammar)
 
    1.1. Định nghĩa
    1.2. Dẫn xuất và ngôn ngữ
    1.3. Cây dẫn xuất
    1.4. Quan hệ giữa dẫn xuất và cây dẫn xuất
    1.5. Dẫn xuất trái nhất, dẫn xuất phải nhất
    1.6. Văn phạm mơ hồ
 
Xuất xứ của văn phạm phi ngữ cảnh là sự mô tả thông qua các ngôn ngữ tự nhiên. Ta có thể viết các quy tắc cú pháp để diễn tả câu “An là sinh viên giỏi“ như sau :
< câu đơn >  < chủ ngữ > < vị ngữ >
< chủ ngữ >  < danh từ >
< vị ngữ >  < động từ > < bổ ngữ >
< bổ ngữ >  < danh từ > < tính từ >
< danh từ >  An
< danh từ >  sinh viên
< động từ >  là
< tính từ >  giỏi
Việc nghiên cứu các văn phạm phi ngữ cảnh đã tạo nên một cơ sở lý luận vững chắc cho việc biểu diễn ngôn ngữ lập trình, việc tìm kiếm các giải thuật phân tích cú pháp vận dụng trong chương trình dịch và cho nhiều ứng dụng khác về xử lý chuỗi. Chẳng hạn, nó rất hữu ích trong việc mô tả các biểu thức số học với nhiều dấu ngoặc lồng nhau hoặc cấu trúc khối trong ngôn ngữ lập trình mà biểu thức chính quy không thể đặc tả.
1.1. Định nghĩa
Văn phạm phi ngữ cảnh (CFG) là một hệ thống gồm bốn thành phần, ký hiệu là văn phạm G (V, T, P, S), trong đó :
. V là tập hữu hạn các biến (hay ký tự chưa kết thúc)
. T là tập hữu hạn các ký tự kết thúc, V  T = 
. P là tập hữu hạn các luật sinh mà mỗi luật sinh có dạng A   với A là biến và  là chuỗi các ký hiệu  (V  T)*
. S là một biến đặc biệt gọi là ký hiệu bắt đầu.
Thí dụ :Văn phạm G ({S, A, B}, { a, b }, P, S ), trong đó P gồm các luật sinh sau :
S  AB; A  aA; A  a; B  bB; B  b 
Nếu A  1, A  2 , ... , A  k là các luật sinh của biến A trong văn phạm nào đó, ta sẽ ghi ngắn gọn là A  1 | 2 | ... | k
Văn phạm trong Thí dụ trên trên có thể viết gọn là :
S  AB; A  aA  a; B  bB  b
1.2. Dẫn xuất và ngôn ngữ
Dẫn xuất: Để định nghĩa ngôn ngữ sinh bởi văn phạm CFG G (V, T, P, S), ta dẫn nhập khái niệm dẫn xuất. Trước hết ta giới thiệu hai quan hệ G và *G giữa hai chuỗi trong tập (V  T)*. Nếu A   là một luật sinh trong văn phạm và ,  là hai chuỗi bất kỳ trong tập (V  T)* thì A G , hay ta còn nói luật sinh A   áp dụng vào chuỗi A để thu được chuỗi , nghĩa là A sinh trực tiếp  trong văn phạm G. Hai chuỗi gọi là quan hệ nhau bởi G nếu chuỗi thứ hai thu được từ chuỗi thứ nhất bằng cách áp dụng một luật sinh nào đó.
Ngôn ngữ sinh bởi văn phạm phi ngữ cảnh :
Cho văn phạm CFG G(V, T, P, S) :
L(G) = {ww  T * và S *G w}
Nghĩa là, một chuỗi thuộc L(G) nếu:
1) Chuỗi gồm toàn ký hiệu kết thúc.
2) Chuỗi được dẫn ra từ ký hiệu bắt đầu S.
VD: Xét văn phạm G (V, T, P, S), trong đó :
V = {S}, T = {a, b}, P = {S  aSb, S  ab}.
Bằng cách áp dụng luật sinh thứ nhất n -1 lần và luật sinh thứ hai 1 lần, ta có:
S  aSb  aaSbb  a3Sb3  ... an-1bn-1  anbn
Vậy, L(G) chứa các chuỗi có dạng anbn,
hay L(G) = {anbn  n  1}.
1.3. Cây dẫn xuất
 Để dễ hình dung sự phát sinh ra các chuỗi trong văn phạm phi ngữ cảnh, ta thường diễn tả một chuỗi dẫn xuất qua hình ảnh một cây. Một cách hình thức, ta định nghĩa như sau:
 Định nghĩa : Cho văn phạm G (V, T, P, S). Cây dẫn xuất (hay cây phân tích cú pháp) của G được định nghĩa như sau :
i) Mỗi nút (đỉnh) có một nhãn, là một ký hiệu  (V  T  {})
ii) Nút gốc có nhãn là ký hiệu bắt đầu S.
iii) Nếu nút trung gian có nhãn A thì A  V
iv) Nếu nút n có nhãn A và các đỉnh n1, n2, ..., nk là con của n theo thứ tự từ trái sang phải có nhãn lần lượt là X1, X2, ..., Xk thì A  X1X2 ... Xk là một luật sinh trong tập luật sinh P.
v) Nếu nút n có nhãn là từ rỗng  thì n phải là nút lá và là nút con duy nhất của nút cha của nó.
VD
Xét văn phạm G ({S, A}, {a, b}, P, S), trong đó P gồm:
S  aAS | a
A  SbA | SS | ba
Một cây dẫn xuất từ văn phạm có dạng như sau :
Ta thấy, nút 1 có nhãn S và các con của nó lần lượt là a, A, S (chú ý S  aAS là một luật sinh). Tương tự, nút 3 có nhãn A và các con của nó là S, b, A (từ luật sinh A  SbA). Nút 4, 5 có cùng nhãn S và có nút con nhãn a ( luật sinh S  a). Cuối cùng nút 7 có nhãn A và có các nút con b, a ( luật sinh A  ba).
 
Trên cây dẫn xuất, nếu ta đọc các lá theo thứ tự từ “trái sang phải“ thì ta có một dạng câu trong G. Ta gọi chuỗi này là chuỗi sinh bởi cây dẫn xuất.
 
Một cây con (subtree) của cây dẫn xuất có nút gốc nhãn là A còn được gọi là A-cây con (hoặc A-cây). Cây con cũng giống như cây dẫn xuất, chỉ khác là nhãn của nút gốc không nhất thiết phải là ký hiệu bắt đầu S.
 
1.4. Quan hệ giữa dẫn xuất và cây dẫn xuất
Định lý: Nếu G (V, T, P, S) là một văn phạm phi ngữ cảnh thì S *  nếu và chỉ nếu có cây dẫn xuất trong văn phạm sinh ra .
1.5. Dẫn xuất trái nhất, dẫn xuất phải nhất
Nếu tại mỗi bước dẫn xuất, luật sinh được áp dụng vào biến bên trái nhất thì ta gọi đó là dẫn xuất trái nhất (leftmost) hay dẫn xuất trái. Tương tự, nếu biến bên phải nhất được thay thế ở mỗi bước dẫn xuất, đó là dẫn xuất phải nhất (rightmost) hay dẫn xuất phải. Nếu chuỗi w  L(G) với CFG G thì w sẽ có ít nhất một cây dẫn xuất ra nó và tương ứng với các cây này, w chỉ có duy nhất một dẫn xuất trái nhất và duy nhất một dẫn xuất phải nhất. Dĩ nhiên, w có thể có nhiều dẫn xuất trái (phải) nhất vì nó có thể có nhiều cây dẫn xuất.  
Thí dụ 5.7 : Xét cây dẫn xuất ở Hình 5.1
. Dẫn xuất trái nhất của cây :
S  aAS  aSbAS  aabAS  aabbaS  aabbaa.
. Dẫn xuất phải nhất tương ứng là :
S  aAS  aAa  aSbAa  aSbbaa  aabbaa.
1.6. Văn phạm nhập nhằng
Một văn phạm phi ngữ cảnh G có nhiều hơn một cây dẫn xuất cho cùng một chuỗi w, thì G được gọi là văn phạm nhập nhằng (ambiguity). Dĩ nhiên, cũng có thể nói rằng văn phạm G là nhập nhằng nếu có một chuỗi w được dẫn ra từ ký hiệu bắt đầu S với hai dẫn xuất trái hoặc hai dẫn xuất phải.
Vd: Xét văn phạm G với các luật sinh như sau :
E  E + E  E * E  ( E )  a
Văn phạm này sinh ra các chuỗi biểu thức số học với 2 phép toán + và * . Với chuỗi a + a * a, ta có thể vẽ đến hai cây dẫn xuất khác nhau như sau :
Điều này có nghĩa là biểu thức a + a * a có thể hiểu theo 2 cách khác nhau: thực hiện phép cộng trước hay phép nhân trước ? Để khắc phục sự mơ hồ này, ta có thể :
- Hoặc quy định rằng các phép cộng và nhân luôn luôn được thực hiện theo thứ tự từ trái sang phải (trừ khi gặp ngoặc đơn). Ta viết văn phạm G1 không mơ hồ tương đương như sau :
E  E + T  E * T  T; T  ( E )  a

- Hoặc quy định rằng khi không có dấu ngoặc đơn ngăn cách thì phép nhân luôn luôn được ưu tiên hơn phép cộng. Ta viết văn phạm G2 không mơ hồ tương đương như sau :
E  E + T  T
T  T * F  F
F  ( E )  a
II. GIẢN LƯỢC CÁC VĂN PHẠM PHI NGỮ CẢNH
    2.1. Các ký hiệu vô ích
    2.2. Luật sinh 
    2.3. Luật sinh đơn vị
 Thường thì một văn phạm phi ngữ cảnh có thể còn chứa đựng một vài yếu tố thừa, vô ích. Chẳng hạn như theo các đặc tính trên, có những ký hiệu không thực sự tham gia vào quá trình dẫn xuất ra câu, hoặc sẽ có những luật sinh dạng A  B làm kéo dài chuỗi dẫn xuất một cách không cần thiết. Vì vậy, việc giản lược văn phạm phi ngữ cảnh là nhằm loại bỏ những yếu tố vô ích đó mà không làm giảm bớt khả năng sản sinh của văn phạm.
Nếu L là một CFL, nó có thể tạo ra văn phạm CFG với các đặc tính sau :
    - Mỗi biến và mỗi ký hiệu kết thúc của G đều xuất hiện trong dẫn xuất của một số chuỗi trong L.
   - Không có luật sinh nào dạng A  B, mà trong đó A, B đều là biến.
Hơn nữa, nếu   L thì không cần luật sinh A  . Thực tế, nếu   L, ta có mọi luật sinh trong G đều có một trong hai dạng :
A  BC hoặc A  a ( là chuỗi các biến hoặc )
A  a
Hai dạng đặc biệt này gọi là dạng chuẩn Chomsky và dạng chuẩn Greibach.
2.1. Các ký hiệu vô ích
 Một ký hiệu X gọi là có ích nếu có một dẫn xuất S * X * w với các chuỗi ,  bất kỳ và w  T *. Ngược lại X gọi là vô ích.
Vậy, có 2 đặc điểm cho ký hiệu có ích:
- X phải dẫn ra một chuỗi ký hiệu kết thúc.
- X phải nằm trong dẫn xuất từ S.
Tuy nhiên 2 dấu hiệu trên không đủ để đảm bảo X có ích vì X có thể nằm trong dạng câu chứa một biến nhưng từ đó không có ký hiệu kết thúc được sinh ra.
BỔ ĐỀ 1: (Dùng loại bỏ các biến không dẫn ra chuỗi ký hiệu kết thúc)
VD : Xét văn phạm có các luật sinh sau :
S  AB | a
A  a
Áp dụng bổ đề 1, ta thấy không có ký hiệu kết thúc nào được dẫn ra từ B nên ta loại bỏ B và luật sinh S  AB. Tiếp tục, áp dụng bổ đề 2 cho văn phạm :
S  a
A  a
Ta thấy chỉ có S xuất hiện trong dạng câu. Vậy ({S}, {a}, {S  a}, S) là văn phạm tương đương với văn phạm đã cho và không có ký hiệu vô ích.
2.2. Luật sinh 
 Một luật sinh có dạng A   gọi là luật sinh .
 Ta xét đến việc loại bỏ các luật sinh này. Nếu   L(G) thì không thể loại được tất cả các luật sinh , nhưng nếu   L(G) thì có thể.
Ta có thể xác định tập hợp các biến rỗng (nullable) của G bằng giải thuật lặp như sau : Bắt đầu, nếu A   là một luật sinh thì A là biến rỗng. Kế tiếp, nếu B  , trong đó  gồm toàn các ký hiệu là các biến rỗng đã được tìm thấy trước đó thì B cũng là biến rỗng. Lặp lại cho đến khi không còn biến rỗng nào được tìm thấy nữa.
 Tập luật sinh P’ được xây dựng như sau : Nếu A  X1X2 ... Xn là một luật sinh trong P thì ta thêm tất cả các luật sinh A  12 ... n vào P` với điều kiện :
1) Nếu Xi không là biến rỗng thì i = Xi;
2) Nếu Xi là biến rỗng thì i là Xi hoặc ;
3) Không phải tất cả i đều bằng .
VD
Loại bỏ luật sinh trong văn phạm sau :
S  AB ; A  aA | ; B  bB | 
Trước hết, ta xác định tập các biến rỗng trong văn phạm: A, B là các biến rỗng vì có các luật sinh A   và B . S cũng là biến rỗng vì có luật sinh S  AB với A, B đều là các biến rỗng.
 Tập biến rỗng Nullable = {A, B, S}
Theo quy tắc xây dựng tập luật sinh P’ trong định lý , ta có tập luật sinh mới như sau :
S  AB | A | B; A  aA | a; B  bB | b
Lưu ý rằng văn phạm mới G’ không sản sinh ra , trong khi G lại có sinh ra từ rỗng . Vậy muốn có một văn phạm thực sự tương đương với văn phạm G thì ta phải bổ sung thêm luật sinh S   vào tập luật sinh của G’. Ta có, văn phạm G’ tương đương G.
2.3. Luật sinh đơn vị
Một luật sinh có dạng A  B với A, B đều là biến (Ký hiệu chưa kết thúc) gọi là luật sinh đơn vị.
 ĐỊNH LÝ : Mỗi CFL không chứa  được sinh ra bởi CFG không có ký hiệu vô ích, luật sinh  hoặc luật sinh đơn vị .
Thí dụ : Loại bỏ các luật sinh đơn vị trong văn phạm sau :
E  E + T | T; T  T * F | F ; F  ( E ) | a
Gọi tập A = {B  A  * B}, xét các biến trong văn phạm, ta có :
 E = { E, T, F }  T = { T, F }  F = { F }
Vậy tập luật sinh mới, theo định lý sẽ chứa các luật sinh không là luật sinh đơn vị trong P, bổ sung thêm các luật sinh mới thay cho luật sinh đơn vị như sau :
E  E + T | T * F | ( E ) | a ; T  T * F | ( E ) | a ; F  ( E ) | a
III. CHUẨN HÓA VĂN PHẠM PHI NGỮ CẢNH
    3.1. Dạng chuẩn Chomsky - CNF (Chomsky Normal Form)
ĐỊNH LÝ : (Dạng chuẩn Chomsky, hay CNF )
 Một ngôn ngữ phi ngữ cảnh bất kỳ không chứa  đều được sinh ra bằng một văn phạm nào đó mà các luật sinh có dạng A  BC hoặc A  a, với A, B, C là biến còn a là ký hiệu kết thúc.
Đặt G là CFG sinh ra CFL không chứa . CFG tương đương có dạng chuẩn Chomsky có thể xây dựng từ G theo giải thuật sau :
Bước 1 : Thay thế tất cả các luật sinh có độ dài vế phải bằng 1 (luật sinh đơn vị dạng A  B, với A, B là biến )
Bước 2 : Thay thế các luật sinh có độ dài vế phải >1 và có chứa ký hiệu kết thúc.
Bước 3 : Thay thế các luật sinh có độ dài vế phải > 2 ký hiệu chưa kết thúc.
Thí dụ : Tìm văn phạm có dạng CNF tương đương văn phạm sau :
S  A | ABA
A  aA | a | B
B  bB | b
Bước 1 : Thay thế các luật sinh có độ dài vế phải = 1 (luật sinh đơn vị)
Gọi tập A = {B  A  * B }, xét các biến trong văn phạm, ta có :
 S = { S, A, B }  A = { A, B}  B = { B }
Vậy tập luật sinh mới, theo định lý sẽ chứa các luật sinh không là luật sinh đơn vị trong P, bổ sung thêm các luật sinh mới thay cho luật sinh đơn vị như sau :
S  aA | a | bB | b | ABA
A  aA | a | bB | b
B  bB | b
Bước 2 : Thay thế các luật sinh có độ dài vế phải > 1 và có chứa ký hiệu kết thúc.
Ta thấy, a và b đều xuất hiện ở vế phải một số luật sinh, do đó ta tạo thêm 2 biến mới Ca, Cb và 2 luật sinh mới Ca  a và Cb  b. Văn phạm tương đương có tập luật sinh như sau :
S  CaA | a | CbB | b | ABA
A  CaA | a | CbB | b
B  CbB | b
Ca  a
Cb  b
Bước 3 : Thay thế các luật sinh có độ dài vế phải > 2
Chỉ còn duy nhất một luật sinh cần xét ở bước này : S  ABA và tập luật sinh mới được thay thế có dạng như sau :
S  CaA | a | CbB| b | AD1
A  CaA | a | CbB| b
B  CbB| b
Ca  a
Cb  b
D1  BA
Cuối cùng, ta sẽ thu được văn phạm có dạng chuẩn Chomsky như trên tương đương với văn phạm đã cho.


CHƯƠNG IV. ÔTÔMÁT ĐẨY XUỐNG
Nội dung chính của chương này:
    I. ÔTÔMÁT ĐẨY XUỐNG ( PDA : PUSHDOWN AUTOMATA)
    II. PDA VÀ VĂN PHẠM PHI NGỮ CẢNH 
I. ÔTÔMÁT ĐẨY XUỐNG ( PDA : PUSHDOWN AUTOMATA)
     1.1. Mô tả PDA  
    1.2. Định nghĩa
 Như ta đã biết, lớp các ngôn ngữ chính quy được sinh từ văn phạm chính quy, đồng thời cũng được đoán nhận bởi các ôtômát hữu hạn (đơn định hoặc không đơn định). Trong phần này, chúng ta lại thấy một điều tương tự là lớp ngôn ngữ phi ngữ cảnh, được sinh ra từ văn phạm phi ngữ cảnh, cũng được đoán nhận bởi một loại ôtômát khác - gọi là ôtômát đẩy xuống (PDA).
 Có một điều khác biệt là ở đây, chỉ có dạng ôtômát đẩy xuống không đơn định (NPDA) mới có thể đủ mạnh để đoán nhận lớp ngôn ngữ phi ngữ cảnh, còn dạng đơn định (DPDA) chỉ cho phép đoán nhận một tập con thực sự của lớp ngôn ngữ này. Tuy nhiên, tập con đó cũng bao gồm phần lớn các ngôn ngữ lập trình.
 
1.1. Mô tả PDA
 Ôtômát đẩy xuống thực chất là một ôtômát với sự điều khiển cả hai: băng nhập và Stack (bộ đẩy xuống). Về cơ bản, nó vẫn giữ tất cả các thành phần của một ôtômát hữu hạn, với sự bổ sung thêm một ngăn xếp làm việc (Stack) đóng vai trò như một bộ giữ nhớ, nhờ đó mà khả năng ghi nhớ của ôtômát được tăng thêm. Stack xem như là một chồng đĩa, vì vậy cái đặt vào sau sẽ lấy ra trước (LIFO).
1.2. Định nghĩa
Ôtômát đẩy xuống có một bộ điều khiển hữu hạn và một Stack. Stack chứa một chuỗi các ký hiệu thuộc một bộ chữ cái nào đó. Ký hiệu bên trái nhất của chuỗi xem như ký hiệu tại đỉnh Stack. PDA không đơn định nếu như có một số hữu hạn các lựa chọn phép chuyển trong mỗi lần chuyển.
Phép chuyển sẽ có hai kiểu:
- Kiểu thứ nhất phụ thuộc vào ký hiệu nhập, tức là với một trạng thái, một ký hiệu tại đỉnh Stack và một ký hiệu nhập; PDA sẽ lựa chọn trạng thái kế tiếp và một chuỗi các ký hiệu thay thế trên Stack, đầu đọc dịch đi sang phải một ký hiệu.
Một cách hình thức, ta định nghĩa:
Định nghĩa : Một ôtômát đẩy xuống M là một hệ thống M (Q, , , , q0, Z0, F), trong đó :
1) Q là tập hữu hạn các trạng thái
2)  là bộ chữ cái gọi là bộ chữ cái nhập
3)  là bộ chữ cái gọi là bộ chữ cái Stack
4) : hàm chuyển ánh xạ từ Q  ( {})    tập con hữu hạn của Q  *
5) q0 là trạng thái khởi đầu
5) Z0 là một chữ cái riêng của Stack gọi là ký hiệu bắt đầu trên Stack
6) F  Q là tập các trạng thái kết thúc
(Trong trường hợp PDA được thiết kế chấp nhận ngôn ngữ bằng Stack rỗng thì tập hợp F = )
Hàm chuyển không phụ thuộc ký hiệu nhập :
(q, , Z) = {(p1, 1), (p2, 2), ..., (pm, m)}
trong đó q là trạng thái mà PDA đang giữ, độc lập với ký hiệu nhập, PDA đi vào trạng thái pi thay Z bởi i với 1  i  m. Trong trường hợp này đầu đọc không dịch chuyển.

Thí dụ : Mô tả dưới đây cho PDA chấp nhận ngôn ngữ {wcwR w  (0+1)*} bằng Stack rỗng.
M ({q1, q2}, {0, 1, c}, {R, B, Y}, , q1, R, )
     1) (q1, 0, R) = {(q1, BR)}
2) (q1, 1, R) = {(q1, YR)}
3) (q1, 0, B) = {(q1, BB)}
4) (q1, 1, B) = {(q1, YB)}
5) (q1, 0, Y) = {(q1, BY)}
6) (q1, 1, Y) = {(q1, YY)}
7) (q1, c, R) = {(q2, R)}
8) (q1, c, B) = {(q2, B)}
9) (q1, c, Y) = {(q2, Y)}
10) (q2, 0, B) = {(q2, )}
11) (q2, 1, Y) = {(q2, )}
12) (q2, , R) = {(q2, )}
CHƯƠNG IV/ MÁY TURING
  I. MÔ HÌNH MÁY TURING (TM)
    II. NGÔN NGỮ VÀ "HÀM TÍNH ĐƯỢC"
    III. CÁC KỸ THUẬT XÂY DỰNG MÁY TURING
    IV. CÁC BIẾN DẠNG CỦA MÁY TURING
    VI. MÁY TURING NHƯ LÀ MỘT BỘ LIỆT KÊ   
   VII. SỰ TƯƠNG ĐƯƠNG GIỮA VĂN PHẠM kIỂU 0 VÀ MÁY TURING
Trong chương này, ta sẽ xét thêm một loại máy trừu tượng khác - máy Turing (TM - Turing Machines). Chúng có khả năng đoán nhận được lớp ngôn ngữ lớn hơn lớp ngôn ngữ phi ngữ cảnh. Đây còn là một mô hình của sự tính toán, mô hình của các thủ tục hiệu quả, là nền tảng cho quá trình xử lý của máy tính hiện đại, được giới thiệu bởi Alan Turing vào năm 1936. Nhờ đó, các khái niệm về "sự tính được", "sự giải được" được xác định một cách rõ ràng trên cơ sở sự xuất hiện của một số hàm không tính được, các bài toán không giải được.