Giáo trình Toán rời rạc: Phần 2 - Đỗ Đức Giáo

Chia sẻ: Lê Na | Ngày: | Loại File: PDF | Số trang:218

Thêm vào BST

Báo xấu

230
lượt xem 51
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần 2 giáo trình "Toán rời rạc" sau đây gồm nội dung các chương: Chương 6 - Ôtômat hữu hạn đoán nhận ngôn ngữ chính quy, chương 7 - Ôtômat đẩy xuống đoán nhận ngôn ngữ phi ngữ cảnh, chương 8 - Lôgic toán, chương 9 - Đại số boole. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Toán rời rạc: Phần 2 - Đỗ Đức Giáo

Chương 6 ÔTÔMAT HỮU HẠN ĐOÁN NHẬN BIỂU THỨC CHỈNH QUY |1. ÔTÔMAT HỮU HẠN (FINITE AUTOMATA - FA) Ô t ô m a t hữu h ạ n có t h ể xem n h ư " m á y t r ừ u tượng" để đ o á n n h ậ n ngôn ngữ. C h ú n g ta sẽ t h ấ y r ằ n g láp n g ô n ngữ điíỢc đ o á n n h ậ n bởi ô t ô m a t h ữ u h ạ n là k h á đơn g i ộ n . đó c h í n h là lốp n g ô n ngữ c h í n h quỵ do các v ă n p h ạ m c h í n h quy sinh ra. 1.1. D i n h n g h ĩ a ô t ô m a t h ữ u h ạ n Đinh nghĩa ĩ: Ô t ô m a t hữu h ạ n là bộ M = . trong dó: ì - là t ậ p hợp hữu h ạ n k h á c rỗng các ký h i ệ u v à o . Q- là t ậ p hợp hữu h ạ n k h á c rỗng các t r ạ n g t h á i . q,j e Q được gọi là t r ạ n g t h á i ban đ ầ u . F c Q được gọi là t ậ p các t r ạ n g t h á i két t h ú c . 5- được gọi là h à m chuyên có dạng; 1. N ê n h à m chuyển là á n h xạ 5 : Q X ì —> Q. k h i đó M được gọi là ôtômat đơn định (Deterministic Finite Automata, v i ế t t ắ t là DFA). 240
2. Nếu h à m chuyển là ánh xạ ô: Q X ì -» 2 , khi đó M được Q gọi là ôtôtnat không đơn định (Nondeterministic Finite Automata, viết t ắ t NDFA). Ta có thể mô tả các bưốc làm việc của ôtômat hữu hạn M = khi cho xâu vào co = X! x x ... x 6 E* như 2 3 n sau: Xâu vào 0) X, x2 ... x _! n x n t Qo-> Khi bắt đầu làm việc máy ở trạng thái đầu q và đầu đọc 0 đang nhìn vào ô có ký hiệu X,. Tiếp theo máy chuyển từ trạng thái q đuối tác động của ký hiệu vào X i về trạng thái mới 0 ô(q .x,) = q, e Q và đầu đọc chuyển sang phải Ì ô, tức nhìn vào 0 ô có ký hiệu x . Sau đó ôtômat M l ạ i tiếp tậc chuyển từ trạng 2 thái q, nhờ hàm chuyển ô về trạng thái mói q = 5(q,, Xa) = 5(5(q . X,), x ) = 5(q . x , x ) e Q. 2 0 2 0 2 Quá trình đó sẽ tiếp tậc cho tới khi đầu đọc nhìn vào ký hiệu x„ với trạng thái của máy là q , = ô(q,„ X1X2... x„.i). n Hàm chuyển l ạ i đưa máy từ trạng thái q _| đuối tác động n của x„ về trạng thái q,,= 5(q„.ị, x„) = ô(q , X j X ... x„) € Q. Khi đó 0 2 ôtômat dừng l ạ i . Nếu q„ 6 F thì ta nói rằng ôtômat đã đoán nhận xâu co. Trong trường hợp ngược lại thì nói rằng ôtômat không đoản nhận xâu co. Tập L(M) ={co/ co e ì* mà 5(q , co) e F} được gọi là ngôn ngữ 0 được đoán nhận bởi ôtômat M. Tập trạng thái Q trong quá trình tính toán được coi như là bộ nhớ của một ôtômat. Vì Q là hữu hạn nên M được gọi là ôtômat hữu hạn. 241
1.2. Phương pháp biêu d i ê n ô t ô m a t hữu hạn Cho ôtômat thực chất là cho hàm chuyển của nó. Hàm chuyển có thể cho đuối dạng bảng chuyển, hoặc cho đuối dạng đồ thị. a) Phương pháp cho bảng chuyên: Trạng Ký hiệu vào thái Xi x x„ 2 qi ô(q,, X,) ô(q,. x ) 2 • ... S(q,, x„) q 2 -ỉ ô(q . 2 Xi) 5(q . x ) 2 2 ... ô(q . x ) 2 n q 3 S(q . X,) 3 S(q , x 3 2 • •• 5(q . x ) 3 n Qk 5(q , X,) k ỗ(q . x ) k 2 ... 5(q . x„) k Nếu M = là ôtômat đơn định thì ô(q,. Xj) là 0 một trạng thái trong Q, còn nếu nó là ôtômat không đơn định thì ô(q Xj) là một tập các trạng thái trong Q. r Ví dụ 1: Cho ôtômat đơn định M = vối ì ={0. 1}, Q={q,,. q,. q . q.j}. F = {q,,}. trạng thái ban đầu là q,„ còn 2 hàm chuyển cho đuối dạng bảng: Trạng Ký hiệu vào thái 0 1 q.j Q2 Qi q. q 2 Qo q.ì q 3 242
Cho xâu vào (0= 110101. Quá trình hoạt động của ôtômat M diễn ra theo quá trình sau: ô(q,;„ 1) = qi. ô(q,. 1) = q,j, ô(q,„ 0) = q , 2 ỗ(q . 1) = q . 2 5(q,. 0) = q,. 3 5(q„ 1) = q„ e F. Diều đó chứng tỏ ôtômat M đoán nhận xâu 0) = 110101. Dãy trạng thái của M khi cho xâu vào co = 110101 được biểu diễn như sau: co = Ì Ì 0 Ì 0 Ì q - » q, -> q,, -> 0 q-2 -> q -> q. -> 3 q,.i Hay quá trình trên tường đương với diễn đạt sau: S(q , 110101) 0 = Ỗ(ô(q ,. 1), 10101) = S(q„ 10101) = L 5(5(q,. 1). 0101) = 5(q„. 0101) = 5(5(q„. 0).101) = 5(q. .101) 2 = 5(ỗ(q . 1). OI) = ô(q . OI) = S(ô(q . 0). 1) 2 3 3 = 5(q,. 1) = q„ £ F. Ví dụ 2: Cho ôtômat đơn định M = vối ì = {0.1'. Q - {q,„ q,. q . q.í). q,, là trạng thái ban đầu. còn 2 F = { q j là tập trạng thái kết thúc. Hàm chuyển trạng thái được cho b i bảng sau: Trạng thái Ký hiệu vào 0 1 q.. Qi q* Q| q 3 q.. q-2 qo q.3 q 3 q 3 q;i 243
Giả sử xét các xâu co, = 10110. co = no, C0 = 10011. Hỏi 2 3 rằng ôtômat M có đoán nhận các xâu đó hav không ? a. Dãy trạng thái của ôtômat M khi cho CO] vào là: co, = Ì 0 Ì Ì 0 q -» q -> q„ -> q -> q -> q e F. 0 2 2 3 3 Do đó ôtômat M đoán nhận xâu CO) = 10110. b. Với xâu vào K>2 = no. k h i đó dãy trạng thái M đối vối xâu vào co sẽ là: 2 ©2=1 Ì 0 t t t t q , -» q -> q -> q e F : 2 3 3 và ôtômat cĩing đoán nhận xâu C 0 2 = no. c. Vối xâu vào Cù 3 = 10011. Ta lập dãy trạng thái của ôtômat M đối vói co như sau: 3 C0 3 = 1 0 0 1 1 q,,-> q -> q,, -> q, -> q -> q « F 2 0 2 nên máy M không đoán nhận xâu vào 0 ) 3 = 10011. Từ các ví dụ trên ta thấy quá trình đoán nhận một xâu nào đó đối vối ôtômat M đơn định là quá trình biên đoi trạng thái cuối cùng của ôtômat có phải là trạng thái kết thúc hay không. Ta có thể mô tả quá trình đoán nhận xâu vào của ôtômat đơn định M như sau: Thuật toán mô phỏng ôtômat hữu hạn đoán nhận xâu vào: Đầu vào: - Một xâu co. kết thúc b i ký hiệu hết File là eof. 244
- M ộ t ô t ô m a t h ữ u h ạ n M với t r ạ n g t h á i ban đ ầ u q,i và t ậ p t r ạ n g t h á i k é t t h ú c là F. Đ ầ u ra: " Đ ú n g " n ế u M đ o á n n h ậ n x â u co. "Sai" n ế u M k h ô n g đ o á n n h ậ n x â u co. Thuật toán: Begin S:= q ;0 C:=ký hiệu tiếp theo ; While c eof do begin S:= 5(S. C); C:= ký hiệu tiếp theo; end; if s in F return (True) else return (False); End. Ví dụ 3: Cho ô t ô m a t k h ô n g đơn định M = v ố i ì ={0.1 J. Q-{q,,. q,. q . q.í). q.-i là t r ạ n g t h á i ban đ ầ u , 2 F - ÍQ2- q-)} là t ậ p hợp t r ạ n g t h á i k é t t h ú c . Q H à m c h u y ê n ô : Q X £ —>• 2 được cho ỏ bảng sau: Trạng thái Ký h i ệ u vào 0 1 q„ {q,. q,! íq... Q1 ỉ q. 0 q 2 q 2 q* q 2 q 3 0 Q4 q.3 245
Sau đ â y là q u á t r ì n h đ o á n n h ậ n một x â u v à o của m á y M . Vì đ ố i với ô t ô m a t k h ô n g đơn định t h ì h à m chuyển 5 k h i m á y ở t r ạ n g t h á i q và t í n h i ệ u a là ô(q,a) c Q n ê n sẽ x u ấ t h i ệ n t ì n h t r ạ n g rẽ n h á n h . Đ ể cho t i ệ n ta có t h ể l ậ p d ã y t r ạ n g t h á i của m á y ứng v ố i x â u v à o d ư ớ i d ạ n g cây m à gốc của nó là t r ạ n g t h á i ban đ ầ u q„. Trong c â y n à y n ế u có m ộ t đường đi t ừ gốc q ụ đ ế n m ộ t lá chứa t r ạ n g t h á i k ế t t h ú c t h ì ta nói r ữ n g m á y M đoán n h ậ n x â u vào đ a n g xét. Ngược l ạ i , n ê u k h ô n g có m ộ t lá n à o trong cây chứa t r ạ n g t h á i k ế t t h ú c t h ì ta nói M k h ô n g đ o á n n h ậ n x â u vào đó. C h ẳ n g h ạ n k h i cho x â u v à o (0, = 01001 đ ố i v ố i m á y M t h ì ta có cây đ o á n n h ậ n x â u co ị n h ư sau: Trong cây t r ê n có m ộ t đường đi t ừ q„ đ ế n q 4 e F nên xâu CO^OIOOI là x â u đ o á n n h ậ n được bởi m á y M . b) Phương pháp cho ôtômat bằng đồ thi chuyển Cho ô t ô m a t h ữ u h ạ n M = < £ , Q, 5, q , F>. H à m chuyển ô 0 có t h ể cho b ữ n g đồ t h ị chuyển có hướng theo n g u y ê n tắc sau: M ỗ i t r ạ n g t h á i q 6 Q là m ộ t đ ỉ n h của đồ t h ị . N ê u a 6 ì và t ừ 246
trạng thái qi chuyển sang trạng thái qj do đẳng thức Ô(q;,a) = qj (đối vối DFA) thì sẽ có một cung có hướng từ đỉnh qi sang đỉnh qj và trên cung đó được gán n h ã n a. Nêu ô(qj,a) = {qj , qj qj } đối vối ôtômat không đơn định thì từ q; sang qj . qj 2 qj có k cung gán cùng một nhãn a. Đỉnh vào của đồ thị chuyển là đỉnh ứng vói trạng thái ban đầu q,,. Các đỉnh có các trạng thái k ế t thúc được khoanh vòng tròn hai lần. Các đỉnh còn l ạ i khoanh bởi một vòng tròn. Ví dụ 4: Cho ôtômat đơn định M = , 0 ì = {0.1}, Q = {q . q,. q . q }. F = {q }. h à m chuyển 5: Q X ì -> Q 0 2 3 0 được cho dưới dạng đồ thì chuyển n h ư sau: Ì Ví dụ 5: Cho ôtômat không đơn định M = . 0 ì ={0,1}, Q = {q,„ q,, q . q }. F ={q , q ỉ còn h à m chuyển 2 3 2 4 5: Q X E -> 2 cho dưối dạng đồ thị Q 247
Đôi v ố i ô t ô m a t M ta đ ư a vào k h á i n i ệ m "chuyên dịch A" được định nghĩa n h ư sau: H à m A - Closure(T) cho t ậ p t r ạ n g t h á i đ ạ t được t ừ các t r ạ n g t h á i s 6 T qua p h é p chuyển dịch A duv n h ấ t . Lớp T có t h ể chỉ gồm m ộ t p h ầ n tử. Nó dược tính n h ư sau: Đẩy tất cả trạng thái trong T vào stack, Đặt A -Closure(T) là T While stack không rỗng do begin lấy t là phần tử trên cùng của stack ra; for mỗi trạng thải mà có đường đi từ t đến u có nhãn do if u không thuộc A -Closure(T) do begin Thêm u vào A -Closure(T); Đặt u vào Stack; end; end; T h u ậ t t o á n m ô phỏng ô t ô m a t k h ô n g đơn đ ị n h đ o á n n h ậ n x â u vào: Đ ầ u vào: M ộ t x â u v à o to, k ế t t h ú c b i ký h i ệ u file eof. M ộ t ô t ô m a t k h ô n g đơn định N v ố i t r ạ n g t h á i ban đ ầ u q,, và t ậ p t r ạ n g t h á i k ế t t h ú c F c Q . Đ ầ u ra: T r ả l ồ i "True" n ế u N đoán n h ậ n x â u co, "False" trong trường hợp ngược l ạ i : 248
Thuật toán : Begin S:= A -Closure(q ); 0 C:=ký tự tiếp; While c eof do begin S:= - Closure(Move(S,C)); C:=ký tự tiếp; end; if s ó F * 0 then return True else return False End; Chú ý rằng h à m Move(T.a) là tập trạng thái mà N có thể đạt được khi thực hiện dịch chuyển với ký hiệu vào a từ một trạng thái thuộc T. 1.3. Sự tương đương giữa ôtômat đơn định và không đơn định Theo định nghĩa của ôtômat đơn định M và ôtômat không đơn định N thì M cũng là N nên lốp các ngôn ngữ đoán nhận được bởi M cũng là lớp ngôn ngữ đoán nhận bởi N. Ký hiệu các lớp ngôn ngữ được đoán nhận bởi M và N tương ứng là L(M) và UN). Định lý 1: Lốp ngôn ngữ đoán nhận được bởi ôtômat đơn định trùng với lớp ngôn ngữ đoán nhận được bởi ôtômat không đơn định. 249
Chứng minh: Theo định nghĩa ôtômat đơn định và ôtômat không đớn định thì lớp ngôn ngữ đoán nhận được bởi ôtômat đơn định nằm trong lớp ngôn ngữ đoán nhận được bởi ôtômat không đơn định. Ta chứng minh bao hàm thức ngược l ạ i : Lớp ngôn ngữ đoán nhận được hỏi ôtômat không đơn định nằm trong lóp ngôn ngữ do ôtômat đơn định đoán nhận. Thật vậy, giả sử p e ì" đoán nhận được bởi ôtômat không đơn định N = 0 hay p 6 L(N). Ta xây dựng ôtômat đơn định M = đoán nhận p như sau: r = I ; Q' = 2 ; s ={q }; F'={U c Q / U n F * 0 Ị Q 0 0 còn ố: Q'xl -> Q' được xác định như sau: V u e Q'. V X € ì thì ố(U.x) = ỊJ S(q,x) qeU Với M định nghĩa như trên thì ta có: p e L(M) hay UN) C L(M). Ví du 6: Cho ôtómat không đơn định N = Q vối I={a,b}. Q={s,j. s,}. F={s,}. còn h à m chuy n ô: Q X ì ~> 2 được cho bằníỊ bảng chuy n sau: Trạng thái Ký hiệu vào a b So {Sụ. s,} Si Si 0 {s,,s,} Klii đó ôtômat đơn định tương ứng với ôtômat không đơn định N được xâv dựng như sau: M =
H à m chuyển ố cho dưới dạng bảng chuyển như sau: Trạng thái Ký hiệu vào a b 0 0 q< q 3 q 3 0 q 4 q 4 Q4 Ta có L(N) = L(M) hay N tương ứng vối M. Ví d ụ 7: Cho ôtômat không đơn định N = 0 với E = {a,b}, Q = {q , q„ q,0}, F' = {q }. 0 10 A Trong đồ thị chuyển trên thì A là xâu rỗng. Ta xây dựng ôtômat đơn định M như sau: M = ,0 ở đây: ì = {a,b} là bảng ký hiệu vào, Q = {A. B, c, D, E} là tập các trạng thái, A là trạng thái ban đầu, F = {E} tập trạng t h á i kết thúc, A = {q , qi, q2,
c - tai. q , q , Qõ. qe- q?} 2 4 D = {qi, q . q . Qs, Qo- q . qg} 2 4 7 E = { q i , q2, Q4, qs, q«- q7, Qio} (có chứa trạng thái k ế t thúc q ,0 của N) vối hàm chuyển cho đuối dạng bảng: Trạng thái Ký hiệu vào a b A B c B B D c B c D B E E B c hay ôtômat được biểu diễn dưới dạng đồ t h ị chuyển như sau: Ta chỉ ra rằng L(N) = L(M) ={(a/b)" abb}. Thật vậy. giả sử xét xâu vào là co = ababb Ta chỉ ra rằng hai ôtômat N và M cùng đoán nhận xâu co = ababb. Thật vậy, đối vối ôtômat M ta xây d n g chuỗi trạng thái ứng với xâu vào co là: co = a b a b b A - > B -> D -> B ^ D - > E e F 252
Vậy M đoán nhận xâu co. Đối vối N ta xây dựng cây đoán nhận xâu co = ababb như sau: q,0 £ F. nên N đoán nhận co = ababb. 253
J2. NGÔN NGỮ CHÍNH QUY VÀ Biểu THỨC CHÍNH QUY 2.1. N g ô n ngữ c h í n h quy G i ả sử X là b ả n g chữ h ữ u h ạ n k h ô n g rỗng. L* là t ậ p t ấ t cả các x â u (kể cả x â u rỗng) được xây d ự n g t r ê n ì . N h ư đ ã định nghĩa trưốc đ â y t h ì z = ì ' \ { } . + A T ậ p con E c E ' được gọi là m ộ t n g ô n n g ữ t r ê n b ả n g ì . T r ê n t ậ p t ấ t cả các n g ô n ngữ ta có t h ể đ ị n h nghĩa các p h é p t o á n hợp, giao, p h ủ n b ù , n h â n v à l ặ p các n g ô n ngữ. Trong các p h é p t o á n t r ê n , ta đặc b i ệ t c h ú ý ba p h é p t o á n sau đây: a) Phép hợp: Cho hai n g ô n ngữ Eị, E t r ê u t ậ p ì , ta định2 nghĩa p h é p hợp E j
c) Không có ngôn ngữ chính quy nào khác trên ì ngoài các ngôn ngữ chính quy được định nghĩa trong các bưốc a) và b) ở trên. Thông thường để diễn đạt các ngôn ngữ chính quy người ta đưa vào biểu thức chính quy. 2.2. B i ể u thức c h í n h quy Trên bảng X ta định nghĩa biểu thức chính quy theo các bước đệ quy sau đây: a. 0 là biểu thức chính quy, nó biểu diễn ngôn ngữ rỗng. b. Nếu a 6 X thì a là biểu thức chính quy, nó biểu diễn ngôn ngữ {a}. c. Nếu r. s là hai biểu thức chính quy trên ì biểu diễn hai ngôn ngữ R và s tương ứng. Khi đó: (r) VJ (s) là biểu thức chính quy biểu diễn ngôn ngữ R VJ s. (r) . (s) là biểu thức chính quy biểu diễn ngôn ngữ R . s. + (r)' là biểu thức chính quy biểu diễn ngôn ngữ R . Từ định nghĩa vê ngôn ngữ chính quy và biểu thức chính quy trên ì ta có: Định lý 2: M ọ i ngôn ngữ chính quy trên bảng ì đề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, phép nhân, phép lặp. Định lý 3 : Một ngôn ngữ trên ì là chính quy khi và chỉ khi nó biểu diễn được bởi một biển thức chính quy. Chú ý: a) Một ngôn ngữ chính quy là vô hạn khi và chỉ khi biểu thức chính quy biểu diễn nó có dấu + (phép lặp). b) Lóp t ấ t cả các ngôn ngữ chính quy trên E là lốp bé nhất chứa các tộp hữu hạn và đóng đôi vói các phép toán hợp, nhân và lặp. 255
2.3. Thuật toán Thompson Bài toán: Cho m ộ t b i ể u thức c h í n h quy. H ã y xây dựng ô t ô m a t k h ô n g đơn định N đ o á n n h ậ n n g ô n n g ữ c h í n h quy t ừ b i ể u thức c h í n h quy đã cho. Thuật toán: Vào: M ộ t b i ể u thức chính quy r t r ê n bộ ì . Ra: M ộ t ô t ô m a t N đ o á n n h ậ n n g ô n ngữ L ( r ) . Sau đ â y là mô t ả t h u ậ t t o á n của Thompson : Trưốc h ế t t á c h b i ể u thức chính quy r t h à n h các b i ể u thức c h í n h quy t h à n h p h ầ n r,, r , 2 r . Sau đó á p d ụ n g l u ậ t Ì, l u ậ t 2 k đ ể x â y dựng các ô t ô m a t k h ô n g đơn đ ị n h Ni, N-2 N k tương ứng đ o á n n h ậ n các n g ô n ngữ LỘT]), L ( r ) 2 L ( r ) . Cuối c ù n g k d ù n g l u ậ t 3 để xây dựng ô t ô m a t k h ô n g đơn đ ị n h N đ o á n n h ậ n n g ô n n g ữ L(r). - Luật 1: Đ ố i v ố i ký h i ệ u A , xây d ự n g ô t ô m a t k h ô n g đơn A định N đ o á n n h ậ n n g ô n ngữ { } n h ư sau: Start A KĐ—*® v ố i i là t r ạ n g t h á i ban đ ầ u còn f là t r ạ n g t h á i k ế t t h ú c . - Luật 2: V ố i a € ì , x â y dựng ô t ô m a t k h ô n g đơn định đ o á n n h ậ n {a} n h ư sau: Start a —CD——•© vói i là t r ạ n g t h á i ban đ ầ u , f là t r ạ n g t h á i k ế t t h ú c . - Luật 3: G i ả s N(s), N(r) là các ô t ô m a t t h à n h p h ầ n ứng v ố i các b i ể u thức c h í n h quy s v à r : 256
a) Đ ố i v ố i b i ể u thức c h í n h quy (s) u (r) ta x â y dựng ô t ô m a t k h ô n g đơn định N đ o á n n h ậ n n g ô n ngữ s U I R n h ư sau: ỏ đ â y i là t r ạ n g t h á i b a n đ ầ u , f là t r ạ n g t h á i k ế t t h ú c của N v à N n h ậ n được b ằ n g c á c h t ổ hợp h a i ô t ô m a t t h à n h p h ầ n N(s) v à N(r) theo sơ đồ b ả n g c h u y ể n t r ê n . b) Đôi v ễ i b i ể u thức c h í n h quy (s).(r) t h ì ô t ô m a t k h ô n g đơn định N đ o á n n h ậ n n g ô n n g ữ c h í n h quy S.R được cho dưễi dạng b ả n g chuyển sau đ â y : Start •0 N(s)
A Start -o -ỏ-ue^ò- A A ở đ â y i là t r ạ n g t h á i ban đ ầ u , f là t r ạ n g t h á i k ế t t h ú c của N . 2.4. T í n h c h ấ t c ủ a n g ô n n g ữ c h í n h quy Định lý 4 : Lớp t ấ t cả các ngôn ngữ c h í n h quy t r ê n ì là đ ó n g đ ố i v ố i các p h é p t o á n : hợp. n h â n , h i ệ u . l ấ y p h ầ n bù. n h â n ghép và lặp. Ì Chứng minh: T í n h đóng đôi v ố i các p h é p t o á n hợp. n h â n g h é p và l ặ p chứng m i n h theo định nghĩa b i ể u thức c h í n h quy. Ta chứng m i n h t í n h đóng đối vói các p h é p t o á n còn l ạ i sau đây: a) P h é p h i ệ u giữa R| và ĩỉ-2 là 2 n g ô n ngữ c h í n h quv t r ê n ì . G i ả sử R = R , \ R . ở đây R, = L ( M , ) . R 2 2 = L ( M ) và Mi là 2 ô t ô m a t đ o á n n h n Ri (i = 1 , 2), với M i = < £ . Qị. ỗ|. q,, F|>. M = . 2 2 2 2 2 Ta x â y dựng ô t ô m a t M đ o á n n h n R n h ư sau: M = v ố i Q = Q, X Q . q = (q,.q )e Q. 0 2 0 2 F = F, X ( Q A F , ) , còn ỗ: Q X ì -> Q được xác đ ị n h n h ư sau: ô((q,q').x) =
T h ậ t v ậ y , g i ả sử M = là ô t ô m a t đ o á n n h ậ n 0 R. K h i đó ô t ô m a t M ' =_ , ở đ â y A, B e A, a e I , là ký h i ệ u x â u rỗng. D ễ d à n g n h ậ n t h ấ y rằng: Định lý 5 : Đôi vối v ă n p h ạ m c h í n h quy suy rộng G bao giò cũng xâv dựng được v ă n p h ạ m c h í n h quy G' sao cho L(G') = L(G) \ ri. Định nghĩa 4: V ă n p h ạ m c h í n h quy suy rộng là v ă n p h ạ m c h í n h quy m ẫ u n ê u nó k h ô n g có quy tệc A —> a. Định lý 6 : Đôi v ố i v ă n p h ạ m c h í n h quy suy rộng có t h ể xây dựng được v ă n p h ạ m c h í n h quy m ẫ u t ư ơ n g đương v ố i nó. Chứng minh: G i ả sử G = là v ă n p h ạ m c h í n h quy suy rộng. T h ê m ký h i ệ u K v à o A v à đ ặ t A' = A a e R thay bởi cặp quy tệc A A -> aK, K -> ta được R'. Rõ r à n g v ă n p h ạ m G' = < £ , A , ĩ, R'> là v ă n p h ạ m c h í n h quy m ẫ u v à L(G) = L(G'). 259