Giáo trình Toán rời rạc - Phạm Thế Long

 D1AA 
 6) C2a 13) BC6D2 
 7) BC3k 14) D2BB 
Rõ ràng là G' ở dạng chuẩn mà L(G) = L(G'). 
Định lý 4.4.2. Dạng chuẩn Greibach. Cho văn phạm phi ngữ cảnh G = (N, T, P, k). Có thể 
tìm được văn phạm phi ngữ cảnh G' =(N', T, P', k) tương đương sao cho mọi quy tắc dẫn xuất 
của G' có dạng: 
Aa AN', a T, N'* và L(G) = L(G') 
Văn phạm G' như trên được gọi là văn phạm dạng chuẩn GreiBach tương đương với G. 
4.5. Lực lượng của văn phạm phi ngữ cảnh 
Chúng ta đã đề cập đến tính rỗng của văn phạm phi ngữ cảnh. Chúng ta đã khẳng định tồn 
tại thuật toán để đoán nhận ngôn ngữ phi ngữ cảnh là rỗng hay không. Do yêu cầu diễn đạt thuật 
toán rất phong phú đa dạng, người ta cần một văn phạm sinh ra ngôn ngữ là tập vô hạn. Vấn đề 
đặt ra là liệu có cách nào kiểm tra xem văn phạm đã cho sinh ra tập ngôn ngữ hữu hạn hay vô 
hạn, phần này sẽ đề cập đến lực lượng của tập ngôn ngữ do một văn phạm phi ngữ cảnh sinh ra. 
Định lý 4.5.1. Cho L là ngôn ngữ phi ngữ cảnh bất kỳ. Khi đó tồn tại hai số p và q chỉ phụ 
thuộc L, sao cho  zL, z p thì z có thể viết được dạng z = uvwxy thoả mãn điều kiện: 
 vwx q 
 Các xâu x,v không đồng thời là xâu rỗng e 
 Với  i  0 vuviwxiy  L 
 (Định lý trên còn có tên gọi là định lý uvwxy) 
Định lý 4.5.2. Tồn tại thuật toán để xác định văn phạm phi ngữ cảnh đã cho là hữu hạn 
hay vô hạn. 
Chứng minh: Cho G = (N, T, p, k). Chọn p = 2N-1 q = 2N . 
Giả sử có từ z L(G) z p. Khi đó theo định lý 3 xâu z có thể viết dưới dạng z = 
uvwxy mà xâu x và xâu v không đồng thời là xâu rỗng (v+x 0). Khi đó ta có uviwxiy  
L(G) với mọi i tuỳ ý. Từ đây suy ra L(G) vô hạn khi tồn tại xâu có độ dài lớn hơn p. 
Ngược lại nếu L(G) vô hạn nó phải có từ độ dài tùy ý (vì nếu không phải như vậy L(G) là 
hữu hạn). Do vậy trong L(G) phải có từ có độ dài hơn p+q. Giả sử z là xâu như vậy, khi đó xâu z 
có thể viết dưới dạng: 
 z = uviwxiy sao cho vwx q và v+x 0 và iN 
Bây giờ ta giảm i để cho xâu z có độ dài ngắn lại , mỗi lần giảm i từ z ngắn lại thực sự vì 
v+x 0. Giả sử sau một lần giảm i đi 1 đơn vị ta nhận được xâu z’ mà z’ p+q thì chúng 
ta dừng, ngược lại ta coi z’ đóng vai trò của z lặp lại quá trình rút gọn trên. 
Lập luận trên đây cho phép chúng ta suy ra nếu L vô hạn thì ta luôn luôn tìm được từ độ 
dài l sao cho p  l  q+p. 
Nói một cách khác L(G) vô hạn khi và chỉ khi tồn tại từ w có độ dài thoả mãn: 
 p  w p+q 
Từ kết luận trên suy ra để kiểm tra L(G) là hữu hạn hay vô hạn ta chỉ cần kiểm tra xem 
các xâu có độ dài lớn hơn p và không nhỏ hơn p+q có thuộc L(G) hay không? Thuật toán duyệt 
các xâu như vậy luôn luôn kết thúc sau một số hữu hạn bước vì tập các xâu có độ dài thoả mãn 
điều kiện trên là hữu hạn. 
5. Máy Turing 
5.1. Mở đầu 
Khái niệm trực giác về thuật toán mà chúng ta sử dụng từ trước đến nay là: Thuật toán là 
một dãy các qui tắc hay chỉ thị xác định một quá trình tính toán nào đó. Chẳng hạn thuật toán 
Euclide tìm ước số chung lớn nhất của hai số nguyên cho trước, thuật toán xác định một số 
nguyên cho trước có là số nguyên tố hay không? Tính gần đúng giá trị của sinx, cosx, v.v... Nếu 
không có các bài toán dẫn đến việc nghi ngờ có hay không có thuật toán giải quyết một bài toán 
nào đó thì người ta không cần bàn cãi đến khái niệm mang tính trực giác nêu trên. Bởi vì về mặt 
logic, muốn nói có hay không có thuật toán thì phải xác định được chính xác thuật toán là gì? 
Xuất phát từ các bài toán không biết có thuật toán giải nó hay không? buộc người ta phải đặt 
câu hỏi thuật toán là gì? Liệu có thể mô tả toán học chính xác về nó hay không? Liên quan đến 
vấn đề này chúng ta làm quen với máy Turing. 
Vào khoảng năm 1930-1936 các nhà toán học Godel, Kleene, Church, Turing đã cố gắng 
đưa ra mô tả toán học cho khái niệm thuật toán. Các khái niệm về thuật toán của các tác giả nêu 
trên nói chung đều tương đương với nhau. Trong số các khái niệm toán học chính xác về về 
thuật toán, khái niệm do nhà toán họcTuring đưa ra năm 1937 được thừa nhận rộng rãi bởi vì nó 
thuận tiện cho việc nghiên cứu các vấn đề trong lí thuyết và ứng dụng. Máy Turing mà nhà toán 
học Turing dùng để mô tả khái niệm thuật toán có giá trị cả trong nghiên cứu lí thuyết trừu 
tượng lẫn trong các quá trình tính toán cụ thể. Sau khi xuất hiện máy tính điện tử, máy Turing đã 
trở thành một mô hình toán học cho các máy tính thực tế. 
Như chúng ta đã biết, mọi quá trình thực hiện theo thuật toán, xét cho cùng đều là quá 
trình thực hiện một số phép biến đổi sơ cấp nào đó. Trong mô hình máy Turing, người ta chỉ 
dùng một loại biến đổi sơ cấp đơn giản đó là thay thế một kí hiệu này bằng một kí hiệu khác. Vì 
vậy máy Turing là mô hình mô tả toán học khái niệm thuật toán rất phù hợp. Sau khi đã có khái 
niệm chính xác về thuật toán, người ta có cơ sở để chuyển bài toán không có thuật toán giải nó 
về bài toán không có máy Turing tính nó. Trên cơ sở khái niệm thuật toán, cách đây gần nửa thế 
kỉ Turing và Church đã nêu ra luận đề mang tên Turing – Church. Mặc dù luận đề không có 
chứng minh nhưng cho đến nay người ta vẫn không tìm được phản ví dụ phủ định giá trị chân lý 
của nó. Luận đề Turing – Church có thể tóm tắt như sau: Mọi hàm số tính được theo nghĩa trực 
giác đều là hàm tính được bởi một máy Turing nào đó. 
Máy Turing được sử dụng nghiên cứu trong nhiều lĩnh vực khác nhau, để tiện cho việc 
nghiên cứu, trong mỗi lĩnh vực người ta đưa ra các định nghĩa khác nhau về máy Turing, trong 
phạm vi của giáo trình này, chúng ta sẽ nêu định nghĩa máy Turing và khảo sát nó theo góc độ 
ngôn ngữ. 
5.2. Khái niệm và định nghĩa 
Về mặt trực quan có thể coi máy Turing gồm bộ điều khiển có hữu hạn trạng thái (finite 
control), một băng vào (Input tape), băng này được chia thành từng ngăn hay từng ô (cell). Băng 
vào có ngăn trái nhất được coi là ngăn đầu tiên của băng và nó được coi là dài vô hạn về phía 
bên phải. Máy có một đầu đọc băng (tape head), đầu đọc này có thể dò đọc từng ngăn trên băng 
vào. Mỗi ngăn của băng vào có thể chứa một kí hiệu thuộc tập các kí hiệu vào (Input symbol). 
Một dòng vào là một dãy các kí hiệu của bảng chữ cái vào đặt trên băng, các ngăn trên băng 
không chứa kí hiệu vào được coi chứa kí hiệu trắng (blank), ta kí hiệu là B. Hình 1 mô tả cấu tạo 
của máy Turing. 
Hình 1. 
# a1 a2 a3 … … ai …… an # # # 
Bộ điều khiển 
Hoạt động của máy Turing được mô tả như sau: 
Giả sử máy ở trạng thái q, đầu đọc đang chỉ vào kí hiệu ai, nó sẽ chuyển đầu đọc sang 
phía trái hoặc phía phải của ai và thay ai bằng bj nào đó’ Nói một cách khác, phụ thuộc vào kí 
hiệu mà đầu đọc đang đọc trên băng vào và trạng thái của bộ điều khiển máy có thể thực hiện 
các thao tác sau: 
 Thay đổi trạng thái 
 Ghi một kí hiệu khác kí hiệu trắng đè lên kí hiệu đã có trên băng vào. 
 Dịch chuyển đầu đọc đi một ngăn sang trái hoặc sang phải. 
Định nghĩa 5.2.1. Về mặt hình thức ta có thể coi máy Turing là bộ 5 : T=. 
Trong đó: 
- S là tập hữu hạn các trạng thái. 
-  là tập hữu hạn kí hiệu vào. 
-  là ánh xạ, được gọi là hàm chuyển trạng thái, : S x  x {L,R } S x  . 
Chú ý rằng  có thể không xác định với một vài bộ giá trị của các đối số nào đó; L,R là kí 
hiệu chỉ hướng dịch chuyển sang trái hoặc sang phải tương ứng của đầu đọc. Khi đó kí hiệu 
(s,a,M)=(q,b) có nghĩa rằng automat ở trạng thái s, đầu đọc đang trỏ vào kí tự a máy đổi sang 
trạng thái q, thay kí tự a bằng kí tự b và di chuyển đầu đọc theo hướng M. 
- q0 là phần tử thuộc S gọi là trạng thái bắt đầu của máy Turing 
- F  S là tập các trạng thái kết thúc của automat. 
Hình 2. 
Hình 2 mô tả cách làm việc và chuyển đổi trạng thái của máy Turingứng với các trường hợp: 
a/(s,a,L)=(s’,b) 
b/(s,a,L)=(s’,a) 
c/(s,a,R)=(s’,b) 
d/(s,a,R)=(s’,a) 
 L R 
R L 
a/b a/b 
a. a/b 
s’ 
s’ 
s’ 
s’ 
s 
s s 
s 
a) 
b) 
c) 
d) 
Định nghĩa 5.2.2. Ta gọi bộ bốn (s,x,,y) là hình trạng của máy Turing, với sS, s là trạng 
thái hiện thời của T; x, y, *,, ở đây  là kí hiệu nằm trên băng vào mà đầu đọc đang trỏỉ 
vào nó, x là từ ở bên trái đầu đọc, y là từ ở bên phải đầu đọc. 
Giả sử máy Turing T ở hình trạng (s,x,,y). Nó được gọi là chuyển sang hình trạng 
(s’,x’,’,y’), nếu (s,,M)=(s’,’). Khi đó ta viết: 
(s,x,,y)  (s’,x’,’,y’) 
Giả sử máy Turing T ở hình trạng (s,x,,y) và có một dãy hình trạng 
(s1,x1,1,y1),(s2,x2,2,y2),...,(sn,xn,n,yn) mà: 
(s,x,,y)(s1,x1,1,y1)(s2,x2,2,y2)...(sn,xn,n,yn). 
Khi đó ta kí hiệu ngắn gọn là: (s,x,,y)*(sn,xn,n,yn). 
Nếu máy Turing T đang ở một hình trạng nào đó mà không thể chuyển sang hình trạng 
nào khác. Khi đó có thể xảy ra một trong hai tình huống sau: 
 Máy đang ở hình trạng có chứa trạng thái qfF  S, khi đó ta nói máy Turing ở hình 
