Bài giảng Lý thuyết tính toán: Chương 3 - PGS.TS. Phan Huy Khánh

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

104
lượt xem 11
download

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

Chương 3 của bài giảng Lý thuyết tính toán tập trung trình bày về văn phạm và ôtômat đẩy xuống. Các nội dung chính của chương này gồm có: Khái niệm ngôn ngữ lập trình, văn phạm, Ôtômat đẩy xuống. Hy vọng bài giảng sẽ mang lại cho các bạn nhiều hữu ích.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Lý thuyết tính toán: Chương 3 - PGS.TS. Phan Huy Khánh

Chương 3 Văn phạ phạm và và ôtômat đẩ đẩy xuố xuống  Khá Khái niệ niệm ngôn ngữ ngữ lập trì trình (NNLT) (NNLT)  Văn phạ phạm Lý thuyế thuyết tí thuyết ính toá ttính toán toán  Khá Khái niệ niệm văn phạ phạm (Theory (Theory of of Computation) Computation)  Phân cấ cấp cá các loạ loại văn phạ phạm củ của Chomsky  Văn phạ phạm chí chính qui PGS.TS. Phan Huy Khá Khánh khanhph@vnn.vn  Ôtômat đẩ đẩy xuố xuống  Ngôn ngữ ngữ phi ngữ ngữ cảnh  Quan hệ hệ với cá các ôtômat đẩ đẩ y xuố xuống Tính chấ chất củ của cá các ngôn ngữ ngữ phi ngữ ngữ cảnh Chương 3  Văn phạ phạm phạm và và ôtômat đẩ ẩy đẩy đ xuố xuống xuống 2/77 2/77 Lịch sử sử ngôn ngữ ngữ lập trì trình Sự ra đờ đời củ của hợ hợp ngữ ngữ  Từ khi má máy tí tính điệ điện tử tử xuấ xuất hiệ hiện, con ngườ người phả phả i tì tìm cá cách  Ngôn ngữ ngữ hợp dị dịch ra đờ đời từ từ nhữ những năm 1950 : lập trì trình, hay lậ lập chương trì trình (Programming)  Gọi tắ tắt hợ hợp ngữ ngữ (Assembly) (Assembly) hay còn đượ được gọ gọi là là các ngôn  Nhữ Những ngôn ngữngữ đầ đầu tiên chỉ chỉ là tổ hợp củ của cá các con số số (bit) 0 ngữ ngữ biể biểu tượ tượng (Symbolic Language) và 1, gọ gọi là là ngôn ngữ ngữ máy (Machine Language)  Trong hợ hợp ngữ ngữ, cá các mã lệ lệnh và và đị địa chỉ chỉ các toá toán hạ hạng đượ được  Ngôn ngữ ngữ máy phụ phụ thuộ thuộc hoà hoàn toà toàn và vào tổ tổ chứ chức phầ phần cứ cứng thay thế thế bởi cá các từ từ tiế tiếng Anh gợ gợi nhớ nhớ (Mnemonic) (Mnemonic) như như DIV, DIV, của má máy, vàvà rất sơ cấ cấp JUMP, MUL...  Việ Việc lậ lập trì trình rấ rất khó khó khăn, khăn, nhọ nhọc nhằ nhằn và và dễ sai só sót  Các chương trì trình viế viết bằ bằng Assembly :  Từ nhữ những năm 1950, để để giả giảm nhẹ nhẹ việ việc lậ lập trì trình :  Không thể thể chạ chạy ngay đượ được mà mà phả phải qua giai đoạ đoạn hợ hợp dị dịch  Ngườ Người ta sử dụng kỹ thuậ thuật gọ gọi chương trì trình con (Subprogram (Assembler) thà thành ngôn ngữ ngữ máy hay Subroutine) bằng cácách dùng lại nhữ những chương trì trình đã viế viết  Phụ Phụ thuộ thuộc và vào phầ phần cứ cứng  Ngườ Người ta xây dự dựng cá các thư việ viện (kho (kho chương trì trình mẫ mẫu) để để  Xa lạ lạ với ngôn ngữ ngữ tự nhiên (Natural language) khi cầ cần thì thì gọi đế đến 3/77 3/77 4/77 4/77 Ngôn ngữ ngữ máy tiế tiế n gầ gần đế đế n ngôn ngữ ngữ tự nhiên Phá Phát triể triển củ của NNLT  Năm 1957 :  Theo sựsự phá phát triể triển củ của cá các thế thế hệ máy tí tính, cá các ngôn ngữ ngữ  FORTRAN (FORmula TRANslator/ biên dị dịch cá các công thứ thức) lập trì trình cũ cũng không ngừngừng đượ được cả cải tiế tiến và và hoà hoàn thiệ thiện để để đượ được IBM đềđề xướ xướng làlà một trong nhữ những NNLT đầ đầu tiên càng ngà ngày cà càng đá đáp ứng nhu cầ cầu củ của ngườ người sửsử dụng và và  FORTRAN gầ gần gũ gũi ngôn ngữ ngữ tự nhiên vớ với cá cách diễ diễn đạ đạt giả giảm nhẹ nhẹ công việ việc lậ lập trì trình Toá Toán họ học cho phé phép giả giải quyế quyết cá các bà bài toá toán khoa họ học –  Nhiề Nhiều ngôn ngữ ngữ đã ra đờ đời và và hình thà thành hai loạ loại ngôn ngữ ngữ : kỹ thuậ thuật và và đượ được ứng dụdụng rấ rất rộ rộng rãi  Ngôn ngữ ngữ máy bậ bậc thấ thấp (low- (low-level language)  Tiế Tiếp theo là là sự ra đờ đời củ của cá các NNLT như :  Hợp ngữ ngữ  ALGOL 60 (ALGOrithmic Language) 1960,  COBOL (Comon Business Oriented Language) 1964  Ngôn ngữ ngữ lập trì trình bậ bậc cao  Simula, v.v...  Các ngôn ngữngữ bậc thấ thấp và và h ợp ngữ ngữ, thư thườờng chỉ chỉ dùng để để viế viết cá các trì trình điề điều khiể khiển và và kiể kiểm tra thiế thiết bị bị, các trì trình sử sửa lỗ lỗi (Debugger)... 5/77 5/77 6/77 6/77 1
Ngôn ngữ ngữ lập trì trình bậ bậc cao Rất nhiề nhiều NNLT bậ bậc cao đã đượ được phá phát triể triển  Các ngôn ngữ ngữ lập trì trình bậ bậc cao (High- (High-level Language) : Một và vài NNLT quen thuộ thuộc :  Công cụcụ giú giúp giả giải quyế quyết cá các vấ vấn đề đề thự thực tế tế  Lisp (LISt Processing) 1960  Là nơi mà mà nhữ những thà thành tự tựu nghiên cứ cứu mớ mới nhấ nhất củ của Tin họ học  PL/1 (Programming Language number 1) 1963 đượ được đưa vàvào  Basic (Beginner’ (Beginner’s All- All-Purpose Symbolic Instruction Code) 1964  Lĩnh vự vực nghiên cứ cứu phá phát triể triển cá các ngôn ngữ ngữ lập trì trình vừ vừa có có  Pascal (lấ (lấy tên nhà nhà Toá Toán họ học Phá Pháp Blaise PASCAL) 1970 tính truyề truyền thố thống, vừ vừa có có tính hiệ hiện đạ đại  PROLOG (PROgramming in LOGic) 1970  C 1972  ADA (lấ (lấy tên nhà nhà nữ khoa họ học Augusta Ada Byron) 1980  C++, Java, C#, Visual Basic  Cơ sở sở Dữ liệ liệu, lậ lập trì trình hà hàm, lậ lập trì trình logic, hướ hướng đố đối tượ tượng, v.v... 7/77 7/77 8/77 8/77 Phân loạ loại NNLT theo phương thứ thức Định nghĩ nghĩa mộ một NNLT bậ bậc cao  Có nhiề nhiều NNLT theo phương thứ thức :  Một NNLT bậ bậc cao đượ được xây dựdựng mô phỏ phỏng  Mệnh lệnh (imperative) : Fortran (1957), Cobol (1959), Basic (mộ (một cá cách thô thiể thiển) ngôn ngữ ngữ t ự nhiên, nhiên, (1965), Pascal (1970), C (1971), Ada (1979)... thườ thường là là tiế tiếng Anh (hoặ (hoặc tiế tiếng Nga), từ từ bốn yế yếu tố tố :  Định hướ hướng đốđối tượ tượng (object- (object-oriented) : Smalltalk (1969), C++  Bộ ký tự tự (Character Set) (1983), Eiffel (1986), Java (1991), C# (2000), ...  Bộ từ vựng (Vocabulary)  Hàm (functional) : Lisp (1958), (1958), ML (1973), Scheme (1975), Caml (1987), Miranda (1982), ...  Cú phá pháp (Semantic)  Logic (logic- (logic-based) chủ chủ yếu là là ngôn ngữ ngữ Prolog (1970)  Ngữ Ngữ nghĩ nghĩa (Semantic)  Ngôn ngữ ngữ thao tá tác cơ sở sở d ữ liệ liệu như SQL (1980)...  Căn cứ cứ vào cú cú phá pháp củ của NNLT, ngườ người lậ lập trì trình viế viết chương trì trình  Xử lý song song (parallel) : Ada, Occam (1982), C- C-Linda, ... gồm cá các câu lệ lệnh để để giả giải quyế quyết bà bài toá toán củ của mì mình  Mỗi câu lệ lệnh viế viết ra không nhữ những đú đúng đắ đắn vềvề mặt cú cú phá pháp,  Ngoà Ngoài ra còn có có : mà còn phả phải đú đúng đắ đắn cả cả về mặt ngữ ngữ nghĩ nghĩa, hay ý nghĩ nghĩ a logic  Lập trì trình phân bổ (Distributed Programming). của câu lệ lệnh, để để giả giải quyế quyết bà bài toá toán  Lập trì ràng buộc (Constraint Programming). trình rà  Ngoà Ngoài ra, còn có có yếu tố tố một thứ thứ năm là là tính thự thực dụ dụng  Lập trì trình hướ hướng truy cập (Access- (Access-Oriented Programming). (Pragmatic)  Lập trì trình theo luồng dữ liệu (Dataflow Programming), v.v... 9/77 9/77 10/77 10/77 Bộ ký tự tự Bộ từ vựng  Bộ ký tự tự (Character Set)  Bộ từ v ựng (Vocabulary)  Gồm mộ một tậ tập hợ hợp hữ hữu hạ hạn cá các ký tự tự  Gồm cá các từ từ (Word) (Word) hay đơn vịvị từ vựng (Token) dù dùng để để tạo thà thành câu lệ lệnh và và đượ được phân loạ loại tuỳ tuỳ theo vai trò củ của chú chúng trong NNLT đượ được phé phép dùdùng trong ngôn ngữngữ, thư thườ ờng là là các ký tự tự ASCII  Mỗi loạ loại từ từ vựng lạ lại đượ được chia ra thà thành cá cá c nhó nhóm nhỏ nhỏ hơn  Có thể thể hiể hiểu bộ bộ ký tự tự có vai trò như bả bảng chữ chữ cái (Alphabet) tuỳ tuỳ theo chứ chức năng sử sử dụng của mộ một ngôn ngữ ngữ tự nhiên  Ví dụ :  Ví dụ bộ 9 né nét cơ bả bản dù dùng viế viết chữ chữ Hán : Chương trình Pascal Các đơn vị từ vựng Program P; - Tên, hay định danh (Identifier) : Var , y : Integer; Read, Write, P, x, y Begin - Hằng (Constants) : 2 Read(x); y:=x+2; - Toán tử (Operators) : + , := Write(y) - Dấu phân cách (Delimiters) : End. :, (, ), Begin, End. - Từ khoá/dành riêng (KeyWord) : 11/77 11/77 Program, Var, If Then... 12/77 12/77 2
Cú phá pháp Ví dụ văn phạ phạm tiế tiếng Anh  Cú phá pháp (Syntax) (Syntax) hay văn phạ phạm (Grammar)  Giả Giả sử các câu tiế tiếng Anh đượ được xây dự dựng theo nhữ những quy là tập hợ hợp cá các quy tắ tắc cho phé phép : tắc như sau :  Quy địđịnh cá cách thứ thức kế kết hợ hợp cá các ký tự tự thà thành từ từ, kế kết hợ hợp cá các  Câu (Phrase/Sentence) gồ gồm có có hai thà thành phầ phần lầ lần lượ lượt : từ thà thành câu lệ lệnh đú đúng (Statement - Instruction), kếkết hợ hợp  Chủ từ (Subject) các câu lệ lệnh đú đúng thà thành mộ một chương trì trình hoà hoàn chỉ chỉnh  Động từ (Verbe)  Có thể thể hình dung cá cách kế kết hợ hợp nà này giố giống cá cách đặ đặt câu trong Chủ từ có thể  thể là He hoặ hoặc She một ngôn ngữngữ tự nhiên  Động từ có thể thể là sleep hay eat  Để đị định nghĩ nghĩa cú cú phá pháp mộ một ngôn ngữ ngữ lập trì trình, ngư ngườ ời ta thườ thường sử sử dụng :  Từ đó đó có thể thể xây dự dựng đượ được cá các câu kiể kiểu S+V :  Hoặ Hoặc sơ đồ đồ cú phá pháp (Syntax Diagram)  He sleep  Hoặ Hoặc dạng chuẩ chuẩn Backus- Backus-Naur (BNF (BNFBackusNaur Normal Form),  He eat hay dạng Backus- Backus-Naur mở mở rộng (EBNF (EBNFExtended BNF)  She sleep  She eat 13/77 13/77 14/77 14/77 Ví dụ sơ đồ đồ cú phá pháp câu tiế tiếng Anh Khá Khái niệ niệm BNF  Trong tiế tiếng Anh, mộ một câu đơn giả giản gồ gồm 3 thà thành phầ phần :  BNF gồ gồm mộ một dãy cá các quy tắ tắc, hay dạ dạng thứ thức  Chủ Chủ từ (Subject), chẳ chẳng hạ hạn “I” và “You” You”  Mỗi quy tắ tắc có
Ví dụ một NNLT đơn giả giản Lập trì trình theo cú cú phá pháp văn phạ phạm Một câu, tứ tức là là một chương trì trình đơn giả giả n, chẳ chẳ ng hạ hạn :  Văn phạ phạm củ của mộ một NNLT đơn giả giản dạ dạng EBNF như sau : program n := 1 ; while n
Ý nghĩ nghĩa củ của cá các sả sản xuấ xuất Một số số quy ướ ước  Mỗi sả sản xuấ xuất dạ dạng ( (, ) cho biế biết :  Sau đây là là một số số quy ướ ước khi mô tả tả văn phạ phạm G :  Phầ Phần tử tử bên trá (V+) củ trái ( của sả sản xuấ xuất  Các biế biến A, B, C..., X, Y...  N = V   đượ được thay thế thế bởi phầ phần tử tử bên phả (V*) phải (  Các ký tự tự thuộ thuộc  đượ được biể biểu diễ diễn bở bởi a, b, c...  Từ S, bắ bắt đầ đầu quá quá trì trình sả sản sinh câu bằ bằng cá cách :  Áp dụ dụng sả sản xuấ xuất đầ đầu tiên là là S    Các quy tắ tắc, hay sả sản xuấ xuất , )  R, R, đượ được viế viết dạ dạng :   Sau đó đó tìm trong  các phầ phần câu u V có chứ V+ chứa biế biến X  N để áp dụ dụng tuỳ tuỳ ý cá các sả sản xuấ xuất u  v hay  G   Thự Thực hiệ hiện mộ một cá cách đệ đệ quy cho đế đến khi nhậ nhận đượ được câu w nếu muố muốn chỉ chỉ đị định đó đó là sản xuấ xuất thuộ thuộc văn phạ phạm G chỉ chỉ chứ chứa cá các ký hiệ hiệu a  , hay nó nói cá khác, w  * cách khá khi là làm việ việc cù cùng lú lúc vớ với nhiề nhiều văn phạ phạm khá khác nhau  Thông thườ thường, ngư ngườờ i ta tì tìm cá các phầ phần câu u để để áp dụ dụng cá các  Ký tự tự đầ đầu luôn luôn biể biểu diễ diễn bở bởi S sản xuấ xuất lầ lần lượ lượt từ từ trá trái qua phả phả i  Các câu rỗ rỗng đượ được biể biểu diễ diễn bở bởi  25/77 25/77 26/77 26/77 V í dụ Sản sinh câu trong G  Cho văn phạ  Cho G { S  A | B ; B  bB |  ; A  aA |  } phạm G = (V, , R, S) vớ vớ i :  Bằng cá cách áp dụ dụng liên tiế tiếp cá các sả sản xuấ xuất trong R, ta nhậnhận  N = { S, A, B } đượ được cá các câu sả sản sinh bở bở i văn phạ phạm G   = { a, b }, S là là ký tự tự đầ đầu.  Ví dụ, aaaa là m ột câu do G sinh ra bằ bằng cá cách áp dụ dụng lầ lần  R = { S  A, S  B, B  bB, B  , A  aA, A   } lượ lượt cá các sả sản xuấ xuất :  Để cho gọ gọn, khi mô tả tả một văn phạ phạm, ngườ người ta thườ thường nhó nhóm S SS các quy tắ tắc có có cùng ký tự tự bên trá trái vớ với nhau : A Áp dụ dụng S  A AA SA|B B  bB |  A  aA |  aA  A  aA aa AA  Thay vì vì liệ liệt kê hế hết cá các thà thành phầ phần củ của văn phạ phạm G, aaA  A  aA ngườ người ta chỉ chỉ liệ liệt kê cá các quy tắ tắc R củ của văn phạ phạm màmà thôi aaaA  A  aA aa AA  Chẳ Chẳng hạ hạn văn phạphạm G ở trên chỉ chỉ cần liệ liệt kê cá các quy tắ tắc : aaaaA  A  aA AA aa G { S  A | B ; B  bB |  ; A  aA |  } aaaa  A AA B ài tậập :: Mô aa Bài ttập Mô tảả VP ttả VP GG bằ ằng cá bbằng ách thay ccách thay thế thế ccác thế á c ký ký hiệ hiệu quy hiệu quy ướ ướ c cho ước cho cáác ccác B ài tậ Bài ập :: ttập đơn đơn vị vvịị ttừ ừ vvựng ựng trong trong ví vvíí ddụ ụ NNLT NNLT đơnđơn giả gi ản trướ giản trước đây trước đây ?? TTìm ìm cá ách ááp ccách p dụụng lầ ddụng ần lượ llần lượt cá lượt ác sả ccác ản xuấ ssản xu ất để xuất ể sinh đđể sinh ra ra câu câu bbbbb bbbbb ??  27/77 27/77 TTìm ìm cá ách biể ccách biểu diễ biểu diễn cá diễn ác quy ccác quy tắ ắc tạ ttắc ạo tên ttạo tên trong trong NNLT NNLT thà thành VP thành VP vàà cho vvà cho ví vvíí ddụ ụ sinh sinh câu28/77 28/ câu 77 Phé Phép suy dẫ dẫn mộ một bướ bước trong G Phé Phép suy dẫ dẫn nhiề nhiều bướ bước trong G  Cho văn phạ phạm G = (N, , R, S),  Cho văn phạ phạm G = (N, , R, S), uV+, v vV* đgl cá các dạ dạng câu uV+, v vV* đgl cá các dạ dạng câu  Câu v đượ được sả sản sinh từ từ u bằ bằng m ột bướ bước suy dẫ dẫn trong G  Câu v đượ được sả sản sinh từ từ u bằ bằng nhiề nhiều bướ bước suy dẫ dẫn trong G (derives v from u in one step) đượ được biể biểu diễ diễn bở bở i : (derives v from u in several steps) đượ được biể biểu diễ diễn bở bởi : u G v nễ u (nế (nếu và và chỉ chỉ nếu) : u *G v nễ u :  u = xu’ xu’y u gồ gồm 3 phầ phần x, u’ u’ và y, x và và y có có thễ thễ rỗng  và v0 ... vk  V+ sao cho :  k  0 và  v = xv’ xv’y v gồ gồm 3 phầ phần x, v’ v’ và y  u = v0  u ’  v’ là một sx củ của G  v = vk  vi G vi+1 với i, 0  i  k-1  Có thể thể viế viết đầ đầy đủ đủ khi k nhỏ nhỏ : u *G v nễu u = v0 G v1 G v2 G ... G vk = v 29/77 29/77 30/77 30/77 5
Văn phạ phạm G sinh ra câu Phân cấ cấp văn phạ phạm củ của Chomsky  Văn phạ phạm G sinh ra cá các câu bằ bằng cá cách thự thực hiệ hiện quá quá trì trình  N. Chomsky, chia văn phạ phạm thà thành bố bốn loạ loạ i tù tùy theo tí tính suy dẫ dẫn từ từ ký tự tự đầ đầu S cho đế đến khi nhậ nhận đượ được câu gồ gồm cá các chấ chất củ của cá các sả sản xuấ xuất sử sử dụng trong văn phạ phạm : ký tự tự kết thú thúc thuộ thuộc , w   *  Loạ Loại 0 Văn phạ phạm tự tự do  Ngườ viết : S *G Ngườ i ta viế w  Không giớ giới hạ hạn về về sản xuấ xuất (sả (sản xuấ xuất có có dạng bấ bất kỳ kỳ)  Ngôn ngữ ngữ L do văn phạ phạm G sinh ra, viế viết L(G),  Loạ Loại 1 Văn phạ phạm cả cảm ngữ ngữ cảnh là tập hợ hợp cá các câu sao cho : (Context Sensitive Grammar)  Các sả sản xuấ xuất có có dạng , , ||  || và và S   L(G) = { w  * | S *G w }  Loạ Loại 2 Văn phạ phạm phi ngữ ngữ cảnh (Context Free Grammar)  Ví dụ :  Các sả sản xuấ xuất có có dạng A  , A  N, không có có hạn chế chế g ì về   Văn phạ phạm G { S  A | B ; B  bB |  ; A  aA |  }  Loạ Loại 3 Văn phạ phạm chí chính qui (Regular Grammar) ngữ L(G) = a*  b* sinh ra ngôn ngữ gồm cácác câu hoặ hoặc chứ chứa toà toàn chữ chữ a, hoặ hoặc chứ chứa toà toàn chữ chữ b  Sản xuấ xuất có có dạng : A  wB | w, , A và và B  N, w  * hoặ hoặc A  Bw | w 31/77 31/77 32/77 32/77 Nhậ Nhận xé xét về về văn phạ phạm chí chính qui Quan hệ hệ giữ giữa cá các loạ loại văn phạ phạm  Mọi sả sản xuấ xuất củ của văn phạ phạm chí chính qui :  Quy ướ ước gọ gọi văn phạ phạm loạ loạ i i là là Vpi, i=0..3,  Có vế trá trái  là một ký tự tự A  N quan hệ hệ giữ giữa cá các loạ loại văn phạ phạm đượđược biể biểu diễ diễn như sau :  Có vế phả phải  gồm cá các ký tự tự kết thú thúc w  *, VP3  VP2  VP1  VP0 tiế tiếp theo sau, hay đặ đặt trướ trước, hoặ hoặc không có có, mộ một ký tự tự BN  Quan hệhệ bao hà hàm ở trên là là thự thực sự sự :  Văn phạ phạm chí chính qui G {A  Bw | w } i>j nễ nễu VPi  VPj phạm tuyến tí đgl văn phạ tính trá trái (Left (Left Linear Grammars)  Với i>j thì thì một văn phạ phạm loạ loại i cũng là là văn phạ phạm loạ loại j  Văn phạ phạm chí chính qui G {A  wB | w } phạm tuyến tí đgl văn phạ tính phải (Right (Right Linear Grammars)  Sự bao hàhàm giữ giữa VP2 và VP1 không đượ được thậ thật rõ rà ràng :  VP2 có thể thể chứ chứa cá các sả sản xuấ xuất dạ dạng A    Ngườ Ngườ i ta chứ chứng minh đượ được rằrằng mọ mọi ngôn ngữ ngữ sản sinh bở bở i  Do vậ vậ y, điề điều kiệ kiện | ||  || củ của cá cá c VP1 không thỏ thỏa mãn phạm tuyến tí một văn phạ tính phả i cũng có có thể thể đượ được sả sản sinh bỡi mộ phạm tuyến tí một văn phạ tính trá trái và ngượ ngược lạlạ i  Với mọ mọi loạ loại sả sản xuấ xuất khá khá c, điề điều kiệ kiện nà nà y lạ lạ i thỏ thỏa mãn 33/77 33/77 34/77 34/77 Tính tương đương giữ giữa văn phạ phạm và và Bao hà hàm giữ giữa cá các NN do VP sinh ra ôtômat  Bảng tó tóm tắ tắt về về tính tương đương giữ giữa văn phạ phạm và và ôtômat của cá các lớ lớp văn phạ phạm theo Chomsky : Loại Văn phạm Dạng sản xuất Ôtômat Ví dụ L(VP0) Không có 0 Tự do Máy Turing Ngôn ngữ tự nhiên hạn chế gì L(VP1)   , Máy Turing với 1 Cảm ngữ cảnh {anbncn | n  1} ||  || băng hữu hạn L(VP2) 2 Ôtômat Phi ngữ cảnh A {anbn | n  1} đẩy xuống L(VP3) 3 Chính quy A  bB | w Ôtômat hữu hạn {0(10)n | n  0} 35/77 35/77 36/77 36/77 6
Các văn phạ phạm chí chính qui Ví dụ 1 : xây dự dựng VP3 G từ từ NNCQ L  Các VP3 đgl văn phạ phạm chí chính quy là là không phả phải ngẫ ngẫu nhiên  Cho M vớ vớ i L(M) là là NNCQ gồ gồm cá các câu kế kết thú thúc bở bởi b  Thự Thực tế tế, cá các ngôn ngữ ngữ đượ được sả sản sinh bở bở i VP3  L(M) = (a+b)*b đều là là ngôn ngữ ngữ chí chính quy hay mọ mọi câu bấ bất kỳ kỳ kết thú thúc bở bởi mộ một con b  Ta có có đị định lý sau đây :  Ví dụ các câu sau  L(M) : a b  b b  Một ngôn ngữngữ là chí chính qui nễ nễu ngôn ngữ ngữ đó đó đượ được sả sản sinh bở bởi mộ một văn phạ phạm chí chính qui  abbab SS AA  aaabbb = a3b3 ... a Ngườ Người ta viế viết :  L(G) = L( L() = L(M) = L Với G là  Xây dự dựng VPCQ G từ từ ôhh M sao cho L(G)=L(M) : là VP3, l là một BTCQ vàvà M là là một ôhh L là một ngôn ngữ G { S  aS | bA ; ngữ chí chính qui A  bA | aS ; A  } } do A là là trạ trạng thá thái cuố cuối duy nhấ nhất 37/77 37/77 38/77 38/77 Ví dụ 2 : xây dự dựng VP3 G từ từ NNCQ L Bài tậ tập  Cho M như sau :  Xây dự dựng cá các VPCQ G từ từ các ôhh M dướ dướ i đây :  Xây dự dựng VPCQ G từ từ ôhh M sao cho L(G)=L(M) : G { S  bS | aA ; A  aB | bS ; B  aB | bC ; C  bS | aA | } } 39/77 39/77 40/77 40/77 Xây dự dựng ôhh M từ từ VP3 G V í dụ 2  Cho VP3 G gồ gồm cá các sx như sau :  Cho VP3 G gồ gồm cá các sx như sau : { S  aS | bS | abb } { S  aS | bS | a | b }  Xây dự dựng ôhh M sao cho L(M) = L(G) :  Xây dự dựng ôhh M sao cho L(M) = L(G) : a, b a a, b Hoặ a, b abb Hoặc SS AA SS AA abb gọn hơn SS AA b Chú Chú ý A là là trạ trạng thá trạng thái cuố thái cuối mớ cuối mớ i thêm và mới ào vvào Chú Chú ý A là là trạ trạng thá trạng thái cuố thái cuối mớ cuối mớ i thêm và mới ào vvào 41/77 41/77 42/77 42/77 7
Bài tậ tập Các tí tính chấ chất củ của ngôn ngữ ngữ chí chính quy  Cho cá các VP3 Gi như sau :  Cho hai NNCQ L1 và L2 G1 { S  bS | aT | T T  aT | bU | ; ; U  aT | } }  Ta có có tính chấ chất sau đây : Các ngôn ngữ ngữ đượ được tạ tạo thà thành bở bởi G2 { S  aA | aB | b A A  b ; B  bB | a }  Phé Phép hợ hợp củ của hai NNCQ L1  L2  Phé Phép ghé ghép tiế tiếp củ của hai NNCQ L1 . L2  Xây dự dựng cá các ôhh M thừ thừa nhậ nhận cá các L(Gi)  Phé Phép nghị nghịch đả đảo mộ một NNCQ L1R  Phé Phép lấ lấy phầ phần bù bù một NNCQ L1 =  – L1  Phé Phép giao củ của hai NNCQ L1  L2 đều là là các NNCQ 43/77 43/77 44/77 44/77 Bài tậ tập chương 3 Hướ Hướng dẫ dẫn 1. Mô tả tả các ngôn ngữ ngữ cho bở bở i cá các văn phạ phạm sau đây :  Mô tả tả ngôn ngữ ngữ sinh ra bở bở i văn phạ phạm G :  S  aS | Sb | aSb | c  Bướ Bước 1 :  S  SS | a | b Vẽ các cây con phân tí tích (sub- (sub-parsetree) cho cá các SX củ của G  S  aA | bB | c A  Sa B  Sb  Bướ Bước 2 : Tì Tìm cá các khả khả năng ghé ghép cá các cây con phân tí tích để để tạo câu xuấ xuất phá phát từ từ gốc S  S  AB A  Sc | a B  dB | b  Bướ Bước 3 : Đọc cá các dạ dạng câu cócó thể thể sinh ra ở bướ bước 2  S  SaS | b  Bướ Bước 4 : Dù Dùng BTCQ, hoặ hoặc dù dùng biể biểu diễ diễn tậ tập hợ hợp để để ghé ghép  S  aS | bS | a | b nối cá các kế kết quả quả ở bướ bước 3  SX|Y X Y  aY | bY | a | b  Bướ Bước 5 : trì trình bà bày kế kết quả quả 2. Mô tả tả văn phạ phạm sả sản sinh cá các ngôn ngữ ngữ sau đây :  a *b  (a+b)(ab)*(baab)* 45/77 45/77 46/77 46/77 Hướ Hướng dẫ dẫn Hướ Hướng dẫ dẫn 3  Mô tả tả văn phạ phạm G sả sản sinh ngôn ngữ ngữ đã cho :  Làm thế thế nào để để liệ liệt kê cá các câu sả sản sinh từ từ một ngôn ngữ ngữ L  Bướ Bước 1 : Đặt cá các phầ phần câu bở bởi cá các ký tự tự AN đã cho ?  Bướ Bước 2 : Đặt cá các SX từ từ ký tự tự đầ đầu S vớ với cá các ký tự tự A ở bướ bước 1  Bướ Bước 1 : Xây dự dựng cây “bao đóng” * đóng”  Bướ Bước 3 : Hòan thiệ thiện kế kết quả quả để để nhậ nhận đượ được L(G)  Bướ Bước 2 : Tìm cá các tí tính chấ chất P củ của cá các câu w sả sản sinh từ từ ngôn ngữ ngữ L  Ví dụ (a+b)(ab)*(baab)* sao cho w  L vàvà P(w) P(w)  S  ABC  Bướ Bước 3 : “Nhặ Nhặt ra” ra” từ cây “bao đóng” * các câu w ở bướ đóng” bước 2  A a |b  B  abB |   C  baabC |  47/77 47/77 48/77 48/77 8
Mô tả tả ôtômat đẩ đẩy xuố xuống (ôđx (ôđx)) Hoạ Hoạt độ động củ của ôđx  Một ôđx không đơn đị định Hoạ Hoạt độ động đoá đoán nhậ nhận Ôđx không đơn đị định như sau : NSA : Non- Non-deterministic Stack Automaton,  Tương tự tự một ôhh không đđ, đđ, hay NPA : Non- Non-deterministic Pushdown Automaton Automaton câu và w* đượ vào w được đặ đặt ở mút trá trái trên băng và vào có một số số phầ phần tửtử tương tự tự ôhh :  Lú c đầ đầu, đầ đầu đọđọc ở vị trí trí w(1) w(1)  Một băng vàvào chứ chứa câu sẽ sẽ đượ được đoá đoán nhậ nhận (ở (ở mút trá trái nhấ nhất) DSĐX rỗ rỗng và và ôđx đang ở trạtrạng thá thái đầ đầu q0  Một đầ đầu đọ đọc đọ đọc lầ lần lượ lượt cá các ký tự tự của câu trên băng  Đầu đọ đọc đọ đọc lầ lần lượ lượt từ từng ký tựtự của w trên băng  Một tậ tập hợ hợp cá các trạ trạng thá thái, trong đó đó có một trạ trạng thá thái đầ đầu và và một số số trạ trạng thá thái cuố cuối (trạ (trạng thá thái đạ đạt đượ được)  Ôđx nhì nhìn mộ một phầ phần câu trên đỉ đỉnh DSĐX (Top) để để thay thế thế  Một quan hệ (Pop- (Pop-Push) bằ bằng cá cách ghi (đè) lên mộ một dãy ký tự tự hệ chuyể chuyển tiế tiếp là làm thay đổđổi trạ trạng thá thái với mỗ mỗi ký tự tự đọ đọc đượ được rên băng  Ôđx di chuyể chuyển đầ đầu đọ đọc qua phả phải và và thay đổ đổi trạ trạng thá thái Ngoà Ngoài ra, NSA còn có có :  Ôhh dừ dừng khi mọ mọi ký tự tự của w đã đượ được đọ đọc hế hết  Một danh sásách đẩ đẩy xuố xuống (Stack/Pushdown (Stack/Pushdown List) List) (DSĐX (DSĐX)) và thừ thừa nhậ nhận câu, hoặ hoặc hó hóc giữ giữa chừ chừng có thể thể chứ chứa không hạ hạn chế chế các ký tựtự nào đó đó  Một đầ đầu ghi để để có thể thể ghi lên DSĐX 49/77 49/77 50/77 50/77 Minh hoạ hoạ hoạ hoạt độ động củ của ôđx Định nghĩ nghĩa hì hình thứ thức ôđx  Một NSA là là m ột bộ bộ 7 : M  Q, , , , Z, q0, A A, trong trong đó đó : Câu và =a nbn  Q là là tập hợ hợp hữ hữu hạ hạn cá các trạ trạng thá thái vào trên băng w w=a b   là bảng chữ chữ vào hữ hữu hạ hạn Input Alphabet Alphabet a a a b b b a a a b b b   là bộ chữ chữ đẩ đẩy xuố xuống hữ hữu hạ hạn Stack Alphabet Alphabet  Z   là ký tự tự đầ đầu củ của DSĐX Initial Stack Symbol Symbol qi  qi+1   q0  Q là là trạ trạng thá thái đầ đầu    F  Q là là tập cá các trạ trạng thá thái cuố cuối R/W R/W Head Head    ((Q  *  *)  (Q  *)) là là quan hệ hệ chuyể chuyển tiế tiếp gồm mộ một tậ tập hợ hợp hữ hữu hạ hạn cá các quan hệ hệ ((p, u, ), (q, )) Trướ Trước : trên đĩ đĩnh DSĐX là là  Sau : trên trên đĩ đĩnh DSĐX là là  p, q  Q ; u  * ; ,   * Có thể thể viế viết gọ gọn quan hệ hệ thà thành puq 51/77 51/77 52/77 52/77 Mô tả tả Các khá khái niệ niệm  Bộ chữ chữ đẩ đẩy xuố xuống  của ôđx :  Ngườ Ngườ i ta cũ cũng đị định nghĩ nghĩa mộ một cá cách hì hình thứ thức  Chứ Chứa tậ tập hợ hợp cá các ký tự tự sẽ đượ được đưa vàvào trong DSĐX tương tự tự các ôhh, nhưng có có mặt củ của DSĐX cácác khá khá i niệ niệm :  Không nhấ nhất thiế thiết phân biệ biệt  với  (có (có thể thể    )  Cấu hì hình  Ký tự tự Z là là ký tự tự đầ đầu hay nộ nội dung ban đầ đầu củ của DSĐX  Chuyể Chuyển tiế tiếp mộ một bướ bước  Các chuyể  Chuyể Chuyển tiế tiếp nhiề nhiều bướ bước chuyển tiế tiếp ((p, u, ), (q, )) trong  :  Ôđx đoá đoán nhậ nhận câu và vào  Tương tự tự một ôhh không đđ  NN đượ được thừ thừa nhậ nhận bở bởi ôđx  Có thêm hoạ hoạt độ động chuyể chuyển tiế tiếp củ của DSĐX :  Câu và vào bắ bắt đầ đầu bở bởi tiề tiền tố tố u : w = uw’ uw’  Ôtômat chuyể chuyển từ từ trạ trạng thá thái p sang trạ trạng thá thá i q  Phầ Phần câu  đang nằ nằm trên đỉ đỉnh củ của DSĐX  Đầu đọ đọc đọ đọc xong tiề tiền tố tố u củ của câu và vào  Thay thế thế  trên đỉnh DSĐX bở bởi câu phầ phần  53/77 53/77 54/77 54/77 9
Ôđx thừ thừa nhậ nhận câu và vào Biể Biểu diễ diễn ôtômat đẩ đẩy xuố xuống  Cho ôđx MQ, , , , Z, q0, F MQ, F và một câu và w* và o w  Cho ôtômat M  Q, , , , Z, q0, F F  Ôđx thừ thừa nhậ nhận câu w nếu quá quá trì trình đoá đoán nhậ nhận đạ đạt đế đến mộ một  Có thể thể biể biểu diễ diễn M tương tự tự các ôhh như sau : trong cá các trạ trạng thá thái kế kết thú thúc :  Bằng cá cách liệ liệt kê hế hết cá các thà thành phầ phần củ của M  Phầ Phần câu xửxử lí còn lạ lại rỗ rỗng  Dùng đồ đồ thị thị  (q0, w, Z) ├*M  p, ,   với p  F  Thự Thực tế tế, ngư ngườ ời ta thườ thường dù dùng cách biể biểu diễ diễn đồ thị thị khi số số trạ trạng thá thái củ của ôtômat không quá quá lớn  Do ôđx M không đơn đị định, nên có có thể thể có nhiề nhiều phé phép đoá đoán nhậ nhận khá khác nhau trên cù cùng mộ một câu và vào 55/77 55/77 56/77 56/77 Dùng đồ đồ thị thị biể biểu diễ diễn ôđx Ví dụ 1 : ôđx đơn đị định ngữ { anbn | n  0 } đượ  Ngôn ngữ được thừ thừa nhậ nhận bở bởi ôđx M1 :  Cho ôđx M  Q, , , , Z, q0, F F Q  { s, p, q }   { a, b }   { A }, F  { q } quy ướ ước vẽ vẽ M như sau :  gồm cá các chuyể chuyển tiế tiếp : s, a,    s, A A s, b, A A   p,  > p p là trạng thái đầu, p = q0 s, , Z Z   q,  p, b, A A  p,  p, , Z Z  q,  VVừa ừa đọ ọc vừ đđọc ừa ghi vvừa ghi nhớ nhớ nhớ Đ ọc từ Đọc ừng con ttừng con bb AA vàào DSĐX vvào DSĐX vvà à xoá xo xoáá đỉ ỉnh DSĐX đđỉnh DSĐX u, | p q (p, u, , q,     nn con con aa đã đã đọ ọc đđọc llà à concon AA a, |A b, A| q q là trạng thái cuối, q  F b, A| , Z| > s p q XXử ử lý lý câu câu rỗỗng rrỗng , Z|  annbnn  57/77 57/77 58/77 58/77 Ôđx M1 đoá nhận câu anbn đoán nhậ Cách vẽ vẽ khá khác củ của ôđx M1 và o a3b3, ôđx M1 thự  Cho câu và thực hiệ hiện đoá đoán nhậ nhận như sau : Có thể thể vẽ ôđx M 1 theo cá cách khá khác như sau : saaabbbZ ├M1 saabbbAZ ├M1 sabbbAAZ ├M1 sbbbAAAZ ghi nhớ nhớ a ├M1 pbbAAZ ├M1 pbAZ ├M1 pZ kiể kiểm tra b a, Z|AZ a, A|AAZ q thừ thừa nhậ nhận b, A| a, |A b, A| b, A| , Z| > s p q b, A| , Z| > s p q , Z| , Z|  Như vậ vậy M1 thừ thừa nhậ các câu anbn, n0, ta viế nhận cá viết L(M1) = anbn 59/77 59/77 60/77 60/77 10
Ví dụ 2 : ôđx không đơn đị định Ôđx M2 thừ thừa nhậ nhận câu abba ngữ {wwR} đượ  Ngôn ngữ được thừ thừa nhậ nhận bở bở i M2 như sau :  Cho câu và và o abba, ôđx M 2 thự thực hiệ hiện đoá đoá n nhậ nhận như sau : Q  { s, p, q}   { a, b }   { A, B } F{q} sabbaZ ├M1 sbbaAZ ├M2 sbaBAZ ghi nhớ nhớ a, a, b đã đọ đọc  chứ chứa cá các chuyể chuyển tiế tiếp : ├M2 pbaBAZ chuyể chuyển dị dịch không đơn đị định s, a,   s, A A s, ,   p,  p, b, B B  p,  ├M2 paAZ ├M2 pZ kiể kiểm tra a, b để để xoá xoá A, A, B trên DSĐX s, b,   s, B B p, a, A A  p,  p, , z z  q,  q thừ thừa nhậ nhận câu abba (thà (thành công) VVừa ừa đọ ọc vừ đđọc ừa ghi vvừa ghi nhớ nh ớ nhớ Đ ọc từ Đọc ừng con ttừng con a, a, bb A, A, BB vàào DSĐX vvào DSĐX vvà à xoá xo xoá á đỉỉnh DSĐX đđỉnh DSĐX a, |A a, A| ccác ác con a, b đã đọ ọ con a, b đã đđọcc llà à con A, con A, BB , | , Z| a, A| > s p q a, |A , Z| b, |A , Z| , | b, B| > s p q XXử ử lý , Z| Chuyể Chuyển dị Chuyển ị ch ddịch lý câu câu rỗỗng rrỗng b, |B b, B| không không đơn đơn đị ịnh đđịnh  wwRR  61/77 61/77 62/77 62/77 Ôđx M2 đoá đoán nhậ nhận câu abba thấ thất bạ bại Ví dụ ôđx kđđ hai trạ trạng thá thái  Vẫn câu và vào abba, ôđx M 2 thự thực hiệ hiện đoá đoán nhậ nhận như sau :  Có thể thể xây dự dựng ôđx M3 gồm chỉ chỉ hai trạ trạng thá thái sabbaZ ├M1 sbbaAZ ├M2 sbaBAZ ghi nhớ nhớ a, a, b đã đọ đọc M3 thừ thừa nhậ ngữ wwR với DSĐX rỗ nhận ngôn ngữ rỗng : Q  { s, p }   { a, b }   { A, B } F{p} ├M2 saBBAZ ├M2 sABBAZ hóc : không thể thể đọ đọc tiế tiếp a hay b !  gồm cá các chuyể chuyển tiế tiếp : ├M2 pABBAZ ??? cũng vẫ vẫn hó hóc : không thể thể đọ đọc tiế tiếp s, a,   s, A A  s, ,   p,  p, b, B B  p,  ôtômat không thừ thừa nhậ nhận câu abba ! s, b,   s, B B p, a, A A  p,  p, , Z Z  p,  a, |A a, A| a, |A a, A| , | , Z| > s p q , | > s p b, B| b, |B , Z| b, B| , Z| Chuyể Chuyển dị Chuyển ị ch ddịch b, |B , Z| không không đơn đơn đị ịnh đđịnh 63/77 63/77 64/77 64/77 Văn phạ phạm phi ngữ ngữ cảnh Ví dụ các VP2  Theo phân cấ cấp VP củ của Chomsky, VP phi ngữngữ cảnh (PNC) :  Dướ Dưới đây là làm ột số số VP PNC : G   N, , R, S  G1 { S  aSb |  } L(G1) = anbn, n  n0 gồm cá các sả sản xuấ xuất dạ dạng A    G2 { S  aSa | bSb |  } L(G1) = wwR )* = V*, không có với A  N,   (N) có hạn chế chế gì trên   G3 { S  aB | bA |  A  bAA | aS B  bS | aBB }  Từ G, có có thể thể đị định nghĩ nghĩa NN PNC : L(G3) gồ gồm cá các câu chứ chứa cù cùng số số chữ chữ a và chữ chữ b trong mộ một L = L(G) thứ thứ tự nào đó đó  Một NN L là là PNC nế nếu tồ tồn tạ tại mộ một VP PNC sả sản sinh ra L  G4 { S  aAS | a A  SbA | SS | ba } L(G4) = ? 65/77 65/77 66/77 66/77 11
Quan hệ hệ giữ giữa VP2 và ôđx Tính chấ chất củ của cá các ngôn ngữ ngữ PNC  Các ngôn ngữ ngữ thừ thừa nhậ nhận bở bở i cá các ôtômat đẩ đẩy xuố xuống có có thể thể  Cho L1 và L2 là hai NN PNC, ta có có các tí tính chấ chất sau : đượ được sinh bở bở i cá các văn phạ phạm PNC và và ngượ ngược lạ lại  Các ngôn ngữ ngữ sau là phi ngữ ngữ cảnh :  Định lý :  L1  L2 phé phép hợ hợp củ của hai NN PNC Một ngôn ngữ ngữ là PNC nễu  L1 . L2 phé phép ghé ghép tiế tiếp hai NN PNC ngôn ngữ ngữ đó đó đượ được thừ thừa nhậ nhận bở bởi mộ một ôtômat đẩ đẩy xuố xuống  L1* lấy bao đó đóng củ của mộ một NN PNC L = L(M) = L(G) vớ là VP2 và M là với G là là ôđx  Ngôn ngữ ngữ :  L1  L2 phé phép giao củ của hai NN PNC không hẳ hẳn là là phi ngữ ngữ cảnh !  Tuy nhiên ngôn ngữ ngữ :  LR  L2 là PNC vớ vớ i LR là NNCQ và và L2 là PNC 67/77 67/77 68/77 68/77 Vấn đề đề tạo sinh câu củ của VP PNC Ví dụ có nhiề nhiều cá cách suy dẫ dẫn  Cho VP PNC G  (N, , R, S) có có L = L(G)  Cho văn phạ phạm G :  Khi áp dụ dụng cá các sả sản xuấ xuất để để tạo sinh câu, thứ thứ t ự áp dụ dụng G { S  SS 1 | aSa 2 | bSb 3 |  4 } (đánh số số các sả sản xuấ xuất) là không quan trọ trọng :  Với câu w=aabaab,  Xuấ Xuất phá phát từ từ ký tự tự đầ đầu S, có có thể thể áp dụ dụng tuỳ tuỳ ý cá các sả sản xuấ xuất, có thể thể có 10 cá cách suy dẫ dẫn khá khác nhau để để sinh ra w : hay dù dùng cá các dẫ dẫn xuấ xuất khá khác nhau trong G đềđều có có thể thể tạo ra Cách 1 (dãy cá các SX là là 124324) : cùng mộ một câu S 1 SS 2 aSaS 4 aaS 3 aabSb 2 aabaSab 4 aabaab  Tính “phi ngữ ngữ cảnh” nh” thể thể hiệ hiện ở chỗ chỗ : mộ một ký tự tự không kếkết Cách 2 (dãy cá các SX là là 132424) : thú thúc A AN có có thể thể đự đựơc thay thế thế độ độc lậ lập vớ với cá các ký tự tự bao S 1 SS 3 SbSb 2 SbaSab 4 Sbaab 2 aSabaab 4 aabaab xung quanh (trư (trướ ớc A và và sau A), không phụ phụ thuộ thuộc và vào “ngữ ngữ cảnh” V.v... nh”  Tính không quan trọ trọng về về thứ thứ tự khi áp dụ dụng cá các sả sản xuấ xuất  Sự khá khác nhau củ của cá các cá cách suy dẫ dẫn ra w là đặ đặc trưng củ của cá các NN PNC là thứ thứ tự áp dụ dụng cá các sả sản xuấ xuất củ của G 69/77 69/77 70/77 70/77 Ví dụ hiệ hiện tượ tượng nhậ nhập nhằ nhằng Văn phạ phạm nhậ nhập nhằ nhằng  Trong NN tự tự nhiên nó nói chung, tiế tiếng Việ Việt nó nói riêng,  Cho VP PNC G : thườ thường xuyên xả xảy ra cá các hiệ hiện tượ tượng nhậ nhập nhằ nhằng  VP G đgl nhậ nhập nhằ nhằng (Ambiguous Grammar) khĩ khĩ  Nhậ Nhập nhằ nhằng về về từ loạ loại : Có hai cây phân tí tích cù cùng suy dẫ dẫn cho mộ một câu w wL(G)  Học sinh họ học sinh họ họ c  Cho L là là NN PNC :  Nhậ Nhập nhằ nhằng về về nghĩ nghĩa :  NN L đgl nhậ nhập nhằ nhằng cố cố hữu  Ông già già đi nhanh quá quá (Inherently Ambiguous Language) khĩ khĩ  Nhậ Nhập nhằ nhằng về về phá phát âm : NN L đượ được sinh bở bởi nhiề nhiều VP khá khác nhau  Bà Ba bố bốn bậ bận bá bán bá bánh L = L(G1) = L(G2) = ...  Nhậ Nhập nhằ nhằng về về tiế tiếng Việ Việt không dấ dấu : và tất cả cả các văn phạ phạm G1, G2 ... nà này đề đều nhậ nhập nhằ nhằng  Nha may Co khi Gia Lam  Cho VP PNC G nhậnhập nhằ nhằng :  Có thể thể biế biến đổ đổi G về về G’ tương đương, đương, L(G’ L(G’) = L(G), sao cho  G không còn làlà văn phạ phạm nhậ nhập nhằ nhằng 71/77 71/77 72/77 72/77 12
Ví dụ văn phạ phạm nhậ nhập nhằ nhằng Một số số ví dụ khá khác về về VP nhậ nhập nhằ nhằng  Cho VP PNC G có có các SX :  Các VP sau đây đề đều : { E  E+E 1 | E*E 2 | a 3 }  G1 { S  aSa | bSb | a | b |  }  VP G nhậ nhập nhằ nhằng vì vì có hai cây PT sinh ra câu w=a+a*a :  G2 { S  aS | Sa | a }  E 1 E+E 3 a+E 2 a+E*E 3 a+a*E 3 a+a*a  E 2 E*E 1 E+E*E 3 a+E*E 3 a+a*E 3 a+a*a 1 EE 2 EE B ài tậ Bài ập : ttập EE EE EE EE Cho ví ví ddụụ minh họ ọa tí hhọa ính nhậ ttính nhập nhằ nhập nhằng nhằng 2 ccủa ủa G11 vvà à G22 ? EE 1 EE 3 3 E E 3 E E 3 E 3 E 3 E E aa + + aa ** aa aa + + aa ** aa 73/77 73/77 74/77 74/77 Bài tậ tập chương 4 Hướ Hướng dẫ dẫn 1 1. Mô tả tả các ôhh đẩ đẩy xuố xuống thừ thừa nhậ nhận cá các NN sau đây :  Mô tả tả các ôhh đẩ đẩy xuố xuống thừ nhận NN L = anbncm thừa nhậ a) anbncm  Vẽ Ođx thừ nhận anbn (đã thừa nhậ (đã biế biết cá cách vẽ vẽ) b) anbmcn  Vẽ tiế tiếp Ođx chỉ đọc cm (không cầ chỉ đọ cần ghi nhớ nhớ vào DSĐX) DSĐX) 2. Tìm văn phạ phạm PNC sả sản sinh cá các ngôn ngữ ngữ sau đây : a) anbncm b) anbmcn 3. Chứ Chứng minh rằ rằng NN { aibjck | i  j hoặ hoặc i  k } là là PNC Phầ Phần bù bù của ngôn ngữ ngữ này cũ cũng làlà PNC ? Gợi ý : hộ hội củ của cá các ngôn ngữ ngữ PNC cũ cũng là là PNC 4. Chứ rằng NN { an | n là Chứng minh rằ là số nguyên tố tố } không là là PNC 75/77 75/77 76/77 76/77 Hướ Hướng dẫ dẫn 2 Tìm văn phạ phạm PNC sả ngữ anbncm sản sinh ngôn ngữ Ý tưở tưởng : vậ vận dụ dụng VP G’ L(G’ ) = anbn sau đó G’ mà L(G’ đó thêm cm  Xây dự dựng G’ G’ { S  aSb |  } có L(G’) = anbn có L(G’  Thêm cm để để nhậ nhận đượ được G như sau : G { S  AB A  aAb |  B  cB | } }  Quả thật, L(G) = anbncm Quả thậ 77/77 77/77 13