Đề Thi Môn Ngôn Ngữ Hình Thức Và Otomat - TaiLieu.VN

Trang chủ » đề Thi Ngôn Ngữ Hình Thức Và Otomat » Đề Thi Môn Ngôn Ngữ Hình Thức Và Otomat - TaiLieu.VN

Có thể bạn quan tâm

OPTADS360 intTypePromotion=1 zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn tailieu.vn NÂNG CẤP Đăng Nhập | Đăng Ký Chủ đề »
  • Chứng chỉ CCNA
  • Chứng chỉ Microsoft
  • HOT
    • FORM.07: Bộ 125+ Biểu Mẫu Báo Cáo...
    • CEO.27: Bộ Tài Liệu Dành Cho StartUp...
    • CMO.03: Bộ Tài Liệu Hệ Thống Quản Trị...
    • FORM.08: Bộ 130+ Biểu Mẫu Thống Kê...
    • CEO.24: Bộ 240+ Tài Liệu Quản Trị Rủi...
    • LV.26: Bộ 320 Luận Văn Thạc Sĩ Y...
    • FORM.04: Bộ 240+ Biểu Mẫu Chứng Từ Kế...
    • TL.01: Bộ Tiểu Luận Triết Học
    • CEO.29: Bộ Tài Liệu Hệ Thống Quản Trị...
    LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Tài...
TUYỂN SINH YOMEDIA ADSENSE Trang Chủ » Công Nghệ Thông Tin » Chứng chỉ quốc tế Đề thi môn ngôn ngữ hình thức và otomat

Chia sẻ: Hồ Viết Dũng | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST Báo xấu 1.109 lượt xem 160 download Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giả sử L là ngôn ngữ chính quy. Khi đó sẽ tồn tại một DFA M chấp nhận cho ngôn ngữ L. Gọi n là số trạng thái của DFA M đó. Xét chuỗi z = anb1c1dn . Ta có độ dài của chuỗi z là: |z| = 2n + 2 n . Theo bổ đề bơm, ta có thể đặt z = uvw , trong đó u, v, w là các chuỗi con của z với điều kiện như sau: |uv| ≤ n, |v| ≥ 1 và với mọi i ≥ 0 ta có uviw ϵ L

AMBIENT/ Chủ đề:
  • thủ thuật máy tính
  • công nghệ thông tin
  • tin học
  • quản trị mạng
  • computer network

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

Đăng nhập để gửi bình luận! Lưu