trạng kết thúc. 
 Máy đang ở hình trạng mà đầu đọc đã ở ngăn đầu tiên bên trái mà nó vẫn phải tiếp tục 
di chuyển về bên trái, khi đó ta nói máy Turing ở hình trạng tắt. 
Máy Turing ở một trong hai hình trạng kết thúc hoặc tắt gọi là hình trạng dừng hoặc chết. 
Hình trạng (q0,e,#,x) được gọi là hình trạng ban đầu của máy Turing T, ở đây e là kí hiệu 
xâu rỗng,# là kí hiệu giới hạn trái của xâu x , đầu đọc trỏ vào kí tự đầu tiên của x. 
5.3. Hàm Turing thực hiện được 
Định nghĩa 5.3.1. Giả sử  là một bảng chữ cái,  là ánh xạ : * *.  được gọi là 
hàm Turing thực hiện được, nếu tồn tại máy Turing T = sao cho 
(q0,e,#,x)*(q,z,,y) và hình trạng (q,z, ,y) là hình trạng dừng khi và chỉ khi (x)=y. Nếu đối 
với xâu vào #x máy T ở hình trạng dừng nhưng không đạt đến hình trạng kết thúc, thì (x) được 
coi là không xác định với x. 
Định nghĩa 5.3.2. Cho máy Turing T = ta gọi tập 
L(T)={x*(q0,e,#,x)*(s’,z,,y), s’F} 
là ngôn ngữ đoán nhận bởi máy Turing T. 
Hình 1 mô tả tình trạng trên băng vào khi máy Turing ở trạng thái bắt đầu và ở trạng thái 
dừng. 
Hình 1. 
Chú ý: Máy Turing T = được gọi là tất định, nếu 0(s,a,M) 1; ngược lại 
T được gọi là không tất định. Một ngôn ngữ có thể đoán nhận bởi máy Turing tất định hoặc 
không tất định. 
Có thể định nghĩa ngôn ngữ đoán nhận bởi máy Turing T = bằng cách sau: 
Giả sử  là hàm nào đó : * * ta gọi miền xác định của hàm  Turing thực hiện được là 
ngôn ngữ đoán nhận bởi máy Turing T. 
Ví dụ 5.3.1. Máy Turing cho bởi sơ đồ ở hình 2 đoán nhận ngôn ngữ là tập 
L = {anbncn ; nN}. 
Hình 2. 
Khái niệm văn phạm, ngôn ngữ và phân loại ngôn ngữ sẽ được đề cập ở phần sau, tuy 
nhiên ngay từ đây, chúng ta có thể hiểu văn phạm loại 0 là văn phạm không có bất kì một điều 
kiện ràng buộc nào và nó sinh ra lớp ngôn ngữ rất phức tạp như lớp các ngôn ngữ tự nhiên mà 
loài người đang sử dụng. Liên quan đến lớp ngôn ngữ loại 0 ta có định lý sau. 
 từ vào trên băng từ kết thúc trên băng 
 # x .. .. .. …….. # z  y 
L R 
R R 
R L 
 R 
#, a 
a, b, c, x, y, z b/z 
c/z 
s3 s2 
a/x s1 
# 
x 
s4 s5 
# # # 
(yes) (no) 
s7 s6 
a, b, c, x, y, z 
b/y 
a, b, c 
#, c 
Định lý 5.3.1. Ngôn ngữ L sinh bởi văn phạm loại 0 khi và chỉ khi nó là ngôn ngữ đoạn 
nhận bởi máy Turing . 
Chúng ta sẽ không chứng minh định lý này, tuy nhiên kết quả định lý trên cho chúng ta 
nhìn nhận một cách hệ thống vấn đề đang xem xét: Có thể nghiên cứu ngôn ngữ theo quan điểm 
sinh và quan điểm đoán nhận, hai quan điểm này ứng với hai công cụ là văn phạm và Automat. 
Kết quả thu được từ hai công cụ này là tương đương nhau. 
Nhờ máy Turing chúng ta đã đưa ra khái niệm hàm Turing thực hiện được. Thực chất của 
hàm Turing thực hiện được là hàm biến đổi một xâu x sang xâu x’ với x,x’*. Dựa vào hàm 
Turing thực hiện được chúng ta đưa ra khái niệm hàm Turing tính được. 
Định nghĩa 5.3.3. Chúng ta nói rằng hàm  :NnN là Turing tính được, nếu tồn tại máy 
Turing thực hiện hàm  :1,&* 1* thoả mãn điều kiện : 
a/ (1x1+1&1x2+1&......,&1xk+1)=1y+1, nếu (x1,x2,....xk)=y ; 
b/ (1x1+1&1x2+1&.....,&1xk+1)= không xác định, nếu (x1,x2,.....xk) không xác định. 
Ví dụ 5.3.2. Hàm f(x,y)=x+y là hàm Turing tính được. 
Ta xây dựng máy Turing T= 
'=1,&,B ,S==q0, q1, q2,q3 
Hàm chuyển trạng thái được cho trong hình 3c. Hình 3a, 3b tương ứng là trạng thái của băng vào 
lúc bắt đầu và khi kết thúc. 
Hình 3. 
5.4. Độ phức tạp của thuật toán 
Nhờ máy Turing, chúng ta đã có được khái niệm chính xác về thuật toán. Tuy nhiên với 
một hàm Turing tính được người ta có thể xây dựng các máy Turing khác nhau, nghĩa là có các 
# 11…1&111..1 #B11………1 
R R 
R 
a) b) 
c) 
q2 q3 
B/B 
1/B 
q0 
q1 
&/1
Stop 
q0 
1/1 
thuật toán khác nhau để thực hiện một bài toán. Một cách tự nhiên câu hỏi được đặt ra là: trong 
các thuật toán tính hàm f, toán thuật nào tốt hơn, tốt hơn theo nghĩa nào ? Đây là vấn đề rất quan 
trọng trong khoa học tính toán và ứng dụng thực tiễn. Liên quan đến vấn đề này chúng ta làm 
quen với một số khái niệm sau: 
Định nghĩa 5.4.1. Giả sử w* , ta kí hiệu T(w) là số các bước cơ bản của quá trình hoạt 
động của máy Turing T để đoán nhận từ w. Giả sử 0,1,….,k là dãy các hình trạng mà máy 
Turing T đoán nhận từ w, với k là hình trạng kết thúc, nghĩa là 01… k khi đó T(w) xác 
định như sau: T(w)=k, nếu T đoán nhận từ w, ngược lại T(w) không xác định. Hàm T(w) được 
gọi là hàm xác định thời gian tính toán. Việc xác định, đánh giá hàm T được gọi là đánh giá độ 
phức tạp thuật toán theo thời gian 
Định nghĩa 5.4.2. Giả sử w* và 0,1,.....,k là dãy hình trạng mà máy Turing T đoán 
nhận từ w, ở hình trạng i máy T sử dụng i ô nhớ trên băng khi đó ta xác định L(w) như sau: 
L(w)= max i i=1,2..k nếu T đoán nhận xâu w, không xác định nếu T không đoán nhận xâu w. 
Hàm L(w) được gọi là hàm xác định dung tích bộ nhớ. 
Việc xác định, đánh giá hàm L(w) được gọi là đánh giá độ phức tạp thuật toán theo dung 
tích bộ nhớ. 
Định nghĩa 5.4.3. Giả sử có hai hàm f: N  N và g:N  N , chúng ta nói rằng hàm f có 
cùng bậc với hàm g nếu tồn tại số k và số m sao cho sao cho f(n) kg(n) với mọi n  m kí hiệu 
f=O(g). 
Giả sử f là hàm xác định thời gian tính hoặc hoặc xác định dung tích bộ nhớ khi thực hiện 
một thuật toán nào đó và giả sử f=O(g), khi đó ta nói rằng thuật toán có độ phức tạp cùng bậc 
với g. Nếu g(n) là đa thức bậc n thì ta nói rằng bài toán có độ phức tạp đa thức. Nếu g(n) là hàm 
số mũ theo n thì ta nói rằng bài toán có độ phức tạp hàm số mũ... 
Ví dụ 5.4.4. Giả sử cho dãy số gồm k số n1,n2,...,nk , hãy sắp xếp dãy số theo thứ tự không 
giảm theo thuật toán nổi bọt. Theo thuật toán này chúng ta thực hiện so sánh và đổi chỗ hai 
phần tử đứng cạnh nhau nếu số đứng trước lớn hơn số đứng sau. Nếu coi thao tác cơ bản ở đây là 
phép so sánh thì lần thứ nhất thực hiện (k-1) phép so sánh và phần tử lớn nhất được đặt ở cuối 
dãy,lần thứ 2 cần k-2.....Số phép so sánh để sắp xếp dãy số gồm k phần tử là (k-1)+(k-
1)+....+1=k(k-1)/2. Từ đây suy ra độ phức tạp của thuật trên là O(k2). 
 Bài tập 
1. Hãy xác định các thành phần của các máy hữu hạn trạng thái M=(S, X, Y, , , s0), khi biết 
biểu diễn đồ thị của chúng: 
 a) 
