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

Mạng xã hội chia sẻ tài liệu Upload Đăng nhập Nâng cấp VIP Trang chủ » Công Nghệ Thông Tin » Chứng chỉ CNTT quốc tế4 trang 1552 lượt xem 1610Đề thi môn ngôn ngữ hình thức và otomat

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

Chủ đề:

dung78pro

Ngôn ngữ hình thức

Tài liệu Ngôn ngữ hình thức

SaveLikeShareReport Download AI tóm tắt /4 TRƯỜNG ĐẠI HỌC CẦN THƠĐề thi môn: TIN HỌC LÝ THUYẾTKHOA CNTT & TRUYỀN THÔNGLớp: TIN HỌC K.29Lần 2 – Học kỳ 1 – Năm học 06 - 07Thời gian làm bài: 120 phútNỘ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ữ chính quy:L = {ai bj cj di | 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: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 | 01A → 0A | 0B → 1B | 1Câ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 | 0A → AS | 1Câ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 | 1A → 0A | 0B → 1B | 1Câ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):X000Kết quả (output):000000000(9 số 0)- HẾT -ĐHCT, ngày 02 tháng 02 năm 2007Giáo viên ra đềNguyễn Thanh Bìnhq1q2q3a, baa, bstartb ĐÁP ÁNCâ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ữ chính quy:L = {ai bj cj di | 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 ϵ LDo 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:DFA tương đương: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: start[q1][q2][q3][q1, q2][q2, q3][q1,q2,q3]ababbabaabq1q2q3a, baa, bstartbq1startq2q3bbaaa 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 | 01A → 0A | 0B → 1B | 1Bướ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 | C0C1A → C0A | 0B → C1B | 1C0 → 0C1 → 1Bướ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 | C0C1A → C0A | 0B → C1B | 1C0 → 0C1 → 1D0 → SAD1 → SBCâ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 | 0A → AS | 1Bướ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 | 0A2 → A2A1 | 1Bước 3: khử tính đệ quy trái ở tập luật sinh trên:A1 → 0 | 0B1A2 → 1 | 1B2B1 → A2 | A2B1B2 → A1 | A1B2Bước 4: các luật sinh từ biến A1 và A2 đã thỏa dạng chuẩn Greibach. Bước 5: chuyển các luật sinh từ biến B1 và B2 về dạng chuẩn Greibach.A1 → 0 | 0B1A2 → 1 | 1B2B1 → 1 | 1B2 | 1B1 | 1B2B1B2 → 0 | 0B1 | 0B2 | 0B1B2Tậ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 | 1A → 0A | 0B → 1B | 1Xâ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.-- HẾT --q0q1q7(X, B, R)startq5q6q2q3q4(0, 1, R)(0, 0, R)(B, 2, R)(B, 2, L)(0, 0, L)(2, 2, L)(1, 1, R)(2, 2, R)(2, 2, R)(2, 2, R)(B, B, L)(2, 0, L)(1, 0, L)(B, B, Ø)

Tài liệu liên quan

Đề cương chi tiết luận văn Thạc sĩ: Nhận dạng văn bản một số ngôn ngữ La Tinh

W 8 trang

Cách đổi font từ Vntime sang Time New Roman

W 4 trang

Chương 2: Liên kết các ngôn ngữ bậc cao với ASM

10 trang

Khái niệm về ontology

9 trang

Lý thuyết và bài tập ngôn ngữ lập trình C++

268 trang

Biểu diễn tri thức sử dụng mạng ngữ nghĩa (Ths. Đinh Nguyễn Anh Dũng - GS. TSKH. Hoàng Kiếm)

W 10 trang

Font và Typeface

14 trang

Ám màu - Những kiến thức và kinh nghiệm của bản thân

21 trang

Chapter 1 : Các khái niệm cơ bản về ngôn ngữ C

W 9 trang

NGÔN NGỮ và PHƯƠNG PHÁP DỊCH - Chương 5: Sinh mã

122 trang

Tài liêu mới

Bài tập Tin học ứng dụng

W 4 trang

Đề thi Tin học văn phòng dành cho thi tuyển công chức

12 trang

Đề thi Chứng chỉ B Tin học Quốc gia

3 trang

Đề thi Tin học trình độ A môn Word

1 trang

Đề thi Tin học trình độ A môn Powerpoint

1 trang

Đề thi sát hạch kỹ năng ứng dụng công nghệ thông tin cơ bản năm 2024 (Thực hành)

2 trang

AI tóm tắt

- Giúp bạn nắm bắt nội dung tài liệu nhanh chóng!

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

Zalo/Tel:

093 303 0098

Email:

[email protected]

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok

Chịu trách nhiệm nội dung: Nguyễn Công Hà Doanh nghiệp quản lý: Công ty TNHH Tài Liệu trực tuyến Vi Na - GCN ĐKDN: 0307893603 Địa chỉ: 54A Nơ Trang Long, P. Bình Thạnh, TP.HCM - Điện thoại: 0283 5102 888 - Email: [email protected]ấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015