Nội dung Text: Đề thi môn ngôn ngữ hình thức và otomat

  1. TRƯỜNG ĐẠI HỌC CẦN THƠ Đề thi môn: TIN HỌC LÝ THUYẾT KHOA CNTT & TRUYỀN THÔNG Lớp: TIN HỌC K.29 Lần 2 – Học kỳ 1 – Năm học 06 - 07 Thời gian làm bài: 120 phút NỘI DUNG ĐỀ Câu 1 (1.0 điểm): Áp dụng bổ đề bơm, bạn hãy chứng minh ngôn ngữ sau đây không là ngôn ngữ i j j i chính quy: L = {a b c d | i, j ≥ 1} Câu 2 (2.0 điểm): Bạn hãy tìm một DFA tương đương với NFA sau: b a start a, b a, b q1 q2 q3 Câu 3 (1.5 điểm): Bạn hãy vẽ một automata hữu hạn chấp nhận cho ngôn ngữ được ký hiệu bởi biểu thức chính quy sau: ( (a + ab) b* a )* Câu 4 (1.0 điểm): Bạn hãy chuyển văn phạm sau đây về dạng chuẩn Chomsky (cho biết rằng văn phạm không có ký hiệu vô ích): S → 0SA | 1SB | 01 A → 0A | 0 B → 1B | 1 Câu 5 (1.0 điểm): Bạn hãy chuyển văn phạm sau đây về dạng chuẩn Greibach: S → SA | 0 A → AS | 1 Câu 6 (1.5 điểm): Bạn hãy thiết kế một PDA tương đương với văn phạm phi ngữ cảnh có tập luật sinh như sau: S → 0SA | 1SB | 0 | 1 A → 0A | 0 B → 1B | 1 Câu 7 (2.0 điểm): Bạn hãy thiết kế một máy Turing để thực hiện phép nhân 3 một số nguyên n dương (n > 0). Chú ý: trên băng nhập đã được cho trước một ký hiệu X ở đầu băng. Đầu đọc đang chỉ tại vị trí đầu tiên của băng nhập (ký hiệu X). Ví dụ: thực hiện phép nhân 3 cho số n = 3 (3 * 3 = 9) Đầu vào (input): X000 Kết quả (output): 000000000 (9 số 0) - HẾT - ĐHCT, ngày 02 tháng 02 năm 2007 Giáo viên ra đề Nguyễn Thanh Bình
  2. ĐÁP ÁN Câu 1 (1.0 điểm): Áp dụng bổ đề bơm, bạn hãy chứng minh ngôn ngữ sau đây không là ngôn ngữ i j j i chính quy: L = {a b c d | i, j ≥ 1} Giả sử L là ngôn ngữ chính quy. Khi đó sẽ tồn tại một DFA M chấp nhận cho ngôn ngữ L. Gọi n là số trạng thái của DFA M đó. Xét chuỗi z = anb1c1dn . Ta có độ dài của chuỗi z là: |z| = 2n + 2 > n . Theo bổ đề bơm, ta có thể đặt z = uvw , trong đó u, v, w là các chuỗi con của z với điều kiện như sau: |uv| ≤ n, |v| ≥ 1 và với mọi i ≥ 0 ta có uviw ϵ L Do uv là chuỗi tiền tố của chuỗi z = anb1c1dn và uv có độ dài chuỗi không lớn hơn n nên uv chỉ chứa ký tự a. Vậy v cũng chỉ chứa ký hiệu a (và có ít nhất một ký hiệu a). Xét chuỗi uv2w, ta thấy chuỗi uv2w so với chuỗi uvw = z = anb1c1dn có nhiều hơn một chuỗi v. Mặt khác, trong chuỗi v chỉ chứa ký hiệu a, nên ta suy ra trong chuỗi uv2w sẽ có số ký hiệu a lớn hơn n (và số ký hiệu d không đổi là n). Vậy trong chuỗi uv2w sẽ có số ký hiệu a nhiều hơn ký hiệu d, hay chuỗi uv2w không thuộc ngôn ngữ L. Vậy giả thiết L là ngôn ngữ chính quy sai, hay L không là ngôn ngữ chính quy. Câu 2 (2.0 điểm): Bạn hãy tìm một DFA tương đương với NFA sau: b a start a, b a, b q1 q2 q3 DFA tương đương: b start b b [q 1] [q 1, q 2] [q 1,q 2,q 3] a a a a a [q 2] [q 2, q 3] b b [q 3] Câu 3 (1.5 điểm): Bạn hãy vẽ một automata hữu hạn chấp nhận cho ngôn ngữ được ký hiệu bởi biểu thức chính quy sau: ( (a + ab) b* a )* Cách 1: b a start q1 q2 a a b q3
  3. Cách 2: sử dụng cách vẽ đã học theo định lý 3.3 – Giáo trình Tin học lý thuyết – MSc. Võ Huỳnh Trâm – Đại học Cần Thơ – 2003. Câu 4 (1.0 điểm): Bạn hãy chuyển văn phạm sau đây về dạng chuẩn Chomsky (cho biết rằng văn phạm không có ký hiệu vô ích): S → 0SA | 1SB | 01 A → 0A | 0 B → 1B | 1 Bước 1: bỏ qua (vì đề bài đã cho biết văn phạm không có ký hiệu vô ích, và nhìn vào văn phạm ta thấy không có luật sinh ε hay luật sinh đơn vị). Bước 2: thay thế các ký hiệu kết thúc ở các luật sinh có độ dài vế phải lớn hơn 1 bằng các biến tương ứng. S → C0SA | C1SB | C0C1 A → C0A | 0 B → C1B | 1 C0 → 0 C1 → 1 Bước 3: thay thế luật sinh có độ dài vế phải lớn hơn 2 bằng các luật sinh có độ dài vế phải bằng 2. S → C0D0 | C1D1 | C0C1 A → C0A | 0 B → C1B | 1 C0 → 0 C1 → 1 D0 → SA D1 → SB Câu 5 (1.0 điểm): Bạn hãy chuyển văn phạm sau đây về dạng chuẩn Greibach: S → SA | 0 A → AS | 1 Bước 1: văn phạm đã ở dạng chuẩn Chomsky. Bước 2: thay biến S bằng biến A1, biến A bằng biến A2. Ta có tập luật sinh: A1 → A1A2 | 0 A2 → A2A1 | 1 Bước 3: khử tính đệ quy trái ở tập luật sinh trên: A1 → 0 | 0B1 A2 → 1 | 1B2 B1 → A2 | A2B1 B2 → A1 | A1B2 Bước 4: các luật sinh từ biến A1 và A2 đã thỏa dạng chuẩn Greibach.
  4. Bước 5: chuyển các luật sinh từ biến B1 và B2 về dạng chuẩn Greibach. A1 → 0 | 0B1 A2 → 1 | 1B2 B1 → 1 | 1B2 | 1B1 | 1B2B1 B2 → 0 | 0B1 | 0B2 | 0B1B2 Tập luật sinh trên đã thỏa dạng chuẩn Greibach. Câu 6 (1.5 điểm): Bạn hãy thiết kế một PDA tương đương với văn phạm phi ngữ cảnh có tập luật sinh như sau: S → 0SA | 1SB | 0 | 1 A → 0A | 0 B → 1B | 1 Xây dựng PDA M như sau: M ({q}, {0, 1}, {S, A, B}, δ, q, S, Ø) Với các hàm chuyển δ như sau: δ (q, 0, S) = { (q, SA), (q, ε) } δ (q, 1, S) = { (q, SB), (q, ε) } δ (q, 0, A) = { (q, A), (q, ε) } δ (q, 1, B) = { (q, B), (q, ε) } Câu 7 (2.0 điểm): Bạn hãy thiết kế một máy Turing để thực hiện phép nhân 3 một số nguyên n dương (n > 0). Chú ý: trên băng nhập đã được cho trước một ký hiệu X ở đầu băng. Đầu đọc đang chỉ tại vị trí đầu tiên của băng nhập (ký hiệu X). Ý tưởng: a) Đổi X thành B (để làm chốt chặn ở đầu chuỗi) b) Gặp số 0 đầu tiên đổi thành 1 (đổi thành 1 để đánh dấu số 0 đó đã được xét) c) Di chuyển đến cuối chuỗi, đổi 2 ký hiệu B thành ký hiệu 2. d) Di chuyển về đầu chuỗi cho đến khi gặp ký hiệu 1, dịch phải. 1. Nếu ký hiệu tiếp theo là 0, lặp lại bước b. 2. Nếu ký hiệu tiếp theo là 2 thì di chuyển về cuối chuỗi (cho đến khi gặp B), sau đó dịch trái đổi các ký hiệu 1 và 2 thành 0. Gặp ký hiệu B ở đầu chuỗi thì kết thúc. (0, 0, R) (0, 0, L) (2, 2, R) (2, 2, L) start (X, B, R) (0, 1, R) (B, 2, R) (B, 2, L) q0 q1 q2 q3 q4 (1, 1, R) (2, 2, R) (2, 0, L) (1, 0, L) (2, 2, R) (B, B, L) q5 q6 q7 (B, B, Ø) -- HẾT --
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

  • BÀI TẬP THỰC HÀNH LẬP TRÌNH C CƠ BẢN_SỐ 2

    doc 2 p | 341 | 66

  • Đề thi môn lập trình C trên Windows

    doc 17 p | 250 | 64

  • Cơ sở Toán trong kỹ thuật lập trình: Phần 1

    pdf 183 p | 185 | 62

  • Đề thi cuối kỳ môn Phân tích thiết kế hệ thống hướng đối tượng - ĐH Văn Lang

    pdf 4 p | 576 | 43

  • Đề cương môn học: Công nghệ .NET

    pdf 125 p | 272 | 31

  • Đề kiểm tra môn C++

    doc 15 p | 183 | 14

  • Bài giảng Nhập môn Công nghệ phần mềm: Chương 5 - ĐH Bách khoa TP HCM

    pdf 14 p | 121 | 12

  • Bài giảng Cơ sở dữ liệu: Chương 0 - ThS. Nguyễn Thị Như Anh

    pdf 10 p | 53 | 5

  • Bài giảng Lập trình hướng đối tượng: Hướng dẫn môn học - Trần Thị Anh Thi

    pdf 3 p | 64 | 3

  • Bài giảng Đặc tả hình thức: Chương 0 - Nguyễn Thị Minh Tuyền

    pdf 12 p | 67 | 3