b) 
c) 
2. Mạch tuần tự theo sơ đồ dưới đây là mạch flip-flop 
Giả sử thoạt đầu x1=1, x2=1 và y=0 hãy xác định giá trị của a,b và c. 
q0 q1 
b/1 
a/1 b/1 
a/0 
A B 
D C 
b/0 
a/0 
a/0 
b/1 b/0 
a/1 
b/0 
a/0 
y x2 
x1 
b 
a 
c 
A B 
D C 
a/1 
c/2 a/0 
b/0 
a/2 
b/0 
b/1 b/2 
c/2 
a/2 
c/0 
c/0 
3. Hãy chỉ ra rằng mỗi máy hữu hạn trạng thái cho dưới dạng các sơ đồ dưới đây là một automat 
hữu hạn trạng thái và hãy vẽ lại sơ đồ của các automat tương ứng 
4. Cho L là tập hữu hạn các xâu sinh ra từ tập a,b chỉ ra rằng tồn tại automat hữu hạn đoán 
nhận tập L. 
5. Hãy thiết kế automat hữu hạn trạng thái chỉ đoán nhận các xâu sinh ra từ tập a,b nhưng 
không chưa kí tự a. 
6. Hãy chỉ ra rằng một xâu  bất kỳ sinh từ tập a,b chấp nhận bởi automat cho ở hình dưới đây 
khi và chỉ khi  có hai kí tự cuối là ‘bb’ 
7. Hãy xác định bảng hàm chuyển trạng thái cho các automat không tất định ở dạng sơ đồ hình 
dưới đây: 
8. Hãy chỉ ra các văn phạm sau đây thuộc loại nào ? 
a/ T=a,b;N=*,A;* là kí tự bắt đầu. Tập P gồm các dẫn xuất : 
q0 
B A B 
q1 
C 
a) 
b) 
b/1 
a/0 b/0 
b/0 a/0 
b/0 
a/1 
a/1 
q0 q1 q2 
b 
a 
a 
b 
b 
a 
A B C D 
A B 
C 
b a b 
b 
a 
b 
b 
a 
a b 
a 
b 
a) 
b) 
 *b*, *aA , Aa* , AbA , A a , *b 
