Môn Lý Thuyết Ngôn Ngữ Hình Thức Và Automata - Tài Liệu đại Học

Tài liệu đại học Toggle navigation

• Miễn phí (current)
• Danh mục
  • Khoa học kỹ thuật
  • Công nghệ thông tin
  • Kinh tế, Tài chính, Kế toán
  • Văn hóa, Xã hội
  • Ngoại ngữ
  • Văn học, Báo chí
  • Kiến trúc, xây dựng
  • Sư phạm
  • Khoa học Tự nhiên
  • Luật
  • Y Dược, Công nghệ thực phẩm
  • Nông Lâm Thủy sản
  • Ôn thi Đại học, THPT
  • Đại cương
  • Tài liệu khác
  • Luận văn tổng hợp
  • Nông Lâm
  • Nông nghiệp
  • Luận văn luận án
  • Văn mẫu
• Luận văn tổng hợp

1. Home
2. Luận văn tổng hợp
3. Môn Lý Thuyết ngôn ngữ hình thức và automata

Trich dan Môn Lý Thuyết ngôn ngữ hình thức và automata - Pdf 44

Trang 1 Đại học Quốc gia Tp. Hồ Chí Minh Đề Thi Học Kỳ 1/2003 Trường Đại Học Bách Khoa Môn Lý Thuyết Automat&NNHT - 501038 Khoa Công Nghệ Thông Tin Ngày 09/01/2004 - Thời gian 120 phút ---oOo--- ĐỀ 0001 Họ tên: .......................................................... MSSV:....................... Lưu ý: 1. Sinh viên trả lời vào PHIẾU TRẢ LỜI TRẮC NGHIỆM. Sinh viên phải điền đầy đủ các thông tin vào PHIẾU TRẢ LỜI TRẮC NGHIỆM chú ý MSMH: 501038. 2. Sinh viên phải điền họ tên và MSSV của mình vào đề thi. Sinh viên NỘP lại đề thi. 3. Đề gồm 4 trang, 50 câu. 4. Sinh viên chỉ được phép sử dụng tài liệu trong ba tờ giấy khổ A4. 5. Sinh viên chú ý một số kí hiệu và từ viết tắt. na(w) là kí hiệu biểu diễn số kí hiệu a trong chuỗi w. Dành cho câu 1 đến câu 3: Cho các ngôn ngữ sau (chú ý n, m nguyên không âm): L1 = {w ∈ {a, b, c}*: na(w) = nb(w) + nc(w)} L2 = {aS → aSb | aS | a (C).S → aSb | aS | λ (D).S → aSb | SS | a (E). Tất cả đều sai. 3. Văn phạm nào sinh ra L3 (A). S → A | B A → aA | aX B → Bb | Xb X → aXb | λ (B). S → A | B A → aAb | a B → aAb | b (C).S → aS | Sb | a | b (D). Cả A, B, C đúng (E). Tất cả đều sai. Dành cho câu 4 đến câu 8 7: Cho văn phạm G sau: E → EE* | EE+ | a | b. G có tập kí hiệu kết thúc là {a, b, *, +} 4. Chuỗi nào sau đây được sinh ra bởi G (A). a+b*a (B). aab++a* (C). a+bb* (D).ab*bb+ (E). Tất cả đều sai. 5. Chuỗi nào sau đây được sinh ra bởi G (A). a++b* (B). ab++a* (C). ab+ba* (D).b*ab+ (E). Tất cả đều sai. 6. Dãy dẫn xuất của chuỗi ab+ba*+ trong G bao gồm bao nhiêu bước dẫn xuất (bao nhiêu lần áp dụng luật sinh) (w)} (C).{w ∈ {a, b}*: na(w) = nb(w) + 1} (D). {w∈{a, b}*: nb(w) ≤ na(w) ≤ nb(w) + 2} (E). Tất cả đều sai. 12. Cho văn phạm S → aSa | bSb | a | b | λ. Tìm ngôn ngữ tương ứng (A). {wwR : w ∈{a, b}*} (B). {w ∈{a, b}* : w = wR} (C).Trang 2 14. Văn phạm S → aSbS | bSaS | λ nhập nhằng trên chuỗi nào sau đây (A). aabb (B). abba (C). abab (D). Cả A, B, C đúng. (E). Tất cả đều sai. 15. Văn phạm S → aSbS | bSaS | a | λ nhập nhằng trên chuỗi nào sau đây (A). aaba (B). aab (C). aaabb (D). Cả A, B, C đúng. (E). Tất cả đều sai. 16. Văn phạm nào sau đây KHÔNG nhập nhằng (A). S → aSb | bSa | SS | a (B). S → aSbS | bSaS | a | λ (C).S → aS | aSb | b (D). Cả A, B, C đúng. (E). Tất cả đều sai. Dành cho câu 17 đến câu 19: Cho văn phạm G sau S → aAAB | bC A → bB | λ B → Aa | A | λ C → bA | B 17. Sau khi loại bỏ luật sinh - λ theo giải thuật đã học, biến S có bao nhiêu luật sinh (hay S có bao nhiêu vế phải) (A). 8 (B). 9 (C). 7 (D). 6 (E). Tất cả đều sai. 18. Sau khi loại bỏ luật sinh - λ theo giải thuật đã học, văn phạm có bao nhiêu luật sinh (A). 18 (B). 14 (C). 15 (D). 16 (E). 17 19. Sau khi loại bỏ luật sinh - λ và luật sinh đơn vị theo giải thuật đã học, biến C có bao nhiêu luật sinh (A). 8 (B). 7 (C). 6 (D). 5 (E). 4 Dành cho câu 20 và 21: Cho văn phạm G sau S → aSbS | acS | bdS | e. Biến đổi G thành G’ tương đương có dạng chuẩn Chomsky theo giải thuật đã học. 20. Trong G’ biến S có bao nhiêu luật sinh (A). 4 (B). 5 (C). 6 (D). 7 (E). Tất cả đều sai. 22)} (B). {A(3→A11A22)} (C).{A(4→B11A22)} (D).{B(6→A11S22)} (E). Tất cả đều sai. (D).{B(6→A11S23)} (E). Tất cả đều sai. 27. Tập V24 có chứa phần tử nào sau đây (A). {S(2→B22S34)} (B). {A(4→B22A3424)} (B). {S(2→B12S34)} (C).{A(3→A11A24)} (D).{B(6→A12S34)} (E). Tất cả đều sai. bm: n > m > 0} L4 = {an + mbncm: n, m > 0} 29. Npda nào sau đây chấp nhận đúng ngôn ngữ L1 (A). δ(q0, a, z) = (q0, az) δ(q0, a, a) = (q0, aa) δ(q0, b, a) = (q1, λ) δ(q1, λ, z) = (qf, z) (B). δ(q0, a, z) = (q0, az) δ(q0, a, a) = (q0, aa)δ(q0, b, a) = (q1, λ) δ(q1, b, a) = (q1, λ) δ(q1, b, z) = (q20, az) δ(q0, a, a) = (q0, aa)δ(q0, b, a) = (q1, λ) δ(q1, b, a) = (q1, λ) δ(q1, b, z) = (q2, bz) δ(q2, b, b) = (q2, bb)δ(q2, c, b) = (q, b, a) = (q1, λ) δ(q1, b, z) = (q2, bz) δ(q0, b, z) = (q2, bz) δ(q2, b, b) = (q2, bb) δ(q2, c, b) = (q3, λ) δ(q3, c, b) = (q3, λ) δ(q3, b, a) = (q1, λ) δ(q1, b, z) = (q2, bz) δ(q0, b, z) = (q2, bz) δ(q2, b, b) = (q2, bb) δ(q0, λ, a) = (qf, a) δ(q1, λ, a) = (qf, a) δ(q21, b, z) = (qf, bz) δ(qf, b, b) = (qf, bb) (C).δ(q0, a, z) = (q0, az) δ(q0, a, a) = (q0, aa)δ(q0, b, a) = (q1, λ) δ(q1, b, a) = (q1, λ) 0, az) δ(q0, a, a) = (q0, aa) δ(q0, b, a) = (q1, λ) δ(q1, b, a) = (q1, λ) δ(q1, b, z) = (q2, bz) δ(q0, b, z) = (q2, bz) δ(q2, b, b) = (q, b, z) = (q0, bz) δ(q0, a, a) = (q0, aa) δ(q0, b, a) = (q0, λ) δ(q0, a, b) = (q0, λ) δ(q0, b, b) = (q0, bb) δ(q0, λ, z) = (qf, z) δ(q03 = L1 ∪ L2 (D). L4 = {w ∈ {a, b}*: na(w) ≥ nb(w)} (E). Tất cả đều sai. Dành cho câu 36: Xét ngôn ngữ L = {anbkcnk : n, k ≥ 0}. Giả sử L phi ngữ cảnh, rõ ràng L vô hạn nên có thể áp dụng bổ đề bơm. Gọi m là hằng số nguyên dương được chỉ ra trong bổ đề bơm, chuỗi w = 2mmmcba ∈ L thỏa | w | ≥ m. Do đó có thể viết w = uvxyz với |vxy| ≤ m, vy không rỗng, và uv = uv2xy2z có na(w2) × nb(w2) > nc(w2). Do đó uv2xy2z ∉ L. Mâu thuẫn. [4] Nếu vy chứa c, chọn i = 2, ta được chuỗi w2 = uv2xy2z có na(w{anbmcn: n ≤ m ≤ 2n} (D). Cả A, B đúng. (E). Cả A, B, C đúng. 38. Ngôn ngữ nào sau đây KHÔNG phi ngữ cảnh (A). {ww: w ∈ {a, b}*} (B). {wcw: w ∈ {a, b}*} (C).{anbmcman} (D). Cả A, B đúng. (E). Cả A, B, C đúng. 39. Ngôn ngữ nào sau đây KHÔNG phi ngữ cảnh đơn định (A). {wwR: w∈ {a, b}*} (B). {w∈ {a, b}*1, a) = (q1, a, R) δ(q1, y) = (q1, y, R) δ(q1, b) = (q2, y, L) δ(q2, y) = (q2, y, L) δ(q2, a) = (q2, a, L) δ(q2, x) = (q0, x, R) δ(qbb (B). xaaq1yb (C). xaq2ayb (D).q2xaayb (E). xq2aayb 44. Máy Turing trên chấp nhận đúng ngôn ngữ nào sau đây (A). {anbm : n > m} (B). {anbm : n < m} (C). {anbm : n ≠ m} (D). {w ∈ {a, b}*: na(w) ≠ nb(w)} (C).L1 ∩ 3L là PNC. (D). Cả A, B, C đúng. (E). Chỉ có B, C đúng. 48. Một chuỗi w KHÔNG được chấp nhận bởi một máy Turing M nếu (A). M dừng ở một trạng thái không kết thúc. (B). M không bao giờ dừng. (C). M chưa duyệt hết chuỗi ngõ nhập ở trên băng. (D). Cả A, B đúng. (E). Cả A, B, C đúng. 49. Từ việc nghiên cứu máy Turing chúng ta có thể phát biểu (A). Bất kỳ giải thuật nào cũng tồn tại máy Turing để thực hiện nó. (B). Số lượng máy Turing là vô hạn đếm được. (C). Bất kỳ ngôn ngữ nào cũng tồn tại máy Turing chấp nhận nó. (D). Cả A, B, C đúng (E). Chỉ có A, B đúng. 50. Từ các lớp ngôn ngữ đã nghiên cứu chúng ta có thể phát biểu (PNC: phi ngữ cảnh, CNC: cảm ngữ cảnh) (A). Tồn tại một ngôn ngữ CNC mà không PNC. (B). Lớp ngôn ngữ đệ qui và CNC là đồng nhất. (C). Lớp ngôn ngữ khả liệt kê đệ qui bao trùm mọi ngôn ngữ. (D). Lớp ngôn ngữ PNC chỉ bao gồm hai lớp PNC (E). Tất cả đều sai. tuyến tính và PNC đơn định. Trang 5 ĐÁP ÁN 1 D 11 B 21 D 31 B 41 B 2 B 12 D 22 C 32 D 42 B 3 A 13 C 23 D 33 E 43 E 4 B 14 C 24 E 34 A 44 C 5 E 15 E 25 A 35 D 45 D Tải File Word Nhờ tải bản gốc Tài liệu, ebook tham khảo khác

• Giáo trình : Lý thuyết, ngôn ngữ hình thức và Otômat
• Lý thuyết và bài tập môn di truyền học 2
• Bài tập lý thuyết ngôn ngữ hình thức và automata
• Bài giảng môn học lý thuyết automata và ngôn ngữ hình thức
• Môn Lý Thuyết ngôn ngữ hình thức và automata
• Vấn đề hạt Higgs, lý thuyết và thực nghiệm
• Hình thành và phát triển năng lực trí tuệ chung cho học sinh THPT qua giảng dạy ngôn ngữ lập trình pascal
• Hình thành và phát triển năng lực trí tuệ chung cho học sinh THPT qua giảng dạy ngôn ngữ lập trình pascal
• Ngôn ngữ lập trình Visual Basic và ứng dụng vào việc xây dựng hệ thống thông tin quản lý bán hàng
• Nhập môn về văn phạm và ngôn ngữ hình thức
• Đề án Lí luận về lạm phát tiền tệ. Thực trạng và sự vận dụng ở Việt Nam
• Đề án Chuyển dịch cơ cấu kinh tế ngành nhằm tạo việc làm cho ngư dân ven biển miền Trung giai đoạn 2006 - 2010
• Nghiên cứu nhu cầu và khó khăn của thành viên kênh nhằm đưa ra giải pháp nâng cao hoạt động của kênh phân phối tại công ty Bia Việt Hà
• Trình bày về nội dung, chức năng công việc của mức phiên trong mô hình mạng OSI
• Nghiên cứu về kinh tế thị trường định hướng xã hội chủ nghĩa ở Việt Nam
• Phương hướng phát triển kinh tế-xã hội tỉnh Hưng Yên đến năm 2010 và một số định hướng đến năm 2020
• Đẩy mạnh cổ phần hoá một bộ phận doanh nghiệp nhà nước của Việt nam hiện nay
• Tiềm năng phát triển tài nguyên du lịch ở địa bàn Thừa Thiên Huế
• Đặc điểm nguồn khách và phương hướng, biện pháp nhằm thu hút khách du lịch tại chi nhánh OSC travel Hà Nội
• Nâng cao chất lượng nguồn nhân lực trong quá trình gia nhập WTO

Hệ thống tự động tổng hợp link tải tài liệu, ebook miễn phí cho các bạn sinh viên tham khảo.

Học thêm

• Nhờ tải tài liệu
• Từ điển Nhật Việt online
• Từ điển Hàn Việt online
• Văn mẫu tuyển chọn
• Tài liệu Cao học
• Tài liệu tham khảo
• Truyện Tiếng Anh

Music ♫

Copyright: Tài liệu đại học ©

Top