Thêm tài liệu vào bộ sưu tập có sẵn: Đồng ý Thêm vào bộ sưu tập mới: *Tên bộ sưu tập Mô Tả: *Từ Khóa: Tạo mới Báo xấu
  • Hãy cho chúng tôi biết lý do bạn muốn thông báo. Chúng tôi sẽ khắc phục vấn đề này trong thời gian ngắn nhất.
  • Không hoạt động
  • Có nội dung khiêu dâm
  • Có nội dung chính trị, phản động.
  • Spam
  • Vi phạm bản quyền.
  • Nội dung không đúng tiêu đề.
Hoặc bạn có thể nhập những lý do khác vào ô bên dưới (100 ký tự): Vui lòng nhập mã xác nhận vào ô bên dưới. Nếu bạn không đọc được, hãy Chọn mã xác nhận khác.. Đồng ý LAVA AANETWORK THÔNG TIN
  • Về chúng tôi
  • Quy định bảo mật
  • Thỏa thuận sử dụng
  • Quy chế hoạt động
TRỢ GIÚP
  • Hướng dẫn sử dụng
  • Upload tài liệu
  • Hỏi và đáp
HỖ TRỢ KHÁCH HÀNG
  • Liên hệ
  • Hỗ trợ trực tuyến
  • Liên hệ quảng cáo
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

Đang xử lý... Đồng bộ tài khoản Login thành công! AMBIENT

Từ khóa » đề Thi Ngôn Ngữ Hình Thức Và Otomat