b/ T=a,b,c; N=*,A,B ;* là kí tự bắt đầu. Tập P gồm các dẫn xuất : 
* AB , ABBA, A aA , BBb, A a, B b 
c/ T=a,b; N=*,A,B ;* là kí tự bắt đầu. Tập P gồm các dẫn xuất: 
* A, *AAB, Aa ABa ,Aaa , Bb ABb, ABABB, B b. 
9. Cho văn phạm sau : 
T=a,b,c; N=*,A,B,C,D,E ;* là kí tự bắt đầu. Tập P gồm các dẫn xuất: 
* aAB , * aB, AaAC, AaC ,BDc, Db, CDCE. 
 CEDE ,DE DC, CcDcc 
a/Cho biết G là văn phạm loại nào ? 
b/ Hãy chứng tỏ L(G)= anbncn n=1,2.... 
c/ Hãy viết văn phạm trên ở dạng BNF (Backur Naur Form) 
10. Hãy chỉ ra rằng văn phạm sinh G ra tập ngôn ngữ L(G)= anbnck n,k=1,2.... là ngôn ngữ phi 
ngữ cảnh (context-free language). 
11. Viết văn phạm G có tập T=a,b sao cho xâu L(G) có một trong các tính chất sau: 
a/ Bắt đầu bằng kí tự a 
b/ Kết thúc bằng hai kí tự ab 
c/ Kết thúc bằng hai kí tự ba 
d/ Không kết thúc bằng ab 
12. Giả sử G là văn phạm và  là xâu rỗng. Hãy chỉ ra rằng nếu G có các qui tắc dẫn xuất sau: 
A  , A B hoặc A  với A,BN, T* \, thì tồn tại văn phạm G’ chính qui sao cho 
L(G’)=L(G). 
13. Hãy xây dựng máy hữu hạn trạng thái thoả mãn các điều kiện sau: 
a/ Nhận dòng vào là dãy các bit 
b/ Dòng ra bằng 1 nếu trong dòng vào có số chữ số 1 là số chẵn, dòng ra bằng 0 trong 
trường hợp ngược lại. 
14. Hãy xây dựng máy hữu hạn trạng thái thoả mãn điều kiện sau: 
a/ Nhận dòng vào là dãy các bit 
b/ Dòng ra bằng 1 nếu trong dòng vào có k chữ số 1 , k là số chia hết cho 3 . dòng ra 
bằng 0 trong trường hợp ngược lại. 
15. Chứng minh rằng không có máy hữu hạn trạng thái có tính chất sau : 
a/ Nhận dòng vào là dãy các bít 
b/ Dòng ra là 1 khi dòng vào có số chữ số 1 bằng số chữ số 0, dòng ra bằng 0 trong 
trường hợp ngược lại 
16. Hãy xây dựng văn phạm G sao cho L(G)= a2n-1  n N . 
17. Hãy xây dựng văn phạm G sao cho L(G)= an b2m  n, m N . 
18. Cho văn phạm G= , N=A,B,k; T= a,b ; 
P : k bA B b A bAA 
 k aB A ak B aBB 
 A a B  bk 
