Giáo trình Lý thuyết ngôn ngữ hình thức và ôtômát - Nguyễn Thanh Bình

Khoa Công nghệ Thông tin
Trường Đại học Bách khoa
Đại học Đà Nắng
GIÁO TRÌNH
LÝ THUYẾT
NGÔN NGỮ HÌNH THỨC VÀ ÔTÔMÁT
Nguyễn Thanh Bình
Đà Nắng, 2007
Mục lục
Chương 1. Mở đầu.................................................................................................................. 6
Chương 3. Biểu thức chỉnh quy và văn phạm chỉnh quy................................................... 27
Biểu thức chính quy (regular expresssion)	27
Định nghĩa hình thức của biểu thức chính quy	27
Độ uu tiên các phép toán trên biểu thức chính quy	28
Các tính chất đại số của biểu thức chính quy	28
Bài tập	29
Biểu thức chính quy và ngôn ngữ chính quy	29
Bài tập	33
ứng dụng của biểu thức chính quy	33
Phân tích từ vựng (lexical analysis)	33
Văn phạm chính quy	33
Văn phạm tuyến tính phải và văn phạm tuyến tính trái	33
Ngôn ngữ chính quy và văn phạm chính quy	34
Bài tập	36
Các tính chất đóng của ngôn ngữ chính quy	36
Tính đóng của ngôn ngữ chính quy duới các phép toán tập hợp	36
Tính đóng duới các phép toán khác	38
Các thuật toán liên quan đến ngôn ngữ chính quy	39
Sự tương đương của các ôtômát và cực tiểu hóa ôtômát	40
Sự tuơng đuơng của các trạng thái	40
Sự tuơng đuơng của các DFA	41
Cực tiểu hóa DFA	42
Bài tập	 43
Nhận biết các ngôn ngữ không là chính quy	44
Định lý “bơm” cho ngôn ngữ chính quy	44
ứng dụng định “bơm”	45
Bài tập	 46
Chương 4. Vãn phạm và ngôn ngữ phi ngữ cảnh	47
Văn phạm phi ngữ cảnh	47
Định nghĩa văn phạm và ngôn ngữ phi ngữ cảnh	47
Dan xuất trái nhất và dẫn xuất phải nhất	49
Cây dẫn xuất	49
Bài tập	51
ứng dụng của văn phạm phi ngữ cảnh	52
Mô tả ngôn ngữ lập trình	52
Sự nhập nhang trong văn phạm phi ngữ cảnh	52
Bài tập	54
Dạng chuẩn của văn phạm phi ngữ cảnh	54
Loại bỏ kí hiệu vô ích	54
Loại bỏ luật sinh-e	57
Loại bỏ luật sinh đơn vị	59
Giản luợc văn phạm phi ngữ cảnh	61
Dạng chuẩn Chomsky	61
Bài tập	63
Chương 5. Ôtômát đẩy xuống	64
Ôtômát đẩy xuống (PushDown Automata - PDA)	64
Mô tả không hình thức	64
Định nghĩa hình thức	65
Biểu diễn PDA bằng biểu đồ	66
Cấu hình của PDA	67
Ngôn ngữ được đoán nhận bởi PDA	67
Đoán nhận bởi trạng thái cuối	67
Đoán nhận bởi ngăn xếp rỗng	68
Chuyển từ PDA đoán nhận bởi ngăn xếp rỗng về PDA đoán nhận bởi trạng thái cuối 69
Chuyển PDA đoán nhận bởi trạng thái cuối về PDA đoán nhận bởi ngăn xếp rỗng 71
Bài tập	72
Sự tương đương giữa PDA và văn phạm phi ngữ cảnh	72
Chuyển văn phạm phi ngữ cảnh thành PDA	72
Chuyển PDA thành văn phạm phi ngữ cảnh	73
Bài tập	76
Ôtômát đẩy xuống đơn định	76
Bài tập	77
Các tính chất của ngôn ngữ phi ngữ cảnh	77
Các thuật toán liên quan đến ngôn ngữ phi ngữ cảnh	79
Nhận biết các ngôn ngữ không phi ngữ cảnh	79
Kích thuớc cây dẫn xuất	80
Định lý bơm cho ngôn ngữ phi ngữ cảnh	80
ứng dụng định lý bơm cho ngôn ngữ phi ngữ cảnh	82
Bài tập	83
Chương 6. Máy Turing.	84
Máy Turing	84
Định nghĩa máy Turing	84
Biểu diễn máy Turing bàng biểu đồ	86
Cấu hình của máy Turing	87
Ngôn ngữ đuợc đoán nhận bởi máy Turing	88
Bài tập	88
Tính toán bởi máy Turing	88
Bài tập	89
Luận đe Church-Turing	(Church Turing thesis)	89
Các kỹ thuật xây dựng máy Turing	90
Nhớ ở bộ điều khiển	hữu hạn	90
Băng nhiều rãnh	90
Chuơng trình con	 91
Các mô hình khác của máy Turing	91
Máy Turing có nhiều băng	91
Máy Turing không đơn định	92
Tài liệu tham khảo	93
Chương 1. MỞ đầu
Giới thiệu
Vào những năm 1930, Alain Turing đã nghiên cứu các máy trừu tuợng có khả năng thục hiện các tính toán nhu máy tính ngày nay. Các máy trừu tuợng này đuợc gọi là máy Turing. Vào những năm 1940 và 1950, các máy trừu tuợng đơn giản hơn, mà chúng ta gọi là ôtômát hữu hạn, đã đuợc nghiên cứu bởi các nhà khoa học.
Sau đó, vào những năm 1950, nhà ngôn ngữ học Chomsky đã thục hiện các nghiên cứu về văn phạm hình thức. Văn phạm này có mối quan hệ chặt chẽ với ôtômát và ngày nay văn phạm là một phần nền tảng của việc xây dụng một số phần mềm, đặc biệt mà các chuơng trình dịch.
Ôtômát là mô hình hữu ích cho nhiều phần mềm quan trọng. Chẳng hạn duới đây là một số ứng dụng:
Phần mềm thiết kế và kiểm tra các mạch điện tử số.
Bộ phân tích từ vụng của một chuơng trình dịch.
Dịch từ ngôn ngữ bậc cao sang ngôn ngữ bậc thấp.
Dịch từ ngôn ngữ tụ nhiên này sang ngôn ngữ tụ nhiên khác (Anh, Pháp, Việt, ..
Tìm kiếm từ trong văn bản.
Ba khái niệm cơ bản của môn học này là: ngôn ngữ, văn phạm và ôtômát sẽ đuợc trình bày từ các lớp đơn giản đến các lớp phức tạp và mối quan hệ mất thiết giữa chúng.
Khái niệm về ngôn ngữ
Một ngôn ngữ, cho dù là ngôn ngữ tụ nhiên hay ngôn ngữ lập trình, thì đều đuợc xem là một tập hợp các câu. Tuy nhiên, truớc khi có định nghĩa chính xác về ngôn ngữ, chúng ta sẽ tìm hiểu một số các quan niệm hình thức về ngôn ngữ.
Bảng chữ (alphabet)
Bảng chữ hay còn gọi là bộ kí tụ là một bảng hữu hạn các kí hiệu (symbol). Bảng chữ thuờng đuợc kí hiệu là X.
Ví dụ 1.1. Cho các bảng chữ sau:
{a, b, c, .z} : bảng chữ cái Latin
{0, 1, .9} : bảng chữ số thập phân
{0, 1}	: bảng chữ số nhị phân
Xâu (String)
Xâu (từ, chuỗi) là một dãy hữu hạn các kí hiệu từ bảng chữ.
Thông thuờng, ta sử dụng các chữ cái thuờng a, b, c, o biểu diễn các kí hiệu thuộc bảng chữ và các chữ cái w, u, V, o biểu diễn các xâu.
Ví dụ 1.2. Cho bảng chữ X = {a, b, c}các xâu abcabc và aabbab thuộc X.
Xâu rỗng là xâu không chúa kí hiệu nào, thuờng đuợc kí hiệu là £.
Các phép toán trên xâu
Độ dài (length) xâu của một xâu w đuợc kí hiệu là |w|, là số kí hiệu của xâu.
Kết nối (concatenation) hai xâu u và V là xâu nhận đuợc bằng cách nối các kí hiệu của xâu V vào cuối cùng bên phải của xâu u, tức là:
u = aia2 o an và V = bib2 o bm thì kết nối của u và V là xâu uv = aia2 o anbib2 o bm
Đảo (reverse) xâu là xâu nhận đuợc bằng cách viết các kí hiệu theo thứ tự nguợc lại, nghĩa là
w = a1a2 o an thì xâu đảo nhận đuợc là wR = anan-1 o a1
Luu ý, £R = £.
Tiền tố (prefix) và hậu tố (postfix): nếu w = uv thì u đuợc gọi là tiền tố của w và V là hậu tố của w.
Lũy thừa (power) xâu: nếu w là một xâu thì wn là xâu nhận đuợc bằng cách kết nối w với chính nó n lần.
wn = ww...w (n lần)
Luu ý, w0 = £ với mọi w.
Ngôn ngữ
Ngôn ngữ là một tập hợp các xâu trên bảng chữ X. Ngôn ngữ thuờng đuợc kí hiệu là L.
Tập tất cả các xâu trên bảng chữ X, đuợc kí hiệu là X* cũng là một ngôn ngữ.
X+ là tập tất cả các xâu trên bảng chữ X loại trừ xâu rỗng, nghĩa là:
X+ = X* - £
0 là ngôn ngữ rỗng, tức là không chứa bất kỳ kí hiệu nào.
{£} là ngôn ngữ chỉ chứa xâu rỗng. Luu ý, 0 khác với {£}.
Ví dụ 1.3. Cho X = {0, 1}
L = {(010)n | n >0} là một ngôn ngữ trên X.
Còn X* = {£, 0, 1, 00, 01, 10, 11, 000, ...}
Ví dụ 1.4.
L1 = {a, ab, abb, bba, bbb} là ngôn ngữ hữu hạn trên {a, b}.
L2 = {(ab)n | n > 0} là ngôn ngữ vô hạn trên {a, b}.
Các phép toán trên ngôn ngữ
Ngôn ngữ là một tập hợp, do đó tất cả các phép toán trên tập hợp đều có thể áp dụng cho ngôn ngữ. Ngoài ra ngôn ngữ còn có một số phép toán quan trọng khác.
Cho các ngôn ngữ L, L1 và L2 trên bảng chữ X.
Phép hợp
L1 u L2 = {w I w e L1 hoặc w e L2}
Phép giao
L1 n L2 = {w I w e L1 và w e L2}
Phép hiệu
L1 - L2 = {w I w e L1 và w Ế L2}
Phép bù
L = {w I w Ế L} hoặc L = X* - L
Phép ghép nối
L1L2 = = {w I w = uv, u e L1 và v e L2}
Vỉ dụ 1.5. Cho L1 = {0, 1} và L2 = {00, 11}
L1L2 = {000, 011, 100, 111}
Phép nghịch đảo
LR = {w I wR e L}
Phép lũy thừa
Ln = LL...L (n lần)
Hay L0 = {e}, Li = LLi-1
Phép bao đóng (closure)
L* = L0 u L1 u ... u Ln
Phép bao đỏng dương
L} = L1 u L2 u ... u Ln
Lưu ý:	L* = L+ u {e}
L} = LL* = L*L
Vi dụ 1.6. Cho L = {a, b}
L2 = {aa, ab, bb, ba}
L3 = {aaaa, aaab, aabb, aaba, abaa, abab, abbb, abba, bbaa, bbab, bbbb, bbba, baaa, baab, babb, baba}
Khái niệm về văn phạm
Khi nghiên cứu ngôn ngữ cần một cơ chế mô tả ngôn ngữ đó là văn phạm (grammar). Một cách không hình thức, văn phạm là các quy tắc sinh câu đúng.
Đối với ngôn ngữ tự nhiên, văn phạm là hệ thống ngữ pháp. Đối với ngôn ngữ lập trình, văn phạm là các quy tắc cú pháp viết chương trình.
Ví dụ 1.7. Định nghĩa một câu tiếng Việt đơn giản bởi văn phạm sau:
 I 
 I 
 I 
