Tài liệu Một số tính chất của ngôn ngữ chính quy

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN --------------- BÙI THỊ MAI MỘT SỐ TÍNH CHẤT CỦA NGÔN NGỮ CHÍNH QUY KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán ứng dụng HÀ NỘI – 2017 TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN --------------- BÙI THỊ MAI MỘT SỐ TÍNH CHẤT CỦA NGÔN NGỮ CHÍNH QUY KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán ứng dụng Người hướng dẫn khoa học TS. KIỀU VĂN HƯNG HÀ NỘI – 2017 LỜI CẢM ƠN Để hoàn thành khóa luận tốt nghiệp này, em xin bày tỏ lòng biết ơn chân thành tới các thầy giáo và cô giáo trong Khoa Toán – Trường Đại học Sư phạm Hà Nội 2, đã tận tình giúp đỡ chỉ bảo trong suốt thời gian em theo học tại khoa và trong thời gian làm khóa luận. Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới TS. Kiều Văn Hưng – người thầy đã trực tiếp hướng dẫn em, luôn tận tâm chỉ bảo và định hướng cho em trong suốt quá trình làm khóa luận để em có được kết quả như ngày hôm nay. Mặc dù đã có rất nhiều cố gắng, song thời gian và kinh nghiệm bản thân còn nhiều hạn chế nên khóa luận không thể tránh khỏi những thiếu sót rất mong được sự đóng góp ý kiến của các thầy cô giáo, các bạn sinh viên và bạn đọc. Em xin chân thành cảm ơn. Hà Nội,ngày 24 tháng 04 năm 2017 Sinh viên Bùi Thị Mai LỜI CAM ĐOAN Khóa luận này là kết quả nghiên cứu của bản thân em dưới sự hướng dẫn tận tình của thầy giáo TS.Kiều Văn Hưng. Trong khi nghiên cứu hoàn thành đề tài nghiên cứu này em đã tham khảo một số tài liệu đã ghi trong phần tài liệu tham khảo. Em xin khẳng định kết quả của đề tài “ Một số tính chất của ngôn ngữ chính quy” là kết quả của việc nghiên cứu , học tập và nỗ lực của bản thân, không có sự trùng lặp với các kết quả của đề tài khác. Nếu sai em xin chịu hoàn toàn trách nhiệm. Hà Nội,ngày 24 tháng 04 năm 2017 Sinh viên Bùi Thị Mai MỤC LỤC LỜI MỞ ĐẦU .........................................................................................1 CHƯƠNG 1. NGÔN NGỮ CHÍNH QUY VÀ BIỂU THỨC CHÍNH QUY .......................................................................................................3 1.1. Định nghĩa ngôn ngữ chính quy và biểu thức chính quy. .....................3 1.2. Sự liên hệ giữa otomat và ngôn ngữ chính quy ...................................6 1.3 Điều kiện cần của ngôn ngữ chính quy .............................................. 10 1.3.1 Otomat tối tiểu .............................................................................. 10 1.3.2. Điều kiện cần của ngôn ngữ chính quy .......................................... 12 CHƯƠNG 2. TÍNH CHẤT CỦA NGÔN NGỮ CHÍNH QUY ................. 17 2.1. Đóng đối với các phép toán tập hợp đơn giản ................................... 17 2.2. Đóng đối với các phép toán khác ..................................................... 19 KẾT LUẬN CHUNG ............................................................................ 22 TÀI LIỆU THAM KHẢO ...................................................................... 23 LỜI MỞ ĐẦU Ngôn ngữ là một phương tiện để giao tiếp, sự giao tiếp có thể hiểu là giao tiếp giữa con người với nhau, giao tiếp giữa người với máy hay giao tiếp giữa máy với máy. Nếu như ngôn ngữ mà con người có thể giao tiếp được với nhau được gọi là ngôn ngữ tự nhiên , thì ngôn ngữ mà chúng ta vẫn thường sử dụng để giao tiếp với máy, hay giữa máy với máy được gọi là ngôn ngữ hình thức. Con người muốn máy tính thực hiện công việc phải viết các yêu cầu đưa cho máy bằng ngôn ngữ máy hiểu được. Việc viết các yêu cầu như thế gọi là lập trình. Ngôn ngữ dùng để lập trình được gọi là ngôn ngữ lập trình. Các ngôn ngữ lập trình đều là ngôn ngữ hình thức. Trong đó, ngôn ngữ chính quy là một nội dung khá mới mẻ giúp chúng ta hiểu sâu hơn về cấu trúc ngôn ngữ lập trình, đặc biệt nội dung Một số tính chất của ngôn ngữ chính quy là một nội dung khá hay với em. Xuất phát từ sự yêu thích đối với chuyên ngành Toán Ứng dụng và lòng đam mê nghiên cứu khoa học, em đã chọn đề tài Một số tính chất của ngôn ngữ chính quy để làm nội dung nghiên cứu khóa luận tốt nghiệp. Khóa luận của em gồm 2 chương. Chương 1 : “ Ngôn ngữ chính quy và biểu thức chính quy ” sẽ định nghĩa các ngôn ngữ chính quy trực tiếp từ các khái niệm về ngôn ngữ. Đồng thời với các ngôn ngữ chính quy, chúng ta đưa ra khái niệm về biểu thức chính quy , là công cụ để biểu diễn các ngôn ngữ chính quy. Chương 2 : “ Tính chất của ngôn ngữ chính quy” nêu ra các ngôn ngữ chính quy và các ví dụ minh họa để chúng ta thấy rằng ngôn ngữ chính quy cũng có các tính chất đặc trưng. Tác giả luận văn chân thành cảm ơn TS.Kiều Văn Hưng đã tận tình hướng dẫn tác giả đọc các tài liệu và tập dượt nghiên cứu. 1 Tác giả chân thành cảm ơn các thầy cô giáo Khoa Toán trường Đại học Sư phạm Hà Nội 2 , đặc biệt là tổ Toán ứng dụng , đã tạo điều kiện thuận lợi cho tác giải trong quá trình học Đại học và thực hiện bản khóa luận này. 2 CHƯƠNG 1 NGÔN NGỮ CHÍNH QUY VÀ BIỂU THỨC CHÍNH QUY Trong chương này, chúng ta sẽ định nghĩa các ngôn ngữ chính quy trực tiếp từ các khái niệm về ngôn ngữ, ta cũng sẽ chỉ ra rằng các định nghĩa này là tương đương. Đồng thời với các ngôn ngữ chính quy, chúng ta đưa ra các khái niệm về biểu thức chính quy, là công cụ để biểu diễn ngôn ngữ chính quy. 1.1. Định nghĩa ngôn ngữ chính quy và biểu thức chính quy. Định nghĩa 1.1 Cho bảng chữ cái  = { a1 , a2 ,..., an }, khi đó ngôn ngữ chính quy (regular languages) được định nghĩa quy đệ như sau: +, Các ngôn ngữ  và {ai } ( i = 1, 2, …,n) được gọi là các ngôn ngữ chính quy trên bảng chữ cái . +, Nếu R và S là hai ngôn ngữ chính quy trên bảng chữ cái  thì R  S; R.S; R+(hay S+) là các ngôn ngữ chính quy trên bảng chữ cái . +, Không có các ngôn ngữ chính quy nào khác trên bảng chữ cái  ngoài các ngôn ngữ chính quy được định nghĩa như trên. Định lý 1.1 Mọi ngôn ngữ chính quy trên bảng chữ cái  đều nhận được từ các ngôn ngữ hữu hạn bằng cách áp dụng một số hữu hạn lần các phép toán hợp, nhân ghép và phép lặp. Để diễn đạt các ngôn ngữ chính quy ,ta đưa vào khái niệm biểu thức chính quy , được định nghĩa như sau: Định nghĩa 1.2 Cho bảng chữ cái  = { a1 , a2 ,..., an }, khi đó biểu thức chính quy được định nghĩa như sau: 3 1,  và a ( với a  ) là các biểu thức chính quy trên bảng chữ cái  biểu diễn ngôn ngữ  và ngôn ngữ {a}. 2, Nếu r và s là hai biểu thức chính quy biểu diễn các ngôn ngữ chính quy R và S trên bảng chữ cái  thì: +, r + s là biểu thức chính quy trên bảng chữ cái  biểu diễn ngôn ngữ R  S. +, r.s là biểu thức chính quy trên bảng chữ cái  biểu diễn ngôn ngữ R.S. +, r+ (hay s +) là biểu thức chính quy trên bảng chữ cái  biểu diễn ngôn ngữ R+ (hay R+). 3, Không có các biểu thức chính quy nào khác trên bảng chữ cái  ngoài các biểu thức chính quy được định nghĩa như trên. Chú ý: Trong biểu thức chính quy, ta có thể bỏ các dấu ngoặc và quy ước thứ tự thực hiện các phép tính là phép lặp , phép ghép, phép hợp. Chẳng hạn biểu thức chính quy ab *a + ba thay cho biểu thức (((a(b *))a)+(ba). Ngoài ra nếu không sợ nhầm lẫn ta có thể sử dụng kí hiệu a thay cho biểu thức chính quy a với mỗi a  . Định nghĩa 1.2 Hai biểu thức chính quy r và s gọi là tương đương, kí hiệu r = s, nếu chúng biểu diễn cùng một ngôn ngữ. Với r, s, t là các biểu thức chính quy trên bảng chữ cái  ta có các kết quả sau: 1, r + s = s + r 2, (r + s ) + t = r + (s + t ) 3, r + r = r’ 4, (rs)t = r(st) 5, r( s + t ) = rs + rt, (s + t)r = sr + tr 6, * = ε 4 7, (r*)* = r* 8, rr* + ε = r* 9, (r*s*)* = (r + s)* Định lí 1.3 Cho L là một ngôn ngữ trên bảng chữ cái . Khi đó L là một ngôn ngữ chính quy khi và chỉ khi tồn tại một biểu thức chính quy trên  biểu diễn L. Chứng minh: Giả sử tồn tại một biểu thức chính quy trên bảng chữ cái  = { a1 , a2 ,..., an } biểu diễn L. Theo định nghĩa biểu thức chính quy thì L là tập hợp được tạo thành từ các tập cơ sở {} , {ε} , { a1 } ,…, { an } bằng việc áp dụng một số hữu hạn các phép hợp, lặp, ghép. Vì các tập cơ sở trên là ngôn ngữ chính quy và hợp, ghép, lặp của một số hữu hạn của chúng cũng là ngôn ngữ chính quy . Do đó L là một ngôn ngữ chính quy. Giả sử L là một ngôn ngữ chính quy trên bảng chữ cái . Khi đó L = T(A), với A =< Q, , δ, q0, F >, ω  * là một otomat hữu hạn đơn định . Giả sử Q = { q1 , q2 ,..., qn } . Kí hiệu Ryk là tập hợp tất cả các từ mà dưới tác động của chúng, otomat A chuyển từ trạng thái qi đến qj , thêm vào đó các trạng thái mà A đi qua có chỉ số không vượt quá k. Trên đồ thị chuyển của A , Ryk là tập hợp các từ ứng với các đường đi từ qi đến qj không đi qua . Ví dụ 1.1 Xác định ngôn ngữ chính quy được biểu diễn bởi biểu thức r = ( 01* + 02)1. Ta có r = ( 01* + 02)1 = 01*1 + 021, vậy ngôn ngữ chính quy biểu diễn bởi r là L(r) = L(01*1 + 021) = L(01*1)  L(021) = { 01n , 021 | n  1 } 5 1.2. Sự liên hệ giữa otomat và ngôn ngữ chính quy Định lý 1.4 Nếu L là một ngôn ngữ chính quy thì tồn tại một otomat hữu hạn không đơn định A đoán nhận L, tức là L = T(A). Chứng minh : Giả sử L là ngôn ngữ sinh bởi văn phạm chính quy G = (, , S, P), tức là L = L(G). Xét otomat hữu hạn không đơn định A = trong đó: + Q =   {E}, với E là kí hiệu mới và E    + q0 = S + F = {E} nếu quy tắc S → ε P và F = {E, S} nếu S → ε  P + A,  a   ta đặt δ(A, a) = {B  | A → aB  P}  {E | A → a  P} và δ(E, a) = . Ta chứng minh L = T(A). +, Lấy ω  L: Nếu ω = ε : Trong văn phạm G có quy tắc S → ε  P, do đó S  F. Trong trường hợp này δ(S, ε) = {S} nên ε  T(A). Nếu ω = a1a2 ...an ≠ ε : Ta có suy dẫn S ├ a1 A1 ├ a1a2 A2 ├…├ a1a2 ...an1 An1 ├ a1...an1an . Do đó tồn tại dãy quy tắc S → a1 A1 , A1 → a2 A2 ,…, An1 → an trong P. từ định nghĩa của δ ta có A1   (S , a1 ) , A2   ( A1 , a2 ),…, An1   ( An2 , an1 ), E   ( An1an ). Như vậy ,E   (S, a1a2 ...an ) hay ω  T(A). Vậy L  T(A). +, Lấy ω  T(A): Nếu ω = ε: δ(S, ε)  F ≠  hay S  F, vậy có qui tắc S → ε  P ,do đó ε  L(G) Nếu ω = a1a2 ...an ≠ ε : δ(S, ε)  F ≠  với ω ≠ ε hay E  δ(S, ε), do đó tồn tại các trạng thái A1 , A2 ,..., An1   sao cho A1   (S, a1 ), A2   ( A1 , a2 ),…, An1   ( An2 , an1 ),E   ( An1an )Từ đó ta có S → a1 A1 , A1 → a2 A2 ,…, An 1 → an  P 6 hay trong G có một suy dẫn là S ├ a1 A1 ├ a1a2 A2 ├…├ a1a2 ...an1 An1 ├ a1...an1an = ω.Vì vậy ω  L. Hay T(A)  L. Vậy ta đã chứng minh được L =T(A), tức là tồn tại một otomat hữu hạn không đơn định đoán nhận L. Ví dụ 1.2 Cho ngôn ngữ L = { ωa b n ab| n ≥ 0, ω  {a, b}*}. Ta có L = L(G) trong đó G = <{a, b}, {S, A, B}, S, {S → aS, S → bS, S → aA, A → bA, A → aB, B → b}> là văn phạm chính quy. Xây dựng otomat hữu hạn không đơn định A = <{ S, A, B, E}, {a, b}, δ, S, {E}>, trong đó δ(S,a) = {S, A}, δ(S,b) = {S}, δ(A,a) = {B}, δ(A,b) = {A}, δ(B,a) =, δ(B,b) = {E}, δ(E,a) =  , δ(E,b) = . Đồ thị chuyển của A được cho trong hình 1.1. a b a b a S B A E b Hình 1.1. Đồ thị chuyển của otomat A Theo định lý trên, otomat A đoán nhận ngôn ngữ chính quy L, thật vậy ta có: T(A) = { ωa b n ab| n ≥ 0, ω  {a, b}*} = L Định lý 1.5 Nếu L là ngôn ngữ đoán nhận bởi một otomat hữu hạn đơn định thì L là một ngôn ngữ chính quy. Chứng minh : Giả sử L = T(M), với M = < Q, , δ, qo, F > là một otomat hữu hạn đơn 7 định. Xét văn phạm G = ( , Q, qo, P), trong đó P = {q →ap| δ(q,a) = p}  {q →a| δ(q,a) = p  F}. Khi đó G là một văn phạm chính quy. Ta chứng minh L(G) = L, với giả thiết ε  L. +, Lấy ω = a1a2 ...an  L(G), ω ≠ ε, trong G tồn tại suy dẫn q0 ╞ ω hay q 0 ├ a1q1 ├ a1a2 q2 ├ a1a2 ...an1qn1 Do đó q 0 → a1q1 , q0 , a1 ├ a1...an1an = ω. q1  a2 q2, q1  a2 q2,..., qn 1  an 1qn 1, qn 1  an ), p2 =  (q1 , a2 ) ,…, qn1 =  (qn2, an1 ), qn  F  P hay ta có p1 = δ( tức là  (q0 , )  qn  F hay ω T(A) = L. +, Lấy ω = a1a2 ...an  L, ω ≠ ε, khi đó tồn tại dãy trạng thái q1 , q2 ,..., qn sao cho  (q0 , a1 )  p1 , n (q1 , a2 )  q2 ,...,  (qn2 , an1 )  qn1,  (qn1, an )  qn  F. Do đó trong G có các quy tắc q0 → a1q1 , q1  a2 q2, q1  a2 q2,..., qn 1  an 1qn 1, qn 1  an  P, ta có suy dẫn trong G: q 0 ├ a1q1 ├ a1a2 q2 ├ a1a2 ...an1qn1 ├ a1...an1an = ω hay ω L(G). Trong trường hợp ε L, ta xây dựng G’ tương đương với G trong đó kí hiệu xuất phát không xuất hiện trong bất kỳ vế phải của quy tắc nào, đồng thời thêm vào G’ quy tắc q0   để nhận được văn phạm chính quy G’ sao cho L(G’) = L(G)  { ε}. Vậy ta luôn có L(G) = L. Vậy định lý được chứng minh. Ví dụ 1.3 Cho otomat hữu hạn đơn định A= <{ q0 , q1 , q2 }, {0,1},  , q0 ,{q2 } > trong đó  (q0 , 0)  q1 ,  (q1 , 0)  q2 ,  (q1,1)  q0 ,  (q2 ,1)  q0 . Đồ thị chuyển của A là: 0 q0 q1 1 0 1 Hình 1.2 Đồ thị chuyển của otomat A 8 q Dễ thấy rằng T(A) = { ω00  ω { 01, 001}*} là ngôn ngữ chính quy. Kết luận Từ các định lý trên ta có kết luận về sự liên hệ giữa otomat hữu hạn và ngôn ngữ chính quy như sau: +, Gọi D là lớp các ngôn ngữ được đoán nhận bởi otomat hữu hạn đơn định ,N là lớp các ngôn ngữ được đoán nhận bởi otomat hữu hạn không đơn định và R là lớp các ngôn ngữ chính quy. Định lý 1.4 cho biết R  N Định lý 1.5 cho biết D  R Vậy D = N = R +, Ngôn ngữ L là chính quy khi và chỉ khi: Tồn tại một biểu thức chính quy biểu diễn L Tồn tại một văn phạm chính quy sinh ngôn ngữ L Tồn tại một otomat hữu hạn đoán nhận L. Ví dụ 1.4 Với ngôn ngữ chính quy L = {01n, 021 n ≥ 1} ta có: Biểu thức chính quy biểu diễn L là r = 01*1 + 021 Văn phạm chính quy sinh ngôn ngữ L G = <{ 0,1,2}, {S, A, B, C}, S, {S→ 0A, A→ 1A, A→ 1, S→ 0B, B→ 2C, C→ 1}> Otomat hữu hạn A đoán nhận L có đồ thị chuyển là: 1 1 q1 q 0 q0 1 q4 q3 2 9 0 Hình 1.3 Đồ thị chuyển của otomat A 1.3 Điều kiện cần của ngôn ngữ chính quy Khi một ngôn ngữ được đoán nhận bởi một otomat hữu hạn , hoặc được sinh bởi một văn phạm chính quy, hoặc được xác định bởi một biểu thức chính quy thì nó là ngôn ngữ chính quy. Như vậy việc chứng minh một ngôn ngữ chính quy là khá dễ dàng bằng cách chỉ ra rằng nó được xác định bằng một trong những cách trên. Tuy nhiên để khẳng định một ngôn ngữ L không phải là ngôn ngữ chính quy thì lại không hề đơn giản. Dù ta không xây dựng được otomat hữu hạn, văn phạm chính quy hay biểu thức chính quy để xác định L, nhưng ta vẫn không thể kết luận ngôn ngữ này không phải là ngôn ngữ chính quy, bởi vì ta không thể khẳng định được rằng không tồn tại những văn phạm chính quy hay những otomat hữu hạn sinh ra L. Như vậy, cần có một tiêu chuẩn để căn cứ vào đó có thể kết luận một ngôn ngữ không phải là ngôn ngữ chính quy , tiêu chuẩn đó là điều kiện cần của ngôn ngữ chính quy. 1.3.1 Otomat tối tiểu Cùng một ngôn ngữ chính quy L có thể có nhiều otomat hữu hạn đoán nhận nó. Tuy nhiên, trong số đó, trước hết chúng ta quan tâm đến các otomat có số trạng thái ít nhất cùng đoán nhận ngôn ngữ L. Định nghĩa 1.3 Otomat có số trạng thái ít nhất trong các otomat hữu hạn cùng đoán nhận ngôn ngữ L được gọi là otomat tối tiểu của ngôn ngữ L. Nhận xét: Dễ thấy rằng với mỗi ngôn ngữ L, otomat tối tiểu của nó có thể không duy nhất. Ví dụ 1.5 Giả sử otomat M = , với + Q = { t0 , t1 , t2 , t3 } với t0  {q0}, t1 {q1}, t2 { q0, q1}, t3  10 +  (t0 , a)  t0 ,  (t0 , b)  t2 ,  (t1 , a)  t2 ,  (t1, b)  t3 ,  (t2 , a)  t2 ,  (t2 , b)  t2 ,  (t3 , a)  t3 ,  '(t3 , b)  t3 + F  {t1 , t2 } a a b t0 t b a b t T3 a b Hình 1.4 Đồ thị chuyển của M Otomat M là đơn định có 4 trạng thái và có đồ thị chuyển ở hình bên. Dễ thấy rằng otomat M đoán nhận ngôn ngữ : L = T(M) = {anb ω n ≥ 0, ω  {a, b}*} Nhìn vào đồ thị chuyển của M ta thấy ngay rằng không có đường đi nào từ t0 đến được đỉnh kết thúc t1 , vì vậy otomat M sẽ tương đương với otomat M’ có đồ thị chuyển như sau: a a b t0 t b Hình 1.5 Đồ thị chuyển của otomat tối tiểu M’ 11 Rõ ràng là otomat M’ cũng đoán nhận ngôn ngữ L = T(M’) = {anb ω n ≥ 0, ω  {a, b}*}, M’ chỉ có hai trạng thái và là otomat tối tiểu của ngôn ngữ L= {anb ω n ≥ 0, ω  {a, b}*} 1.3.2. Điều kiện cần của ngôn ngữ chính quy Định lý 1.6 Nếu L là ngôn ngữ chính quy thì tồn tại số nguyên dương n sao cho với mọi ω  L mà ω≥ n đều có thể phân tích được dưới dạng ω = uvw, ( với |v| ≥ 1 hay v ≠  ) mà với mọi chỉ số i =0, 1, 2, … ta có uviw  L. Chứng minh : Vì L là một ngôn ngữ chính quy, khi đó tồn tại 1 otomat hữu hạn đoán nhận nó. Giả sử L = T(A) , với A = là một otomat tối tiểu có n trạng thái, tức là |Q| = n. Ta chứng minh n là số tự nhiên cần tìm. Giải sử ω = a1a2 ...an  L với m ≥ n. Khi đó ta có  (q0 ,  )  F tức là q0 , q1 ,..., qm  Q sao cho  (qi 1 , ai )  qi , 1≤ i≤ m và q m  F. Do m ≥ n nên trong dãy q0 , q1 ,...., qm có ít nhất hai trạng thái trùng nhau, giả sử đó là qi  qk , i < k ≤ n, (với k là số nhỏ nhất mà ta có q i =qk) Đặt u = a1...ai , v = ai 1...ak , w = ak 1...am . Ta có  = uvw, |v| = | ai 1...ak | ≥ 1 (do i < k). Ngoài ra ta có : (q0, u) = q i = qk = (q0, uv), Nên (q0, u) = (q0, uv) = ((q0, u), v) = ((q0, uv), v) = (q0, uv2) Tương tự ta có (q0, u) = (q0, uv2) = ( (q0, u), v2) = ( (q0, uv), v2) = (q0, uv3) Tiếp tục ta được (q0, u) = (q0, uvi), i  N. Cuối cùng ta có (q0, uviw) = ((q0, uvi), w) = ((q0, uv), w) = (q0, uvw)  F Vậy uviw  L, i = 0, 1, 2… 12 Định lý được chứng minh. Ví dụ 1.6 : Chứng minh L = {an bn : n  0} là không chính quy. +, Giả sử L là chính quy, dễ thấy L vô hạn. Theo định lý 1.6 tồn tại số nguyên dương m. +, Chọn ω = am bm  L , | ω | = 2m ≥m. Theo định lý 1.6 tồn tại một cách phân tích ω thành bộ ba ω = uvw, trong đó | uv| ≤ m(1), |v| = k ≥ 1(2). Từ cách chọn ω có m kí hiệu a đi đầu, kết hợp với (1) suy ra uv chỉ chứa a, từ đây suy ra v cũng chỉ chứa a. Vậy v = ak . nk Xét ω1 = uviw với i = 0, ta có 0  a bn  L theo định lý trên, nhưng điều này mẫu thuẫn với định nghĩa của L. Vậy L là không chính quy. Nhận xét: +, Lý luận này có thể trực quan hóa như một trò chơi chúng ta đấu với một đối thủ. Mục đích của chúng ta là thắng ván chơi bằng cách tạo ra sự mâu thuẫn của định lý 1.6, trong khi đối thủ chặn đứng chúng ta. Có 4 bước đi trong trò chơi này như sau: +, Đối thủ lấy m. +, Với m đã cho chúng ta lấy một chuỗi ω  L thỏa mãn | ω | = ≥ m. +, Đối thủ chọn phân hoạch uvw thỏa mãn | uv| ≤ m, |v| = k ≥ 1. Chúng ta phải giả thiết rằng đối thủ chọn lựa làm sao cho chúng ta khó thắng ván chơi nhất. +, Chúng ta chọn i sao cho chuỗi được đẩy lên không thuộc L. +, Bước quyết định ở đây là bước 2. Trong khi chúng ta không thể ép buộc đối thủ lấy một phân hoạch cụ thể của chuỗi ω , chúng ta có thể chọn chuỗi ω sao cho đối thủ bị hạn chế nghiêm ngặt trong bước 3, ép buộc một sự lựa chọn 13 u, v, w sao cho cho phép chúng ta tạo ra một mâu thuẫn với định lý trên bước kế tiếp của chúng ta. Hệ quả 1.1 Cho A là otomat hữu hạn đơn định có n trạng thái và L là ngôn ngữ được đoán nhận bởi A. Khi đó L ≠  khi và chỉ khi    L sao cho | | < n. Chứng minh : Điều kiện đủ là hiển nhiên. Bây giờ cho L ≠ . Giả sử mọi từ trong L đều có độ dài ≥ n. Gọi  là từ có độ dài nhỏ nhất trong L, mà || ≥ n. Theo định lý 1.6 ta có  = uvw, trong đó |v| ≥ 1 và với mọi i = 0, 1, 2… ta có uviw  L. Với i = 0, uw  L mà |uw| < ||. Điều này mâu thuẫn với tính nhỏ nhất của ||. Vậy tồn tại   L sao cho | | < n. Nguyên lý 2. 1 ( Nguyên lý chuồng chim bồ câu) Nếu chúng ta đặt n vật thể vào trong m hộp và nếu n > m thì ít nhất có một hộp chứa nhiều hơn một vật thể. Ví dụ 1.7 Ngôn ngữ L = {an bn : n  0} có chính quy không ? Câu trả lời là không, chúng ta sẽ chứng tỏ bằng phương pháp phản chứng sau : Giả sử L là chính quy thì tồn tại dfa M = nào đó cho L. Xét  *(q0,ai) với i = 0, 1,2,…Vì có một số không giới hạn các I, nhưng chỉ có một số hữu hạn các trạng thái trong M, theo nguyên lý chuồng chim bồ câu thì phải có một trạng thái nào đó, chẳng hạn q, sao cho  *(q0, an) = q và  *(q0, am) = q, với n ≠ m. Nhưng vì chấp nhận anbn nên ta có  *(q, b n) = qj  F. Kết hợp với ở trên ta suy ra  *(q0, ambn) =  *(q, bn) = q j 14 Vì vậy M chấp nhận cả chuỗi ambn với n ≠ m. Điều này mâu thuẫn với định nghĩa của L, suy ra L không chính quy. Nhận xét Trong lý luận này nguyên lý chuồng chim bồ câu đơn giản phát biểu rằng một otomat hữu hạn có một bộ nhớ hữu hạn. Để chấp nhận tất cả các chuỗi anbn một otomat phải phân biệt giữa mọi tiếp đầu ngữ an và am. Nhưng vì chỉ có một số hữu hạn các trạng thái nội để thực hiện điều này nên phải có một n và một m nào đó mà đối với chúng otomat không thể phân biệt được. Hệ quả 1.2 Tồn tại một ngôn ngữ phi ngữ cảnh mà không được đoán nhận bởi bất kỳ otomat hữu hạn đơn định nào. Chứng minh Xét ngôn ngữ L = {anbn | n ≥ 1} trên bảng chữ cái  = {a, b}. Ta có L = L(G), trong đó G = < , {S}, S, S → ab}> là văn phạm phi ngữ cảnh. Giả sử L = T(A) với A = là một otomat hữu hạn đơn định. Với n đủ lớn, α = anbn có |α| ≥ |Q|. Ta có thể biểu diễn anbn = uvw, trong đó |v| ≥ 1, uviw L, i = 0,1,2…Ta hãy tập trung phân tích từ v và vi: +, Nếu v chỉ chứa a (|v|a > 0 và (|v|b = 0) thì với i đủ lớn |uviw|a > |uviw|b. +, Nếu v chỉ chứa b (|v|b > 0 và (|v|a = 0) thì với i đủ lớn |uviw|b > |uviw|a. +, Nếu |v|a > 0, |v|b > 0 thì với i = 2 ta có v = (ab)2 = abab tức là a và b xen kẽ nhau trong uviw, khi đó uviw không thể có dạng anbn. Cả 3 trường hợp đều mâu thuẫn với uviw  L. Vậy không tồn tại một otomat hữu hạn đơn định nào đoán nhận L, tức là L không phải là một ngôn ngữ chính quy. Hệ quả này là một ứng dụng điều kiện cần của ngôn ngữ chính quy, để chứng minh một ngôn ngữ không phải là chính quy nếu nó không thỏa mãn điều kiện này. 15