áp dụng định lý 4.5.2 hãy chỉ ra số từ nhiều nhất cần phải duyệt để khẳng định L(G) là hữu hạn 
hay vô hạn ? 
19. Hãy xây dựng văn phạm G mà L(G) là tập các số thực. 
20. Hãy xây dựng văn phạm G mà L(G) là tập các biểu thức số học. 
21. Hãy xây dựng văn phạm G mà L(G) là tập các biểu thức logic. 
22. Hãy xây dựng văn phạm G mà L(G) là tập câu lệnh trong ngôn ngữ lập trình Pascal. 
23 . Cho văn phạm phi ngữ cảnh G=, trong đó N gồm n biến. Hãy chỉ ra số lớn 
nhất các cây dẫn xuất có độ dài đường đi không lớn hơn n+1.Biết rằng mọi vế phải của các quy 
tắc dẫn xuất trong P là xâu có độ dài không lớn hơn m, 
24 . Cho văn phạm phi ngữ cảnh G ở dạng chuẩn Chomsky, giả sử wL(G) và k * w là dẫn 
xuất gồm p bước, khi đó w là xâu có dài bao nhiêu? 
25 . Cho G = 
 N={k}, T={p, [,],~, } 
 p: k  p 
 S  S 
 S  [S  S] 
Hãy chỉ ra dạng tổng quát của L(G)? 
26. Chứng minh rằng mọi văn phạm phi ngữ cảnh đều có thể sinh ra bởi văn phạm mà mỗi qui 
tắc dẫn xuất của nó có thể ở một trong các dạng sau: 
 A  a, A  aB, A  aBC. 
27. Giả sử L1, L2 là ngôn ngữ chính qui trên bảng chữ cái  , S là tập tất cả các xâu trên  
chứng minh rằng : 
 a/ S \ L1, L1 L2 là ngôn ngữ chính qui. 
 b/ L1 L2, L1+ , L1L2 là ngôn ngữ chính qui 
28. Hãy xây dựng automat hữu hạn không tiền định đoán nhận tất cả các xâu trên 0,1, bắt 
đầu bằng 01 và có chứa 110. 
Tài liệu tham khảo 
1. Kenneth H. Rosen. Toán rời rạc ứng dụng trong Tin học.- NXBKHKT, 2000 
2. Nguyễn Đức Nghĩa, Nguyễn Tô Thành. Toán rời rạc.- NXBGD, 1997. 
3. R. Johnsonbaugh. Discrete Mathematics.- Macmillan Pub., 1992. 
4. E. Goodaire, M. Parment. Discrete Mathematics with Graph Theory.- 1993