Văn phạm trên sinh ra các câu đúng sau:
Con hổ ăn con bò đen.
Học sinh nói chuyện nhiều.
Định nghĩa 1.1. Văn phạm G được định nghĩa như là bộ bốn:
G = (N, X, R, S)
trong đó:
N là tập hợp hữu hạn các kí hiệu không kết thúc (non terminal symbol) hay còn được gọi là các biến;
X là bảng chữ, tập các kí hiệu kết thúc (terminal symbol), N n X = 0;
S e N là kí hiệu đầu hay biến khởi đầu;
R là tập các quy tắc (rule) hoặc các sản xuất/luật sinh (production), các luật sinh có dạng:
a p
trong đó a e (N u X)' có chứa ít nhất một biến, Pe (N u X)*.
Một sổ quy ước
Các biến/kí hiệu không kết thúc thuộc N được biểu diễn bởi các kí tự: A, B, C, o
Các kí hiệu kết thúc thuộc X được biểu diễn bởi các kí tự: a, b, c, o
Các xâu chỉ gồm các kí hiệu kết thúc được biểu diễn bởi các kí tự: w, u, v, o
Các xâu gồm các kí hiệu kết thúc và các kí hiệu không kết thúc được biểu diễn bởi các kí tự: a, p, Y, o
Vi dụ 1.8.
Cho văn phạm G1 = ({S, A, B}, {a, b}, R, S), trong đó R gồm các luật sinh sau: S aS I bA, A Bb, B bB I aA I £
Cho văn phạm G2 = ({S}, {0, 1}, {S 0S1 I £}, S)
Từ văn phạm để sinh ra câu, chúng ta có khái niệm dẫn xuất.
Định nghĩa 1.2.
Cho văn phạm G = (N, X, R, S) và hai xâu u e (N u X)' và V e (N u X)*
Dần xuất trực tiếp (hay dẫn xuất một bước): ta nói u dẫn xuất trực tiếp ra V, kí hiệu u V, nếu và chỉ nếu:
G
u = xay
V = xPy
a p e R
Dần xuất gián tiếp (hay dẫn xuất nhiều bước): ta nói u dẫn xuất gián tiếp ra V, kí
*
hiệu u V, nếu và chỉ nếu:
G
u	W,	W2	... V
G 1 G 2 G G
Định nghĩa 1.3.
Cho G = (N, X, R, S), câu w eX* do văn phạm G sinh ra nếu và chỉ nếu:
*
s w
G
Nghĩa là phải tồn tại: sW1	w2	... w, các W1, w2, ... được gọi là các dạng câu của
G G G G
dẫn xuất.
Định nghĩa 1.4.
Cho văn phạm G = (N, X, R, S), ngôn ngữ L do văn phạm G sinh ra là:
L(G) = {w e X* I s => w }
G
Ví dụ 1.9. Cho văn phạm G1 = ({S}, {0, 1}, {S 0S1 I e}, S)
thì S 0S1	00S11	000S111	000111 là một dẫn xuất ra câu.
Ngôn ngữ tương ứng của văn phạm G1 là: L(G1) = {0n1n I n > 0}.
Ví dụ 1.10. Cho văn phạm G2 = ({S, A}, {a, b}, {S aA, A aA, A b}, S)
Ngôn ngữ tương ứng của văn phạm G2 là: L(G2) = {anb I n > 0}.
Phân cấp văn phạm của Chomsky
Theo Chomsky có 4 loại văn phạm theo các dạng của luật sinh như sau:
Nếu các luật sinh đều có dạng A a hoặc A aB với A, B e N, a e X thì văn phạm được gọi là Văn phạm chính quy hay văn phạm loại 3.
Nếu các luật sinh có dạng A a, A e N, a e (N u X)* thì văn phạm được gọi là Văn phạm phi ngữ cảnh hay văn phạm loại 2.
Nếu các luật sinh có dạng a p, a e (N u X)}, p e (N u X)* thỏa mãn |a| < IPI thì văn phạm được gọi là Văn phạm cảm ngữ cảnh hay văn phạm loại 1.
Nếu không có hạn chế gì trên các luật sinh thì văn phạm được gọi là Văn phạm ngữ cấu (tự do) hay văn phạm loại 0.
Lưu ý rằng, văn phạm loại 3 là tập con của văn phạm loại 2, văn phạm loại 2 là tập con của văn phạm loại 1, và văn phạm loại 1 là tập con của văn phạm loại 0.
Khái niệm về ôtômát
Có rất nhiều hệ thống có thể được xem tại mỗi thời điểm thì ở trong một trạng thái (state) của một tập hợp hữu hạn các trạng thái. Mục đích của trạng thái là ghi nhớ lại một phần của lịch sử của hệ thống. Thuận lợi của việc chỉ có số hữu hạn các trạng thái là một hệ thống có thể được cài đặt với tập hợp hữu hạn tài nguyên.
Một cách không hình thức, một ôtômát gồm một tập hợp các trạng thái và các điều khiển dịch chuyển từ trạng thái này sang trạng thái khác khi nhận dữ liệu vào.
Ví dụ 1.11. Ôtômát đơn giản nhất là mô tả các trạng thái của một chuyển mạch (switch). Thiết bị cần ghi nhớ trạng thái của nó là bật hay tắt, cho phép người sử dụng ấn nút thì hiệu ứng nó phụ thuộc vào trạng thái hiện tại của thiết bị. Khi thiết bị ở trạng thái bật, người sử dụng ấn nút thì nó sẽ chuyển sang trạng thái tắt, ngược lại khi thiết bị đang ở trong trạng thái tắt người sử dụng ấn nút thì nó chuyển sang trạng thái bật. Mô hình ôtômát hữu hạn cho một chuyển mạch của thiết bị được mô tả trong hình vẽ 1.1.
Hình 1.1. Mô hình ôtômát hữu hạn mô tả thiết bị chuyển mạch
Ôtômát trên mô tả hai trạng thái bật và tắt của thiết bị, khi có sự tác động từ bên ngoài “ấn nót” thì nó sẽ chuyển từ trạng thái này sang trạng thái khác.
Ví dụ 1.12. Ôtômát mô tả một phần của bộ phân tích từ vựng. Hình vẽ 1.2 mô tả ôtômát hữu hạn nhận biết từ khóa begin.
Hình 1.2 Mô hình ôtônát hữu hạn đoán nhận từ khóa begin
Mỗi trạng thái của ôtômát biểu diễn phần xâu đã được nhận biết của từ khóa begin. Quá trình nhận biết bắt đầu từ xâu rỗng, cho đến khi từ begin được nhìn thấy thì trạng thái cuối cho phép đoán nhận từ khóa.
Chương 2. Ôtômát hữu hạn
Chương này sẽ giới thiệu lớp ngôn ngữ, được gọi là “ngôn ngữ chính qưý”. Lớp ngôn ngữ này được mô tả bởi ôtômát hữu hạn. Lớp ôtômát hữu hạn được chia làm hai loại: ôtômát hữu hạn đơn định là ôtômát mà tại một thời điểm nó chỉ có thể ở trong một trạng thái nhất định, trong khi ôtômát hữu hạn không đơn định (bất định) là ôtômát mà tại mỗi thời điểm có thể ở trong nhiều trạng thái khác nhau.
Ôtômát hữu hạn đơn định (deterministic finite automata - DFA)
Mô tả không hình thức
Ôtômát hữu hạn là một cái “máy” đoán nhận xâu. Nó bao gồm các bộ phận sau:
một băng vào được chia thành ô, dùng để ghi xâu vào, mỗi kí hiệu của xâu vào thuộc bảng chữ X được ghi trên một ô;
một đầư đọc, mỗi thời điểm đọc (trỏ) đến một ô trên băng vào;
một bộ điềư khiển Q, gồm một số hữu hạn các trạng thái, tại mỗi thời điểm nó có một trạng thái.
Băng vào
Hỉnh 2,1 Mô tả ôtômát hữư hạn đơn định
Hoạt động của ôtômát được thực hiện như sau: Ôtômát hoạt động theo từng bước. Mỗi bước như sau: tùy theo trạng thái hiện thời của bộ điều khiển và kí hiệu mà đầu đọc đang đọc, mà ôtômát chuyển sang một trạng thái mới, đồng thời đầu đọc dịch chuyển sang phải một ô.
Quy luật chuyển trạng thái của ôtômát hữa hạn đơn định được mô tả bởi một hàm, được gọi là hàm dịch chuyển (transition function) như sau:
ỗ : Q x X Q
Trong Q, có một trạng thái đầư, thường kí hiệu qo và một tập hợp các trạng thái cưoi/thừa nhận, thường kí hiệu F (F c Q).
Ta nói ôtômát thừa nhận xâu vào w nếu sau khi xuất phát từ trạng thái đầu qo và đầu đọc chỉ vào kí tự bên trái nhất của xâu w, sau một số bước dịch chuyển hữu hạn, ôtômát đọc xong xâu w và rơi vào một trong các trạng thái cuối thuộc F.
Tập hợp tất cả các xâu đoán nhận bởi ôtômát hợp thành ngôn ngữ được thừa nhận bởi ôtômát đó.
Mô tả hình thức
Định nghĩa 2.1. Một ôtômát hữu hạn đơn định (DFA) được định nghĩa như là một bộ năm:
M = (Q, X, ỗ, qo, F)
Trong đó:
Q là tập hữu hạn các trạng thái, Q = {qo, q1,	qn}.
X là bảng chữ vào.
ỗ : Q x X Q là hàm dịch chuyển, ỗ có thể được viết dưới dạng ỗ(q, a) = q’, nghĩa là ôtômát đang ở trạng thái q và đọc kí hiệu a thì nó sẽ chuyển sang trạng thái q’.
qo e Q là trạng thái đầu.
F c Q là tập các trạng thái thừa nhận hay trạng thái cuối.
DFA xử lí xâu như thế nào
Giả sử w = aoa1...an là xâu vào. DFA sẽ bắt đầu với trạng thái qo, nó sẽ thực hiện dịch chuyển ỗ(qo, a1) giả sử cho q1. DFA bây giờ ở trạng thái q1 và kí tự tiếp theo sẽ đọc là a2, nó thực hiện dịch chuyển ỗ(q1, a2) giả sử cho q2. Nó cứ tiếp tục như thế, cho đ ...  bản.
Máy Turing có thể được mô tả bởi hình vẽ sau:
B
B
X1
X2
Xi
Xn
B
B
c
Đầu đọc	Băng
Bộ điều khiển
Hỉnh vẽ 6.1. Mô hỉnh máy Turing
Như thế, máy Turing gồm:
Một bộ điều khiển với một số hữu hạn các trạng thái, trong đó có một trạng thái đầu và một số các trạng thái cuối hay trạng thái thừa nhận.
Một băng được chia thành ô, mỗi ô chứa một kí hiệu. Ban đầu, xâu vào gồm các kí hiệu từ bảng chữ vào được đặt trên băng. Các ô còn lại trên băng vô hạn về phía bên trái và vô hạn về phía bên phải được lấp đầy bởi một kí hiệu đặc biệt, gọi là kí hiệu trắng (blank), được kí hiệu là B hoặc #. Các kí hiệu trắng ở trên băng nhưng không thuộc bảng chữ vào.
Một đầu đọc dịch chuyển trên băng. Đầu đọc ban đầu chỉ vào ô chứa kí hiệu vào bên trái nhất trên băng.
Một bước dịch chuyển của máy Turing phụ thuộc vào trạng thái hiện tại của bộ điều khiển và kí hiệu được đọc trên băng mà nó thực hiện:
Thay đổi trạng thái. Tuy nhiên, có thể ở lại trạng thái cũ.
Viết một kí hiệu lên ô đang được đọc thay thế cho kí hiệu cũ. Kí hiệu mới được viết lên có thể là giống với kí hiệu hiện tại trên băng.
Dịch chuyển đầu đọc sang phải hoặc sang trái một ô.
Máy Turing đoán nhận xâu vào khi nó đạt đến một trong các trạng thái cuối.
Như vậy, chúng ta nhận thấy máy Turing khác với ôtômát hữu hạn là đầu đọc có thể dịch chuyển tự do trên băng (sang phải hay sang trái) và không những đọc mà còn có thể ghi.
Định nghĩa 6.1. Máy Turing được định nghĩa bởi bộ bảy:
M = (Q, s, r, ỗ, qo, B, F)
trong đó:
Q là tập hữu hạn các trạng thái,
E là bảng chữ vào,
r là tập các kí hiệu sử dụng trên băng, E là tập con của r,
qo e Q là trạng thái đầu,
B e r - E là kí hiệu trắng,
F c Q là tập hữu hạn các trạng thái cuối/thừa nhận,
ỗ là hàm dịch chuyển được định nghĩa như sau:
ỗ : Q x r Q x r x {L, R}
trong đó, L va R biểu diễn “trái” hay “phải” là hướng dịch chuyển của đầu đọc.
Hay chúng ta có thể biểu diễn hàm dịch chuyển cụ thể như sau:
ỗ(q, X) = (p, Y, D) với p, q e Q; X, Y e r; D e {L, R}.
Nghĩa là, máy Turung đang ở trạng thái ! và đọc kí hiệu X, thì	máy	Turing	sẽ ghi lên	ô vừa
đọc kí hiệu s thay thế cho X, chuyển sang trạng thái p và dịch đầu đọc sang hướng D.
Ví dụ 6.1. Xây dựng máy Turing đoán nhận ngôn ngữ L = {anbn I n > o}.
Chúng ta sẽ xây dựng máy Turing với ý tưởng là thay mỗi kí	hiệu	a bởi X và thay	mỗi	kí
hiệu b bởi s, cho đến khi tất cả các a được so khớp với các b.
Cụ thể, ban đầu, xuất phát từ kí hiệu vào trái nhất, thay kí hiệu a bởi X và dịch phải vượt qua các kí hiệu a và s nếu gặp, cho đến khi gặp kí hiệu b. Thay kí hiệu b đó bởi s và dịch trái vượt qua các kí hiệu s và a nếu gặp, cho đến khi gặp kí hiệuX. Tại thời điểm này, thì dịch phải một ô, nếu tìm thấy kí hiệu a thì thay nó bởi X và lặp lại chu trình trên để thay kí hiệu b ứng với kí hiệu a đó bởi s. Máy Turing sẽ đoán nhận xâu vào khi thay b bởi s mà không tìm thấy thêm kí hiệu a nào nữa và cũng không tìm thấy thêm kí hiệu b nào nữa.
Vậy máy Turing gồm các thành phần như sau:
M = (Q, X, r, ỗ, qo, B, F)
trong đó:
Q = {qo, qi, q2, q3, q#},
s = {a b},
r = {X, Y, a, b, B},
F = {q#}
ỗ được xây dựng như sau:
ỗ(qo, a) = (qb X, R). Đọc kí hiệu trái nhất a.
S(q1? a) = (qb a, R). Vượt phải qua các kí hiệu a để tìm kí hiệu b.
S(q1? Y) = (qb Y, R). Vượt phải qua các kí hiệu Yđể tìm kí hiệu b.
S(q1? b) = (q2, Y, L). Gặp kí hiệu b tương ứng với kí hiệu a vừa thay thế trước đó.
ỗ(q2, Y) = (q2, Y, L). Vượt trái qua các kí hiệu Y để tìm kí hiệu a trái nhất.
ỗ(q2, a) = (q2, a, L). Vượt trái qua các kí hiệu a để tìm kí hiệu a trái nhất.
ỗ(q2, X) = (qo, X, R). Gặp kí hiệuX đầu tiên bên cạnh nó sẽ là kí hiệu a trái nhất cần tìm nếu có.
ỗ(qo, Y) = (q3, Y, R). Không còn tìm thấy kí hiệu a trái nhất.
ỗ(q3, Y) = (q3, Y, R). Vượt phải qua các Y, tìm xem còn kí hiệu b nào nữa không.
ỗ(q3, B) = (q4, B, R). Không còn tìm thấy thêm kí hiệu b nào nữa. Vậy đoán nhận xâu vào.
Biểu diễn máy Turing bằng biểu đồ
Chúng ta cũng có thể sử dụng biểu đồ dịch chuyển biểu diễn máy Turing mà trong đó:
Các nút biểu diễn các trạng thái.
Có một mũi tên đi vào nút qo để kí hiệu trạng thái đầu.
Các trạng thái kết thúc F là các nút được biểu diễn bởi hai vòng tròn.
Các trạng thái không thuộc F là các nút được biểu diễn bởi chỉ một vòng tròn.
Các cung tương ứng với các dịch chuyển. Một cung từ trạng thái q đến trạng thái p được gán nhãn X/ Y, D nghĩa là ỗ(q, X) = (p, Y, D).
Ví dụ 6.2. Biểu diễn máy Turing trong ví dụ 6.1 bàng biểu đồ.
Hình vẽ 6.2. Máy Turing đoán nhận ngôn ngữ L = {anbn N n > 0}
Cấu hình của máy Turing
Cũng tuơng tự nhu ôtômát đẩy xuống, máy Turing có khái niệm cẩu hình. Tuy nhiên, đối với máy Turing, băng vô hạn về cả hai phía và đầu đọc tự do dịch chuyển trên băng, tức là dịch trái hoặc dịch phải. Nên tại mỗi thời điểm, để mô tả cấu hình của máy Turing chúng ta phải mô tả toàn bộ các kí hiệu trên băng, vị trí đầu đọc và trạng thái hiện tại của máy Turing.
Định nghĩa 6.2. Cho máy Turing M = (Q, X, r, ỗ, qo, B, F), cấu hình máy Turing đuợc định nghĩa bởiX1X2...Xi.iqXiXi+Ị...xn, trong đó:
q e Q là trạng thái của máy Turing,
đầu đọc chỉ vào kí hiệu Xi,
X1X2oXn là xâu trên băng từ trái qua phải chứa các kí hiệu khác kí tự trắng B.
Định nghĩa 6.3. Cho máy Turing M = (Q, r, ỗ, qo, B, F), ta định nghĩa dịch chuyển cẩu hình, kí hiệu bởi |-, nhu sau:
Nếu ỗ(q, Xi) = (p, Y, L) thì ta có dịch chuyển cấu hình sau:
X1X2...Xi-iqXiXi+ioXn h X1X2... Xi-2pXi-iYXi+ioXn
Nếu ỗ(q, Xi) = (p, Y, R) thì ta có dịch chuyển cấu hình sau:
X1X2...Xi-iqXXi+i...Xn h X1X2... Xi-iYpXi+ioXn
Tuơng tự, sử dụng kí hiệu p để biểu diễn dịch chuyển từ không đến nhiều cấu hình.
Ví dụ 6.3. Thực hiện đoán nhận xâu aabb trên máy Turing đuợc xây dựng ở ví dụ 6.i. qoaaabbb p Xqiaabbb p Xaqiabbb p Xaaqibbb p Xaq.-aYbb [■ Xq.-aaYbb q2XaaYbb |- XqoaaYbbp XXqiàYbbh XXa qiYbbp XXaYqibbp -XXaq.'YYb^ XXq.-aYYbị- Xq.'.XaYYb p XXqoaYYb h XXXqiYYb p XXXYqiYb p XXXYYqib p XXXYYq2Y |- XXXYq.-YY	XXXq2YYY ị-	XXq2XYYY ị-	XXXqoYYY ị-	XXXYq3YY |-
XXXYYq3Y |- XXXYYYJsB |- XXXYYYBq.|B.
Hay chúng ta có thể mô tả ngắn gọn hơn: qoaaabbb p XXXYYYBq4B.
Ngôn ngữ được đoán nhận bởi máy Turing
Chúng ta vừa nhận thấy máy Turing đoán nhận ngôn ngữ. Nó bắt đầu đọc kí hiệu trái nhất của xâu vào trên băng và nếu nó đạt đến một trong các trạng thái cuối thì xâu vào đuợc thừa nhận.
Định nghĩa 6.4. Cho máy Turing M = (Q, E, r, ỗ, qo, B, F). L(M) là ngôn ngữ đuợc đoán nhận bởi máy Turing:
L(M) = {w e s* I qow p aq$}
trong đó qf e F; a, p e r*.
Định nghĩa 6.5. Ngôn ngữ đuợc đoán nhận bởi máy Turing đuợc gọi là ngôn ngữ Hệt kê đệ quy (recursively enumerable languages).
Bài tập
Xây dựng máy Turing đoán nhận các ngôn ngữ sau:
{anbncn I n > o}.
{wwR I w e {a, b}*}.
6.2 Tỉnh toán bởi máy Turing
Nhu chúng ta đã biết máy Turing không chỉ đoán nhận ngôn ngữ mà còn có thể thực hiện các tính toán.
Định nghĩa 6.6. Máy Turing tính hàm f: É É nếu với một xâu vào w bất kỳ, máy Turing luôn dừng trong một hình trạng mà f(w) ở trên băng. Hàm f đuợc gọi là hàm tính được (computable function).
Ví dụ 6.4. Xây dựng máy Turing tính hàm f(n) = n + 1, với n là số nguyên duơng.
Chúng ta sẽ biểu diễn n bởi dãy nhị phân. Khi đó, ta sẽ thực hiện phép cộng 1 vào dãy nhị phân. Máy Turing sẽ thực hiện: tìm kí hiệu cuối cùng của dãy nhị phân, nếu đó là kí hiệu o thì thay bởi 1 và kết thúc, nếu đó là kí hiệu 1 thì thay bởi o và dịch trái lặp lại quá trình trên. Nếu cuối cùng gặp kí hiệu trắng B bên trái thì thay bởi 1 và kết thúc.
M = ({qo, q1, q2}, {o, 1}, {o, 1, B}, ỗ, qo, B, {q2})
với ỗ đuợc xây dựng nhu sau:
ỗ(qo, o) = (qo, o, R). Dịch phải tìm kí hiệu cuối cùng.
ỗ(qo, 1) = (qo, 1, R). Dịch phải tìm kí hiệu cuối cùng.
ỗ(qo, B) = (q1, B, L). Gặp kí hiệu cuối.
ỗ(q1, o) = (q2, 1, R). Nếu là kí hiệu o thì thay bởi 1 và kết thúc.
ỗ(q1, 1) = (q1, o, L). Nếu là kí hiệu 1 thì thay bởi o và dịch trái.
ỗ(q1, B) = (q2, 1, R). Nếu gặp kí hiệu B bên trái thì thay bởi 1 và kết thúc.
Tuy nhiên, khi tính toán trên các số nguyên duơng bởi máy Turing, cách biểu diễn bằng các chữ số nhị phân không thuận tiện bằng việc biểu diễn mỗi số nguyên n bởi n + + kí hiệu 1 (chúng ta sử dụng n + 1 kí hiệu, vì muốn biểu diễn đuợc số 0).
Ví dụ 6.5. Xây dựng máy Turing tính hàm f(m, n) = m + n, với m và n là các số nguyên duơng.
Khi đặt trên băng, hai số nguyên m và n đuợc cánh nhau bởi kí hiệu trắng B. Nhu thế, phép cộng thực ra là thay kí hiệu trắng bởi kí hiệu 1 và xóa bớt hai kí hiệu 1 trên băng.
M = ({qo, qi, q2, q3}, {1}, {1, B}, ỗ, qo, B, {q2})
với ỗ đuợc xây dựng nhu sau:
ỗ(q0,	1) = (q1, B, R). Thay kí hiệu 1 thứ nhất bởi B.
ỗ(q1,	1) = (q2, B, R). Thay kí hiệu 1 thứ hai bởi B.
ỗ(q2,	1) = (q2, 1, R). Dịch phải để tìm kí hiệu B ngăn hai	số m và n.
ỗ(q2,	B) = (q3, 1, R). Thay kí hiệu B bởi 1 và kết thúc.
ỗ(q1,	B) = (q3, B, R). Truờng hợp m = 0, thì n chính là kết	quả.
Bài tập
Xây dựng máy Turing tính các hàm sau:
f(n) = n n 1 với n > 0.
Cho n và m là các số nguyên duơng,
f(n, m) = 0 nếu n > m,
f(n, m) = 1 nếu n < m
Xây dựng máy Turing tính hàm:
f(n, m) = n n m	nếu n > m,
f(n, m) = 0	nếu n < m,
với m và n là các số nguyên duơng.
Luận đề Church-Turing (Church Turing thesis)
Luận đề Church-Turing liên quan đến khái niệm thủ tục hiệu quả. Thủ tục hiệu quả là thủ tục giải quyết đuợc vấn đề đặt ra và đạt đuợc kết quả mong muốn.
Luận đề Church-Turing đuợc phát biểu nhu sau: “Các hàm tính toán đuợc bởi các thủ tục hiệu quả thì cũng đuợc tính bởi máy Turing”.
Có thể hiểu rằng, các bài toán giải được trong thực tế thì sẽ đuợc tính toán bởi máy Turing. Nhu thế, chúng ta có thể thấy luận đề Church-Turing chủ yếu liên quan đến vấn đề tính toán bởi máy Turing. Luận đề này đuợc ứng dụng để nghiên cứu về lý thuyết tính toán. Đây là vấn đề vuợt quá khuôn khổ của giáo trình này.
Tuy nhiên, chúng ta có thể hiểu luận đề đối với ngôn ngữ, là vấn đề chúng ta quan tâm trong khuôn khổ giáo trình này: “Các ngôn ngữ nhận biết đuợc bởi các thủ tục hiệu quả thì cũng đuợc đoán nhận bởi máy Turing”.
Nghĩa là, các ngôn ngữ mà tồn tại các phương pháp đoán nhận chúng, thì tồn tại máy Turing đoán nhận chúng.
Các kỹ thuật xây dựng máy Turing
Mô hình máy Turing mà chúng vừa xem xét là mô hình đơn giản nhất. Ngoài ra, còn có một số các kỹ thuật khác để xây dựng bộ điều khiển và băng của máy Turing.
Nhớ ở bộ điều khiển hữu hạn
Mỗi trạng thái của máy Turing không chỉ lưu giữ trạng thái điều khiển mà còn lưu giữ một lượng dữ liệu. Chẳng hạn, một trạng thái như hình vẽ 6.3 gồm trạng thái điều khiển q và ba phần tử dữ liệu A, B và c, nghĩa là một trạng thái được biểu diễn [q, A, B, c]:
Ví dụ 6.6. Xây dựng máy Turing đoán nhận ngôn ngữ L(01* + 10*).
Chúng ta sẽ xây dựng mỗi trạng thái gồm [q a]: trạng thái điều khiển q và một kí hiệu a e {0, 1}. Máy Turing sẽ thực hiện: khi đọc kí hiệu đầu tiên của xâu vào sẽ ghi nhớ vào thành phần thứ hai của trạng thái và sau đó kiểm tra xem kí hiệu này có xuất hiện trong phần còn lại của xâu vào không.
M = (Q, {0,1 u, {0, 1, B), ỗ, [qo, B], [q1, B])
trong đó: Q = {qo, qi} x {0, 1, B}.
Hàm dịch chuyển s được định nghĩa như sau:
ỗ([q0, B], 0) = ([q1, 0], 0, R). Đọc kí hiệu đầu tiên là 0 và ghi nhớ nó vào trạng thái.
ỗ([q0, B], 1) = ([q1, 1], 1, R). Đọc kí hiệu đầu tiên là 1 và ghi nhớ nó vào trạng thái.
ỗ([q1, 0], 1) = ([q1, 0], 1, R). Đọc kí hiệu các kí hiệu 1 sau khi đã đọc kí hiệu 0.
ỗ([q1, 1], 0) = ([q1, 1], 0, R). Đọc kí hiệu các kí hiệu 0 sau khi đã đọc kí hiệu 1.
ỗ([q1, 0], B) = ([q1, B], 0, R). Đoán nhận.
ỗ([q1, 1], B) = ([q1, B], 0, R). Đoán nhận.
Băng nhiều rãnh
Băng của máy Turing có thể gồm nhiều rãnh.	Mỗi	ô trên rãnh chứa một kí	hiệu,	như thế	mỗi
kí hiệu vào sẽ là một bộ các kí hiệu, mỗi kí	hiệu	trên	một	rãnh.	Chẳng	hạn,	kí	hiệu	vào
[X, Y, Z] đối với băng có ba rãnh. Cũng tương tự như kỹ thuật nhớ ở bộ điều khiển, sử dụng băng nhiều rảnh, máy Turing không mở rộng khả năng của nó. Đó chỉ là một cách tổ chức băng vào.
Chương trình con
Cũng giống như đối với các chương trình bình thường, máy Turing có thể được xây dựng gồm nhiều chương trình con tương tác với nhau. Mỗi chương trình con được gọi lúc cần và thực hiện xong chương trình con thì trở về tiếp tục thực hiện chương trình chính.
Mỗi chương trình con được tính bởi máy Turing gồm một tập hợp riêng các trạng thái, trong đó có trạng thái đầu và trạng thái cuối. Khi gọi chương trình con thì máy Turing chuyển về trạng thái đầu của chương trình con. Sau khi kết thúc chương trình con, máy Turing chuyển từ trạng thái cuối của chương trình con về trạng tiếp theo để thực hiện chương trình chính.
Các mô hình khác của máy Turing
Ngoài mô hình cơ bản của máy Turing, còn có một số mô hình mở rộng phức tạp hơn, tuy nhiên chúng đều tương đương với mô hình cơ bản của máy Turing.
6.5.1 Máy Turing có nhiều băng
Máy Turing này gồm có một bộ điều khiển hữu hạn, một số hữu hạn các băng và mỗi đầu đọc cho mỗi băng (Hình vẽ 6.4). Mỗi băng được chia thành ô, mỗi ô chứa một kí hiệu. Các kí hiệu trên băng gồm các kí hiệu của bảng chữ vào và kí hiệu trắng. Các trạng thái gồm có trạng
thái đầu và các trạng thái cuối.
Hình vẽ 6.4. Máy Turing có nhiều băng
Khởi đầu:
xâu vào được đặt trên băng thứ nhất,
tất cả các ô của các băng còn lại được lấp đầy bởi kí hiệu trắng,
bộ điều khiển ở trạng thái đầu,
đầu đọc chỉ đến kí hiệu vào trái nhất trên băng thứ nhất,
tất cả các đầu đọc trên các băng khác có thể chỉ vào bất kỳ ô nào trên băng tương ứng, vì khởi đầu tất cả các ô trên các băng này đều là kí hiệu trắng.
Mỗi bước dịch chuyển phụ thuộc vào trạng thái hiện tại và kí hiệu đang đọc mà thực hiện:
chuyển trạng thái,
trên mỗi băng, kí hiệu đang được đọc được thay thế bởi kí hiệu mới,
mỗi đầu đọc thực hiện dịch chuyển sang trái, sang phải hay giữ nguyên vị trí một cách độc lập.
Máy Turing không đơn định
Cũng tương tự như khái niệm ôtômát hữu hạn đơn định và ôtômát hữu hạn không đơn định, máy Turing không đơn định khác với máy Turing đơn định ở định nghĩa hàm dịch chuyển, ở mỗi bước nó có một số khả năng lựa chọn trong quá trình dịch chuyển. Nghĩa là hàm dịch chuyển s của máy Turing không đơn định đối với mỗi trạng thái ! và kí hiệu trên băng X, thì ỗ(q, X) cho kết quả là tập hợp các bộ ba:
{(!+, Ylt Dị), (!2, Y2, D2), o, (!ko Yk, Dk)}
với 5 là mộ số tự nhiên hữu hạn.
Tuy nhiên, tính không đơn định không mở rộng khả năng của máy Turing. Thật vậy, một ngôn ngữ được đoán nhận bởi máy Turing không đơn định thì nó cũng được thừa nhận bởi máy Turing đơn định.
Tài liêu tham khảo
J. E. Hopscoft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addsion - Wesley, 2001.
A. Stoughton, An Introduction to Formal Language Theory that Integrates Experimentation and Proof, GNU, 2004.
J. M. Autebert, Théorie des languages et des automats, Masson 1994.
Hồ Văn Quân, Giáo trình lý thuyết automat và ngôn ngữ hình thức, NXB Đại học Quốc gia TP Hồ chí Minh, 2002.
Lê Mạnh Thạnh, Nhập môn ngôn ngữ hình thức & Ôtômát hữu hạn, NXB Giáo dục, 2000.
Phan Huy Khánh, Giáo trình Lý thuyết Ngôn ngữ hình thức và Ôtômát, Khoa CNTT, Truờng Đại học Bách khoa, Đại học Đà Nang.
Nguyễn Văn Ba, Ngôn ngữ hình thức, NXB Khoa học và Kỹ thuật, 2002.