Một phân cấp của ngôn ngữ hình thức và automat

Phần I. mở đầu Phần II. Nội dung Phần III. Kết Luận Phần IV. Tài liệu tham khảo Mục lục Nội dung Trang Chương I: Một phân cấp của ngôn ngữ hình thức và automat Bây giờ chúng ta quay lại sự quan tâm chính, đó là nghiên cứu về ngôn ngữ hình thức. Mục đích trực tiếp của chúng ta là sẽ khảo sát ngôn ngữ liên hợp với máy Turing và một vài giới hạn của chúng. Bởi vì máy Turing có thể thực hiện một vài loại thuật toán tính toán nên chúng ta hy vọng tìm ra một họ ngôn ngữ kết hợp với chúng là khá rộng. Nó không chỉ bao gồm ngôn ngữ chính quy và phi ngữ cảnh mà còn nhiều loại khác như ví dụ chúng ta đã gặp ở ngoài những họ này. Câu hỏi đặt ra là liệu có một vài ngôn ngữ không được chấp nhận bởi một máy Turing. Ta sẽ trả lời câu hỏi này bằng sự chỉ ra rằng có nhiều ngôn ngữ hơn máy Turing, vì vậy sẽ có một vài ngôn ngữ mà không có máy Turing đoán nhận. Bằng chứng đưa ra là ngắn gọn và đơn giản nhưng không có cấu trúc và ít đi sâu vào bên trong của vấn đề. Đối với lý do này chúng ta sẽ thiết lập sự tồn tại của ngôn ngữ không được đoán nhận bởi máy Turing. Một con đường khác của người nghiên cứu sẽ là nhìn vào mối quan hệ giữa máy Turing và một loại nào đó của văn phạm và thiết lập một sự liên quan giữa những văn phạm này và ngôn ngữ chính quy và ngôn ngữ phi ngữ cảnh. Điều này dẫn đến tạo ra một hệ thống ngôn ngữ và qua đó dẫn đến một phương thức để phân loại họ ngôn ngữ. Một tập biểu đồ minh họa mối liên hệ giữa họ ngôn ngữ khác nhau một cách rõ ràng. Nhiều thảo luận trong chương này là chỉ đúng cho ngôn ngữ không bao gồm xâu rỗng. Hạn chế này xuất phát từ sự việc máy Turing, như chúng ta đã định nghĩa chúng, không thể chấp nhận xâu rỗng. Để tránh phải diễn đạt lại định nghĩa ta ngầm giả định rằng ngôn ngữ đã thảo luận ở trong chương này không chứa đựng λ. Nó là một vấn đề bình thường để nêu lại rõ ràng mọi thứ vì vậy λ là được gộp vào nhưng chúng ta sẽ để lại điều này cho đọc giả. 11.1 Đệ quy và ngôn ngữ đệ quy đếm được Chúng ta bắt đầu với một vài thuật ngữ đối với ngôn ngữ kết hợp với máy Turing. Trong việc làm cũng vậy, chúng ta cũng phải làm phân biệt tế nhị giữa ngôn ngữ cho cái mà có sự tồn tại một sự chấp nhận của máy Turing và ngôn ngữ cho cái mà có tồn tại một thuật toán. Bởi vì một máy Turing không cần thiết tạm dứng lại trên dữ liệu vào mà nó không chấp nhận, điều thứ nhất khong bao hàm điều thứ hai. Định nghĩa 11.1: Một ngôn ngữ L được coi là đệ quy đếm được nếu tồn tại một máy Turing đoán nhận nó. Địng nghĩa này không chỉ bao hàm có tồn tại một máy Turing M, such that, đối với mọi từ w ọ L: q0w Mx1qfx2 Trông đó: q là trạng thái kết thúc. Định nghĩa không nói gì về cái gì sẽ xảy ra đôiư với w không thuộc L: nó có thể làm cho máy dừng ở trong một trạngthái không kết thúc hoặc nó không bao giờ dừng và lặp vô tận. Chúng ta có thể cố gằng hơn và hỏi rằng: Máy sẽ cho chúng ta liệu có hoặc không một vài dữ liệu đã cho là trong ngôn ngữ của nó Định nghĩa 11.2: Một ngôn ngữ L trên bảng chữ ∑ được coi là đệ quy nếu có tồn tại một máy Turing M đoán nhận L và dừng ở mọi từ w trên ∑* . Trong những từ khác, một ngôn ngữ là đệ quy nếu và chỉ nếu tồn tại một quá trình tính toán hgoàn chỉnh cho nó. Nếu một ngôn ngữ là đệ quy, sẽ luôn tồn tại một cách xây dựng thủ tục đếm được. Giả thiết rằng M là một máy Turing cái mà đã xác định một thành phần ở trong một ngôn ngữ đếm được L. Đầu tiên chngs ta xây dựng một máy Turing khác, gọi là M’ , tạo ra tất cả các xâu ở trong ∑* theo một thứ tự thích hợp, chúng ta gọi là w1 w2 ... Khi các xâu này được tạo ra, chúng trở thành dữ liệu vào cho M, cái được sửa đổi vì vậy nó chỉ viết xâu ở trên băng của nó nếu chúng ở trong L. Có một thủ tục đến được cho mọi ngôn ngữ đệ quy đếm được không phải là dễ để thấy. Chúng ta không thể sử dụng những lý lẽ khi nó dừng lại, bởi vì nếu như một vài wj là không ở trong L, máy M, khi bắt đầu với wj trên băng của nó, có thể không bao giờ dừng và việc đó không bao giờ làm cho xâu ở trong L đi theo sau wj ở trong đếm được. Để chắc chắn rằng điều này không xảy ra, sự tính toán được thực hiện trog một cách khác. Đầu tiên chúng ta lấy M’ tạo ra w2 và để M thực hiện một di chuyển trên w2, theo sau bằng di chuyển thứ 2 ở trên w1. Sau đó, chúng ta tạo ra w3 và làm một bước trên w3, bước thư hai ở trên w2, bước thứ 3 ở trên w1, và vân vân. Thứ tự của sự thực hiện được miêu tả ở trong hình 11.1. Từ điều này, nó làm sáng tỏ rằng M sẽ không bao giờ đi vào một vòng lặp vô tận. Khi w ọ L được tạo bởi M’ và được chấp nhận bởi M trong một số bước hữu hạn, mọi xâu ở trong L là rốt cuộc được sản sinh bởi M. w1 w2 w3 w4 First move Second move Third move Hình 11.1 Dễ dàng nhận thấy rằng mọi ngôn ngữ cái mà tồn tại một thủ tục đếm được là đệ quy đếm được. Chúng ta so sánh đơn giản xâu dữ liệu vào đã cho ngước lại với xâu kế tiếp được tạo ra bởi thủ tục đếm được. Nếu w ọ L, chúng ta sẽ rốt cuộc thu được sự tương thích, và tiến trình có thể chấm dứt. Định nghĩa 11.1 và 11.2 cho chúng ta một ít nhìn nhận một cách tự nhiên của mỗi ngôn ngữ đệ quy hoặc đệ quy đếm được. Những định nghĩa này gán tên cho họ ngôn ngữ liên hợp với máy Turing, nhưng không để lại một cách tự nhiên của ngôn ngữ tiêu biểu trong họ này. Và chúng cũng không cho chúng ta biết nhiều về mối quan hệ giữa những ngôn ngữ hoặc sự liên quan đến các họ ngôn ngữ mà chúng ta đã gặp từ trước. Chúng ta ghi nhận ngay vẻ bề ngoài với câu hỏi như là: “Có ngôn ngữ là đệ quy đếm được nhưng không đệ quy hay không” và “Có ngôn ngôn ngữ, bằng cách này cách khác diễn tả được, đó là đếm được”. Lát sau chúng ta sẽ được cung cấp một vài câu trả lời, chúng ta sẽ không thể tạo ra nhiều ví dụ rõ ràng dứt khoát để minh họa cho những câu hỏi này, đặc biệ là cho câu hỏi thứ hai. Ngôn ngữ không phải là đệ quy đếm được Chúng ta có thể viết tắt sự tồn tại của ngôn ngữ là không đệ quy đếm được trong một cách khác. Một cách rất ngắn và sử dụng một rất cơ sở và tao nhã kết quả của toán học Định lý 11.1 Cho S là một tập vô hạn đếm được. Tập các tập con của nó là không đếm được. Chứng minh: Cho S={s1,s2,...}. Một phần tử bất kỳ t thuộc 2s là tương ứng với một xâu thuộc 0’s và 1’s, với 1 ở vị trí i nếu và chỉ nếu si là ở trong t. Ví dụ: , tập hợp {s2,s3,s6} là tương ứng với xâu 01100100...., khi đó { s1,s3,s5} là tương ứng với xâu10101... Rõ ràng, phần tử bất kỳ của 2s có thể được tương ứng với một xâu, và bất kỳ một xâu nào đều tương ứng với duy nhất một phần tử của 2s. Giả sử rằng 2s là đếm được , khi đó phần tử của nó có thể được viết ở trong một vài thứ tự, gọi t1,t2,... và chúng ta có thể đưa vào một bảng, như ở hình 11.2. Trong bảng này, lấy một phần tử ở trong đường chéo chính, và phần bù của mỗi mục, đó là, thay thế 0 bởi 1, và vice versa. Trong ví dụ ở hình 11.2, phần tử 1100..., vì vậy chúng ta lấy 0011..., là kết quả. Xâu mới tương ứng với một vài phần tử của 2s, gọi ti cho một i nào đó. Nhưng nó không phải là t1 bởi vì nó khác t1 qua s1. Đối với cùng lý do đó nó không thể là t2, t3 hoặc bất kỳ ti nào khác. Sự mâu thuẫn này tạo ra một bế tắc logic rằng có thể bị khác biệt chỉ vì đưa ra thừa nhận trong đó 2s là đếm được. Hình 11.2 t1 1 0 0 0 0 ... t2 1 1 0 0 0 ... t3 1 1 0 1 0 ... t4 1 1 0 0 1 ... ... ... Loại vấn đề này, bởi vì nó bao hàm một sự vận dụng yếu tố đường chéo của một bảng, được gọi là chéo hóa. Kỷ thuật được quy cho nhà toán học G.F.Canto, người đã sử dụng nó để chúng minh rằng tập hợp số thực là khong đếm được. Trong các chương sau, chúng ta sẽ thấy một vấn đề tương tự trong vài khung cảnh. Định lý 11.1 là chéo hóa ở trong dạng furest của nó. Như là một hệ quả trực tiếp của kết quả này, chúng ta có thể thấy rằng, trong một vài cách hiểu, có nhiều náy Turing hơn là ngôn ngữ, vì vậy phải có một vài ngôn ngữ là không đệ quy đếm được. Định lý 11.2: Đối với tập khác rỗng ∑, tồn tại một ngôn ngữ là không đệ quy đếm được. Chứng minh: Một ngôn ngữ là một tập con của ∑*, Vì thế tập tất cả ngôn ngữ là . Từ đó ∑* là không đếm được. Định lý 11.1 cho chúng ta rằng tập các tất cả các ngôn ngữ trên ∑ là không đếm được. Nhưng tập của tất cả máy Turing có thể đếm được. Điều nàu nói lên rằng phải có một vài ngôn ngữ trên ∑ là không đệ quy đếm được. Chứng minh này, mặc dù ngắn và đơn giản, là trong nhiều cách không làm vừa lòng. Nó là hoàn toàn không suy diễn và, khi nó cho chúng ta sự tồn tại của một vài ngôn ngữ là không đệ quy đếm được, nó không cho chúng ta cảm giác thoải mái đối với những ngôn ngữ này might look like. Trong các kết quả tiếp theo, chúng ta nghiên cứu phần kết luận rõ ràng hơn. Một ngôn ngữ là không đệ quy đếm được Vì mọi ngôn ngữ được mô tả trong một hướng thuật toán có thể được đoán nhận bởi một máy Turing và do đó là đệ quy đếm được, sự mô tả của một ngôn ngữ không đệ quy đếm được phải là gián tiếp. Tuy nhiên, nó là có thể. Vấn đề này bao gồm một sự biến thiên ở trong đề tài chéo hóa. Định lý 11.3 Tồn tại một ngôn ngữ đệ quy đếm được mà phần bù của nó là không đệ quy đếm được Chứng minh: Cho ∑ ={a}, và xem như tập hợp tất cả máy Turing với bảng chữ này. Từ tập là đếm được, chúng ta có thể liên hợp với M1, M2,... với các yếu t ố của nó. Đối với mỗi máy Turig Mi có một ngôn ngữ đệ quy đếm được liên hợp L(Mi). Ngược lại, đối với mỗi ngôn ngữ đệ quy đếm được trên ∑ , có một vài máy Turing đoán nhận nó. Bây giờ chúng ta xây dựng một ngôn ngữ L như sau. Đối với mỗi i>=0, xâu ai là ở trong L nếu và chỉ nếu ai thuộc L(Mi), và do đó ai thuộc L, phải là hoặc đúng hoặc sai. Sau đó chúng ta xem như phần bù của L là: ={ai: ai ọ L(Mi)} (11.1) Điều nầy được định nghĩa đúng nhưng, như chúng ta thấy,là không đệ quy đếm được. Chúng ta sẽ thấy điều này vì mâu thuẫn, bắt đầu từ sự cho rằng là đệ quy đếm được. Nếu như vậy thì sẽ có một vài máy Turing gọi là Mk, chẳng hạn =L(Mk) (11.2) Lưu ý xâu ak. Nó thuộc L hay . Giả sử rằng ak ọ. Vì (11.2) điều này cho thấy: ak ọ L(Mk). Nhưng (11.1) lại cho ta: ak ọ. Ngược lại, nếu chúng ta cho rằng ak là trong l thì ak ọ và (11.2) ngụ ý rằng ak L(Mk). Nhưng từ (11.1) chúng ta thấy rằng ak ọ. Mâu thuẫn là không thể tránh được, và chúng ta phải kết luận rằng sự giả định của chúng ta rằng là đệ quy đếm đượclà sai. Để hoàn thành chứng minh định lý như đã bắt đầu, chúng ta vẫn còn phải chỉ ra rằng L là đệ quy đếm được. Chúng ta có thể sử dụng cho điều đã biết thủ tục đếm được cho máy Turing. Cho ai, đầu tiên chúng ta tìm i bằng cách cộng các số của a’s. Sau đó chúng ta sử dụng thủ tục đếm được đối với máy Turing Mi. Cuói cùng chúng ta đưa ra sự mô tả của nó với ai cho một máy Turing phổ dụng Ma dựa theo hoạt động của M trên ai. Nếu ai ở trong L , sự tính toán mang ra bởi Ma rốt cuộc sẽ dừng. Vì vậy L là đệ quy đếm được. Chứng minh của định lý này bày tỏ một cách rõ ràng, từ (11.1), xác định đúng một ngôn ngữ là không đệ quy đếm được. Đây không phải để nói rằng có một cách giải thích dễ dàng, trực quan của ; nó sẽ là khó khăn để trình bày hơn một ít thành phần của ngôn ngữ. Tuy nhiên là có thể xác định. Một ngôn ngữ là đệ quy đếm được nhưng không là đệ quy. Tiếp theo, chúng ta thấy có một vài ngôn ngữ đệ quy đếm được nhưng không đệ quy. Trở lại, chnúg ta cần làm như vậy trong một cách theo đường vòng. Chúng ta bắt đầu bởi thiết lập một kết quả phụ. Định lý 11.4 Nếu một ngôn ngữ L và phần bù của nó là đệ quy đếm được thì của hai ngôn ngữ là đệ quy. Nếu L là đệ quy, thì cũng là đệ quy và do đó cả hai là đệ quy đếm được. Chứng minh: Nếu cả hải L và là đệ quy đếm được thì tồn tại một áy Turing M và M’ cung cấp một thủ tục đếm được tương ứng cho L và . Đầu tiên thủ tục w1, w2,... trong L, thứ hai w’1, w’2,... trong . Giả sử chúng ta cho bất kỳ wọ∑+ . Đầu tiên chúng ta cho M sinh ra w1 va so sánh với w. Nếu chúng là không giống nhau chúng ta co M’ sinh ra w’ và so anhs lại. Nếu chúng ta cần tiếp tục, chúng ta cho M sinh ra w2 rồi M’ sinh ra w’2 và cứ như thế. Bất kỳ wọ∑+ sẽ được sinh ra bởi M hoặc M’, vì vậy cuối cùng chúng ta sẽ thu được sự phù hợp. Nếu xâu phù hợp đó được tạo ra bởi M, w thuộc về L, ngược lại nó thuộc . Quá trình là một thành phần thuật toán cho cả hai L và . Vì vậy chúng là đệ quy. Đối với vấn đề ngược lại, giả sử L là đệ quy. Tồn tại một thành phần thuật toán cho nó. Nhưng điều này trở thành thành phần thuật toán cho bởi phần bù đơn giản kết luận của nó. Tuy nhiên là đệ quy. Từ đó các ngôn ngữ đệ quy là đệ quy đếm được, đó là điều phải chứng minh. Từ điều này, chúng ta kết luận trực tiếp rằng họ ngôn ngữ đệ quy đếm được và họ của ngôn ngữ đệ quy là không trùng nhau. Ngôn ngữ L ở trong định lý 11.3 ở trong họ đệ quy đếm được nhưng không đệ quy. Định lý 11.5 Tồn tại một ngôn ngữ đệ quy đếm được mà không đệ quy. Đó là, họ ngôn ngữ đệ quy là một tập con của họ ngôn ngữ đệ quy đếm được. Chứng minh: Hãy chú ý ngôn ngữ L trong định lý 11.3. Ngôn ngữ này là đệ quy đếm được nhưng phần bù của nó là không phải. Tuy nhiên, theo định lý 11.4, nó là không đệ quy, Cho chúng ta tìm kiếm ví dụ./ Chúng ta kết luận từ điều này là quả thực có định nghĩa ngôn ngữ cho cái mà không thể xây dựng mọt thành phần thuật toán. Câu hỏi: 1/ Nếu L là đệ quy, có nhất thiết rằng L+ là đệ quy hay không? 2/ Chọn một dạng mã hóa đặc biệt cho máy Turing, và với nó, hãy tìm một yếu tố của ngôn ngữ ở trong định lý 11.3 11.2 Văn phạm tổng quát. Để nghiên cứu sự liên quan giữa ngôn ngữ đệ quy đếm được và văn phạm, chúng ta trở lại sự định nghĩa tổng quát của một văn phạm trong chương 1. Trong định nghĩa 1.1, luật sinh được phép lấy từ mọi dạng, nhưng giới hạn khác nhau được làm muộn hơn để lấy một kiểu văn phạm đặc trưng. Nếu chúng ta đưa ra một đạng chung và không đặt ràng buộc, chúng ta sẽ được văn phạm tổng quát. Định nghĩa 11.3 Một văn phạm G=(V,T,S,P) được gọi là văn phạm tổng quát, nếu tất cả các luật sinh là có dạng u-> v. Trong đó u ọ (V T)+ và v ọ (V T)* Trong một văn phạm tổng quát, không cần thiết điều kiện ràng buộc trên các luật sinh. Bất kỳ số lượng biến và ký hiệu kết thúc có thể là bên trái hoặc bên phải, và có thể xuất hiện trong bất kỳ thứ tự nào. Chỉ có một ràng buộc nhỏ: λ không được phép ở phía bên trái của luật sinh. Như chúng ta thấy, vă phạm tổng quát là rộng hơn rất nhiều so với ngững dạng có ràng buộc như là văn phạm chính quy và phi ngữ cảnh mà chúng ta đã học trước đây. Sự thật, văn phạm tổng quát là tương ứng với họn ngôn ngữ lớn nhất chúng ta có thể hy vọng nhận ra bằng một máy tưởng tượng, đó là văn phạm tổng quát sinh ra chính xác họ ngôn ngữ đệ quy đếm được. Chúng ta thấy điều này ở trong hai phần: Thứ nhất là khá không phức tạp nhưng thứ hai bao gồm một cấu trúc dài dòng. Định lý 11.6 Bất kỳ một ngôn ngữ được sinh bởi văn phạm tổng quát là đệ quy đếm được. Chứng minh: Văn phạm trong kết quả định nghĩa một thủ tục liệt kê tất cả các xâu ở trong ngôn ngữ có hệ thống. Ví dụ, chnúg ta có thể liệt kê tất cả w trong L như sau: S w đó là, w được bắt nguồn từ một bước. Từ tập hữu hạn quy tắc của văn phạm sẽ có một số hữu hạn xâu. Tiếp theo chúng ta liệt kê tất cả w ở trong L đó có thể là được bắt nguồn trong hai bước. S x w và cứ như vậy. Chúng ta có thể giả sử dẫn suất này ở trên máy Turing và cho nên có một thủ tục đếm được cho ngôn ngữ. Do đó nó là đệ quy đếm được. Phần này tương ứng giữa ngôn ngữ đệ quy đếm được và văn phạm tổng quát là không ngạc nhiên. Văn phạm sinh ra một xâu bằng một thuật toán xử lý, vì vậy dẫn suất có thể được thực hiện trên máy Turing. Để chỉ ra vấn đề ngược lại, chúng ta mô tả bằng cách nào máy Turing có thể bắt chước bởi một tổng quát. Điều này là không phải dễ, minh chứng là sự dài dòng và kỷ thuật, mặc dù những ý tưởng cơ bản là đơn giản. Đối với lý do này, đầu tiên chúng ta mô tả những đường nét cơ bản cấu trúc bằng cái mà chúng ta tìm một văn phạm từ một máy Turing đã cho. Sau đó chúng ta minh họa nó với một ví dụ đơn giản. Cả đường nét cơ bản và ví dụ cụ thể phải được hiểu đúng trước khi tiến hành chứng minh và chi tiết của cấu trúc này. Chúng ta được cho một máy Turing M, và từ nó, chúng ta muốn xây dựng một văn phạm G, sao cho L(G)=L(M) . Điều này có nghĩa là chúng ta muốn có S Gw For exactly those for which q0w Mxqfy Ta hoàn thành điều này bằng cách xây dựng G vì vậy có một sự tương ứng giữa chuỗi mô tả ngay lập tức của M và những dạng câu nhận được từ G. Trên thực tế, vì M bắt đầu với w trong khi suy dẫn kết thúc tại đó, sự suy dẫn sẽ có kết quả là tính toán của M trong một thứ tự ngược lại. Cũng từ suy dẫn bắt đầu với S, chúng ta phải bắt đầu suy dẫn nó từ một câu từ đặc trưng trạng thái dừng xqfy, từ đây ta suy dẫn q0w. Cái gì chúng ta muốn là để xây dựng G, như sau: S xqfy q0w nếu và chỉ nếu w ọ L(M). Có một vài rắc rối trong này. Một là chúng ta thực sự muốn có S w, và chúng ta cần bỏ q0. Đối với điều này, ta đưa vào một ký hiệu đặc biệt #, cái mà có liên quan với một trạng thái thay đổi trong mô tả tức thời. Trong cách này nó có thể bị loại trừ ở bước cuối cùng. Hơn nữa sự rắc rối có thể đến từ có thể trống rỗng ở giữa mô tả tức thời, đây cũng phải loại trừ cuối cùng bằng văn phạm. Khi ta đặt tất cả những yêu cầu này lại với nhau, chúng ta tìm được văn phạm G sẽ phải có nhiều tập luật sinh: 1/ Một tập cho phép tất cả các suy dẫn có dạng S # xqfy đối với tất cả x,y và trạng thái kết thúc qf với cách trống ở bên trái và phải của # #xqfy 2/ Một tập cho phép suy dẫn # xqfy #q0w bất cứ khi nào q0w Mxqfy 3/ Một tập để loại trừ #q0 và các cách trống nếu có. Ví dụ dưới đây minh họa bằng cách nào có thể được thực hiện trong một số chi tiết. Ví dụ 11.1 Cho M =(Q,,,q0,□,F) là một máy Turing với Q={q0,q1} ={0,1,□} ={0,1} F={q1} and δ(q0,0) = (q0 , 0 , R), δ(q0,□) = (q1 , □ , L), Máy này đoán nhận ngôn ngữ L(00*). Tiếp theo sự gợi ý làm, ta tìm tất cả các yêu cầu được tiếp nhận bởi một văn phạm với V={ □ , #, q0 , q1 , S, A} T={0,1} Tập con thứ nhất của luật sinh là S -> □S|S□|#A A -> 0A|1A|A0|A1|q1 Dễ dàng nhận thấy rằng chúng ta có thể dùng những luật sinh này để tạo ra các xâu # xqfy với x,y ọ {0,1}*, đi trước và theo sau bởi một số tùy ý cách trống. Tập thứ hai của luật sinh là 0q0 -> q0 0 q10□ -> 0q0□ q11□ -> 1q0□ q1□ □ -> □q0□ Những luật sinh này phản ánh sự thay đổi tạo ra trong mô tả tức thời bởi định nghĩa δ . Ví dụ, xâu con q00 thay thế 0q0 khi ánh xạ chuyển δ(q0,0) = (q0 , 0 , R) được sử dụng. Một vài trường hợp test phải thuyết phục bạn rằng luật làm khả năng dẫn xuất x y, bất cứ khi nào y x Cuối cùng, tập cuối: #q0 -> λ □ -> λ là đủ để loại bỏ #q0 và các cách trống Bây giờ hãy nhìn vào quá trình đoàn nhận xâu 00 q000 0q0 00q0□ 0q10□ Một suy dẫn tương ứng với G của xâu trên là: S S□ #A□ #0A□ #0A0□ #0q10□ #00q0□ #0q00□ #q000□#q00000 Bỏ qua những dấu đặc biệt và cách trống, ta thấy rằng phần của suy dẫn là cái chúng ta đã xác nhận, chuỗi của các mô tả tức thời của máy Turing trong một thứ tự đảo ngược. Ví dụ này cho thấy văn phạm chúng ta làm việc, nhưng không nói rằng nó đến từ đâu, Thực tế kết quả là một ứng dụng của một cấu trúc chung, cái mà bây giờ chúng ta đưa ra. Định lý 11.7 Đối với mọi ngôn ngữ đệ quy đếm được L, tồn tại một văn phạm tổng quát G sau cho L=L(G). Chứng minh: Nếu L là đệ quy đếm được thì tồn tại một máy Turing M=(Q,,,q0,□,F) sao cho: q0w Mx1qfx2 với mọi w ọ L Như đã đề cập, ta xây dựng một văn phạm sao cho có thể tạo ra khi cảm nhận các dạng giới hạn của chuỗi mô tả tức thời trong tình toán này. chúng ta cũng muốn văn phạm đầu tiên nhận được từ hình trạng kết thúc, và tại thời điểm kết thúc, để loại trừ tất cả các ký hiệu thừa từ w. Tất cả điều này có thể được làm bằng cách lấy một văn phạm với T = và V={- } Q {#} {S,A} với S và A là ký hiệu không ở trong Q {#} Ta bắt đầu xây dựng P bằng cách đặt vào nó những luật đủ để cho phép các suy dẫn S □ ... □#xqfy□ ... □ với tất cả x,y trong {-{□}}* và tất cả qf ọ F. Điều này có thể đạt được, ví dụ: S -> □ S | S□|#A và A -> aA | Aa | q với mọi a ọ {-{□}} và q ọ F. Tiếp theo những sản phẩm dược sử dụng đi từ #xqfy đến q0w. Đối vpới mỗi ánh xạ chuyển của M bao gồm a,b ọ của dạng δ(qi, a) = (qj , b , R) chúng ta thêm vào P một suy dẫn tương ứng bqj -> qia (11.4) Lý do của điều này là, ở vế phải, xâu con qia của mô tả tức thì được thay thế bởi bqj. Cũng như vậy, đối với mỗi δ(qi, a) = (qj , b , L) chúng ta thêm vào P một luật qjcb -> cqia với mọi cọ . Trở lại, chúng ta làm điều này bởi vì, trong sự chuyển dịch này, xâu con cqia được thay thế bởi qjcb dù c là một ký hiệu nào đều là nguồn gốc để ngay lập tức ròi khỏi đầu đọc ghi. Cuối cùng , để loại bỏ #, q0 các ký tự trống thừa ta thêm vào suy dẫn #q0 -> λ (11.6) □ -> λ (11.7) Bây giờ suy nghĩ với mọi w trong L(M), sao cho →―׀ q0w ׀― xqfy với qf ọ F. Chúng ta có thể giả sử đúng với không mất đi của sự tạo ra x và y khong chứa một ký tự trrống. Ta mô phỏng sự tính toán này , dùng G để thu được chuỗi dạng: S □ ... □#xqfy□ ... □ Điieù này có thể luôn luôn được thực hiện, từ S có thể suy ra các xâu có dạng này. Tiếp theo ta cần chỉ ra rằng: □ ... □#xqfy□ ... □ □ ... □#q0w□ ... □ đó là, chúng ta lấy một dẫn suất tạo ra dịch chuyển của máy Turing ở trong thứ tự ngược lại. Để thấy điều này , ta nhìn vào hai hình trạng liên tiếp nhau của M a1...anqib1b2...bm ׀― a1...qj an cb2...bm (11.8) xuất phát từ một áp dụng của δ(qi, b1) = (qj, c , L) Nếu như vế phải của (11.8) là một dạng sentential của G thì bên trái cũng vậy, từ việc xây dựng G có một quy tắc: qjanc → anqib1 Lập luận tương tự đối với dịch chuyển sang phải của M a1...anqib1b2...bm ׀― a1...ancqj b2...bm (11.9) có thể xuất phát từ một luật chuyển: δ(qi, b1) = (qj, c , R) (11.10) Nhưng với (11.4), G có một quy tắc: cqj -> qib1 vì vậy: a1...ancqj b2...bm ׀― a1...anqib1b2...bm (11.11) Từ sự nghiên cứu này nó cho phép từ một lập luận quy nạp rằng nếu #q0w ׀― #xqfy thì: □ ... □#xqfy□ ... □ □ ... □#q0w□ ... □ Vì vậy, chúng ta có thể dùng G để làm một drivation S □ ... □#xqfy□ ... □ □ ... □#q0w□ ... □ và dùng luật cuối cùng (11.5) và (11.6) để gở bỏ #q0 và ký tự trống S w Như vậy, chúng ta đã chỉ ra rằng với mọi w được đoán nhận bởi M có thể được tạo ra bởi G. Để hoàn thành chứng minh này chúng ta phải chỉ ra vấn đề ngược lại và chứng tỏ rằng S w nghĩa là q0w ׀― xqfy Một xem xét cẩn thận của luật chuyển chỉ ra rằng nguồn gốc của w phải xuất phát theo con đường: S □ ... □#xqfy□ ... □ □ ... □#q0w□ ... □ w Vì thế xqfy q0w , và tất cả chúng ta cần chỉ ra là: xqfy q0w nghĩa là q0w ׀― xqfy Giả sử rằng: (11.11) là một bước ở trong dãy biến đổi của w và vế phải tương ứng với một hình trạng của M. Từ đó một bước ở trong dãy biến đổi phải được thực hiện với quy tắc: cqj -> qib1 M phải có một luật chuyển của dạng (11.10) và chuyển dịch (11.9) là có thể được. từ đó q0w là trạng thái ban đầu khi M đoán nhận w, chúng ta có thể dùng phương pháp quy nạp để chỉ ra rằng (11.12) là đúng Hai định lý này chứng minh cái chúng ta đặt ra để thực hiện. Chúng chỉ ra rằng họ ngôn ngữ liên hợp với văn phạm tổng quát là trùng với họ ngôn ngữ đệ quy đếm được. Bài tập 1/ Trong một vài nguyên bản, sự định nghĩa của một văn phạm tổng quát cần phải có vế trái của bất kỳ quy tắc là một phần tử của (T V)* V(V)* ; đó là, nó chứa ít nhất một biến. Hãy chỉ ra sự thu hẹp này hoặc làm tăng hoặc giảm năng lực của văn phạm. 2/ Xem xét một biến đổi ở trên văn phạm tại thời điểm bắt đầu đối với mọi dãy biến đổi có thể là một tập hữu hạn xâu, hơn là một biến đơn ... 3/ Trong ví dụ 11.1, chứg minh rằng văn phạm có cấu trúc không thể sinh ra bất kỳ một câu với 1’s trong nó. 4/ Đưa ra chi tiết của phần thứ hai của chứng minh của định lý 11.7, chỉ ra rằng S w nghĩa là q0w ׀― xqfy 5/ Xây dựng một máy Turing đoán nhận ngôn ngữ L(01(01)*), sau đó tìm một văn phạm tổng quát để nó sử dụng cấu trúc ở trong định lý 11.7. Đưa ra một dãy biến đổi ch 0101 sử dụng văn phạm tìm được. 6/ Chỉ ra rằng mọi ngôn ngữ tổng quát có tồn tại một văn phạm tổng quát tương đương, mà tất cả quy tắc có dạng u → v với u, v ọ (V T)* và |u| |v| hoặc A → λ với A ọ V 7/ hãy chỉ ra rằng kết luận của bài tập 6 vẫn đúng nếu chúng ta thêm điều kiện u| 2 và |v| 2 8/ Bằng một ví dụ hãy chỉ ra tại sao một số cơ chế để điều khiển loại bỏ q0, chẳng hạn # đã sử dụng trong định lý 11.7 là cần thiết. 11.3 Văn phạm cảm ngữ cảnh và ngôn ngữ cảm ngữ cảnh Giữa giới hạn (thu hẹp), văn phạm phi ngữ cảnh và tổng quát, văn phạm không hạn chế, một khác biệt lớn của văn phạm “không giới hạn” có thể được định nghĩa. Không phải tất cả trường hợp mang lại một kết quả thú vị. ở giữa những cái đó, văn phạm cảm ngữ cảnh được chú ý đáng kể. Văn phạm này đã sinh ra ngôn ngữ liên hợp với một lớp giới hạn của máy Turing, LB automat,.. cái mà chúng ta đã giới thiệu trong mục 10.5 Định nghĩa 11.4 Một văn phạm G = (V,T,S,P) được gọi là cảm ngữ cảnh nếu tất cả các quy tắc của nó có dạng x → y với x, y ọ (V T)+ và |x| |y| (11.13) Định nghĩa trên có thể được phát biểu lại như sau: Một văn phạm G = (V,T,S,P) được gọi là cảm ngữ cảnh nếu tất cả các quy tắc của nó có dạng αAβ → αμβ với A ọ T, α, β, μ ọ (V T)+ và με Các văn phạm G = (V,T,S,P) mà quy tắc có dạng như trên và có thêm quy tắc S → ε nhưng S không xuất hiện ở vế phải của bất kỳ quy tắc nào cũng được xếp vào văn phạm cảm ngữ cảnh. Văn phạm cảm ngữ cảnh và LB Automat Theo thuật ngữ đề nghị, văn phạm cảm ngữ cảnh là liên hợp với một họ ngôn ngữ cùng tên. Định nghĩa 11.5 Một ngôn ngữ L được gọi là cảm ngữ cảnh nếu tồn tại một văn phạm cảm ngữ cảnh G, sao cho L=L(G) hoặc L=L(G) {λ} Trong định nghĩa này, ta đưa vào một xâu rỗng. Định nghĩa 11.4 nghĩa là không được phép có x → λ, vì vậy một văn phạm cảm ngữ cảnh có thể không bao giờ tạo ra một ngôn ngữ chứa một xâu rỗng. Hơn nữa mọi ngôn ngữ phi ngữ cảnh không có λ có thể được tạo ra bởi một trường hợp đặc biệt của văn phạm cảm ngữ cảnh, cho bởi một trong Chomsky hoặc Greibach mẫu thông thường, cả hai cái mà thỏa mãn điều kiện của định nghĩa 11.4. Bằng cách thêm vào xâu rỗng ở trong định nghĩa của một ngôn ngữ cảm ngữ cảnh (nhưng không ở trong văn phạm) ta có thể cho rằng họ ngôn ngữ phi ngữ cảnh là một tập con của họ ngôn ngữ cảm ngữ cảnh. Ví dụ 11.2 Ngôn ngữ L={anbncn: n1} là một văn phạm cảm ngữ cảnh, ta chỉ ra đây bằng một văn phạm cảm ngữ cảnh cho ngôn ngữ. Một ví dụ của nó là: S → abc|Aabc Ab → bA Ac → Bbcc bB → Bb aB →aa| aaA Ta có thể thấy cách chúng hoạt động bằng cách nhìn vào dãy biến dổi của a3b3c3 S aAbc abAc abBbcc aBbbcc aaAbbcc aabAbcc aabbAcc aabbBbccc aabBbbccc aaBbbbccc aaabbbccc Cách giải quyết một cách có kết quả sử dụng biến A và B như là trung gian. Một A là được tạo ra ở bên trái, chuyển sang bên phải để được ký tự c đầu tiên, rồi tạo ra tiếp b và c. Sau đó nó chuyển trung gian sang B và chuyển sang bên trái để tạo ra a. Tiến trình diễn ra tương tự một chương trình của máy Turing để đoán nhận ngôn ngữ L. Từ ngôn ngữ trong ví dụ trên là không phải phi ngữ ngữ cảnh , chúng ta thấy rằng họ của ngôn ngữ phi ngữ cảnh thật sự là một tập con của nhóm ngôn ngữ cảm ngữ cảnh. Ví dụ 11.2 cũng chỉ ra rằng nó không phải là một vấn đề dễ dàng để tìm ra một văn phạm cảm ngữ cảnh ngay cả khi ví dụ tương đối đơn giản. Thường thường cách giải quyết dễ nhất bằng việc bắt đầu với một chương trình máy Turing, sau đó tìm một văn phạm tương đương với nó. Một vài ví dụ sẽ chỉ ra rằng, bất cứ một ngôn ngữ cảm ngữ cảm ngữ cảnh nào, máy Turing tương ứng có thể đoán trước một không gian điều kiện, trong trường hợp đặc biệt nó có thể được xem như là một LB automat. Định lý 11.8 Đối với mọi ngôn ngữ cảm ngữ cảnh L không bao gồm λ , tồn tại LB automat M sao cho L=L(M). Chứng minh: Nếu L là ngôn cảm ngữ cảnh, thì tồn tại một văn phạm đối với L-{λ} , ta chỉ ra chuổi biến đổi trong văn phạm này có thể là dựa theo bởi một LB máy tự động . LB máy tự động sẽ có hai đường, thứ nhất chứa một xâu vào w, đường thứ hai chứa một dạng sentential chuyển hóa sử dụng gMột điểm mấu chốt của lập luận là không thể xảy ra dạng Sentential có thể có độ dài lớn hơn |w|. Một điểm chú ý khác là một máy tự động LB là sự định nghĩa không quyết định. Đây là sự cần thiết trong lập luận, từ đó chúng ta có thể cho rằng quy tắc có thể luôn luôn được đoán và không không phát sinh luân phiên phải được đeo đuổi. Tuy nhiên, sự tính toán mô tả trong định lý 11.6 có thể đưa ra không sử dụng không gian ngoại trừ bị chiếm giữ trước bởi w; đó là, nó có thể được làm bởi một LB máy tự động Định lý 11.9 Nếu một ngôn ngữ L được đoán nhận bởi một vài LB máy tự động M thì tồn tại một văn phạm cảm ngữ cảnh sinh ra L. Chứng minh:Việc xây dựng ở đây là tương tự ở định lý 11.7. Tất cả quy tắc trong định lý 11.7 là không rút gọn ngoại trừ q0 → λ và □ → λ ..... Mối quan hệ giữa ngôn ngữ đệ quy và cảm ngữ cảnh Định lý 11.9, cho chúng ta rằng mọi ngôn ngữ cảm ngữ cảnh là được đoán nhận bởi một vài máy Turing là tất nhiên là đệ quy đếm được. Định lý 11.10 tiếp theo rõ ràng từ đây Định lý 11.10 Mọi ngôn ngữ cảm ngữ cảnh là ngôn ngữ đệ quy. Chứng minh: Xem ngôn ngữ cảm ngữ cảnh L liên hợp với một văn phạm cảm ngữ cảnh và nhìn vào chuổi biến đổi của w. S x1 x2 ... xn w Không mất tính tổng quát, chúng ta có thể giả sử tất cả dạng sentential ở trong một chuổi biến đổi đơn lẻ là khác nhau: đó là xi xj với mọi i j. Vấn đề khó khăn của lập luận của ta là số bước ở trong mọi chuổi biến đổi là một hàm biên của |w|. Ta biết rằng: |xj| |xj-1| bởi vì là không rút gọn. Điều chúng ta cần để thâm vào là tồn tại m chỉ tùy thuộc vào G và w sao cho |xj| |xj-m| với mọi j, với m=m(|w|) là một hàm biên của |VT| và |w|. Sau này vì tính hữu hạn của |VT| nên chỉ có một số hữu hạn xâu có độ dài cho trước. tất nhiên độ dài của chuổi biến đổi của w ọ L là lớn nhất của |w|,m(|w|) Điều này cho chúng ta một thuật toán cho L. Chúng ta đánh dấu tất cả các chuổi biến đổi với đội dài xâu cho đến |w| m(|w|). Từ đó tập các quy tắc của G là hữu hạn, chỉ có một số hữu hạn quy tắc này. Nếu một quy tắc sinh ra w thì w ọ L, ngược lại thì w không thuộc L. Định lý 11.11 Tồn tại một ngôn ngữ đệ quy nhưng không phải là ngôn ngữ cảm ngữ cảnh Chứng minh: Xem tập tất cả văn phạm cảm ngữ cảnh trong T={a,b}. Ta có thể dùng một quy ước trong mỗi văn phạm có một biến tập hợp có dạng V={V0, V1, V2...} Mọi văn phạm cảm ngữ cảnh được chỉ ra bởi quy tắc của nó, ta có thể suy nghĩ và viết ra bằng xâu đơn x1 → y1 x2 → y2 ..... xm → ym Với các xâu này ta áp vào sự tương đồng: h(a)=010 h(b)=0120 h(→)=0130 h(;)=0140 h(Vi)=01i-50 Như vậy, một văn phạm cảm ngữ cảnh được tương ứng với duy nhất một xâu ở trong L(011*0)*). Hơn nữa, sự biểu diễn là có thể lật ngược trong nhìn nhận, cho một xâu bất kỳ, có nhiều nhất một văn phạm phi ngữ cảnh đúng với nó. Chúng ta hãy đưa vào một thứ tự thích hợp trên {0,1}, vì vậy ta có thể viết một xâu theo thứ tự w1 w2 v.v. Một xâu đã cho wj có thể không định nghĩa một văn phạm cảm ngữ cảnh,; Nếu nó định nghĩa được ta gọi văn phạm đó là Gj . Tiếp theo ta định nghĩa một ngôn ngữ L L={ wi, wi định nghĩa một văn phạm cảm ngữ cảnh Gi và wi L(Gi)} L được định nghĩa đúng là là đệ quy. Để thấy điều này, ta xây dựng một phần thuật toán. Cho wi, ta đánh dấu nó để thấy nếu nó định nghĩa một văn phạm cảm ngữ cảnh Gi. Nếu không thì wi L. Nếu một xâu định nghĩa một văn phạm thì L(Gi) là đệ quy, và ta có thể sử dụng phần thuật toán của định lý 11.10 để tìm ra nếu wi ọ L(Gi). Nếu wi L(Gi) thì wi ọ L Nhưng L không phải là ngôn ngữ cảm ngữ cảnh. Nếu L là cảm ngữ cảnh thì sẽ tồn tại một wj sao cho L=L(Gj), bằng sự định nghĩa wj L. Nhưng L=L(Gj), vì vậy ta có một mâu thuẫn. Đảo lại, nếu ta giả sử rằng wj L(Gj), thì với định nghĩa wj ọ L và ta có mâu thuấn thuấn khác. Vì thế ta kêt luận L không phải là ngôn ngữ cảm ngã cảnh. Kết quả của định lý 11.11 chỉ ra rằng automata LB là không mạnh hơn máy Turing, từ chổ chúng chỉ chấp nhận một tập con thích hợp của ngôn ngữ đệ quy. Đồng thời LB automat là mạnh hơn automat đẩy xuống. Ngôn ngữ phi ngữ cảnh được sinh ra bởi văn phạm phi ngữ cảnh là một tập con của ngôn ngữ cảm ngữ cảnh. Bằng các ví dụ khác nhau cho thấy, chúng là một tập con thực sự. Bởi vì thực chất sự tương đương của LB automat và ngôn ngữ cảm ngữ cảnh là một và automat đẩy xuống và ngôn ngữ phi ngữ cảnh cũng là một. Ta thấy rằng một ngôn ngữ được đoán nhận bởi automat đẩy xuống cũng được đoán nhận bởi một LB automat nhưng có nhiều ngôn ngữ được đoán nhận bởi LB automat nhưng không phải được đoán nhận bởi automat đẩy xuống. Bài tập 11.4 Sự phân cấp Chomsky Bây giờ chúng ta gặp phải một số nhóm ngôn ngữ, chúng là ngôn ngữ đệ quy đếm được (LRE), ngôn ngữ cảm ngữ cảnh (LCS), ngôn ngữ phi ngữ cảnh (LCF), và ngôn ngữ chính quy (LREG). Một cách thể hiện mối quan hệ giữa những nhóm này là bằng phân cấp Chomsky. Noam Chomsky, người tìm ra thuyết ngôn ngữ hình thức, cúng cấp một sự phân loại ban đầu thanh bốn loại ngôn ngữ, loại 0 đến loại 3. Thuật ngữ độc đáo này vẫn tồn tại và một sự tìm kiếm thường xuyên dính dáng đến nó, nhưng số loại là thực sự khác những cái tên đối với nhóm ngôn ngữ chúng ta đã học. Ngôn ngữ loại 0 được sinh ra bởi văn phạm không giới hạn, đó là ngôn ngữ đệ quy đếm được. Ngôn ngữ loại 1 gồm có ngôn ngữ cảm ngữ cảnh. Ngôn ngữ loại 2 là ngôn ngữ phi ngữ cảnh. Ngôn ngữ loại 3 là ngôn ngữ chính quy. Như chúng ta đã thấy, mỗi nhóm ngôn ngữ loại i là một tập con thực sự của nhóm ngôn ngữ loại i-1. Biểu đồ (hình 11.3) thể hiện mối quan hệ một cách rõ ràng. Hình 11.3 cho thấy sự độc đáo của phân cấp Chomsky. Chúng ta cũng gặp nhiều nhóm ngôn ngữ khác phủ hoàn toàn lên hình vẽ. Kể cả nhóm ngôn ngữ deterministic phi ngữ cảnh (LDCF) và đệ quy (LREC), chúng ta đi đến mở rộng phân cấp như hình 11.4 Những nhóm ngôn ngữ khác có thể được định nghĩa và vị trí của chúng ở trên biểu đồ đã học, mặc dù mối quan hệ của chúng không phải luôn luôn xếp lồng thứ tự vào nhau như hình 11.3 và 11.4. Trong một số trường hợp đặc biệt, mối quan hệ là không đựoc hiểu trọn vẹn. Ví dụ 11.3 Ta có đưa ra trước đây ngôn ngữ phi ngữ cảnh. L={w:na(w)=nb(w) } và chỉ ra rằng nó là detẻminític nhưng không tuyến tính. Mặt khác ngôn ngữ L={anbn}{ anb2n } là tuyến tính nhưng không là Deter. Điều này chỉ ra rằng mối quan hệ giữa ngôn ngữ chính quy, ngôn ngữ tuyến tính, ngôn ngữ deter, ngôn ngữ cảm ngữ cảnh và ngôn ngữ nondeter như hình 11.5 dưới đây. Hình 11.5 Ví dụ 11.4 Chúng ta đưa ra một khái niệm của một automat DLB ở trong bài tập 7, mục 10.4. Ta có thể đặt câu hỏi mà đã hỏi ở trong sự liên quan với automat: Luật gì NDT sử dụng ở đây? Không may, không có câu trả lời dễ dàng. Tại thời điểm này, không thẻe biết liệu nhóm ngôn ngữ được đoán nhận bởi automat DLB là một tập con thực sự của ngôn ngữ cảm ngữ cảnh hay không. Tổng kết lại, ta đã khám phá mối quan hệ giữa nhiều nhóm ngôn ngữ và automat liên hợp của chúng. Trong đó ta đã thiết lập một sự phân cấp của các ngôn ngữ và đã phân loại automat dựa vào khả năng đoán nhận ngôn ngữ của chúng. Máy Turing là mạnh hơn automat LB. Cuối của sự phân cấp là ngôn ngữ đoán nhận hữu hạn với cái mà chúng ta đẵ bắt đàu học.