Bài tập ngôn ngữ hình thức có lời giải

     

Giả sử L là ngôn từ chính quy.Bạn sẽ xem: bài tập ngôn ngữ hiệ tượng có lời giải

khi đó sẽ trường tồn một DFA M gật đầu cho ngôn từ L.Gọi n là số trạng thái của DFA M đó.Xét chuỗi z = anb1c1dn . Ta tất cả độ nhiều năm của chuỗi z là: |z| = 2n + 2 n . Theo té đề bơm, ta cóthể để z = uvw , trong các số ấy u, v, w là những chuỗi bé 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


Bạn đang xem: Bài tập ngôn ngữ hình thức có lời giải

*

TRƯỜNG ĐẠI HỌC CẦN THƠ Đề thi môn: TIN HỌC LÝ THUYẾTKHOA CNTT và TRUYỀN THÔNG Lớp: TIN HỌC K.29 Lần 2 – học tập kỳ 1 – Năm học 06 - 07 thời hạn làm bài: 120 phút NỘI DUNG ĐỀCâu 1 (1.0 điểm): Áp dụng vấp ngã đề bơm, chúng ta hãy minh chứng ngôn ngữ sau đây không là ngôn từ i j j ichính quy: L = a b c d 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 q.1 q2 q3Câu 3 (1.5 điểm): bạn hãy vẽ một automata hữu hạn đồng ý cho ngữ điệu được ký kết hiệu bởibiểu thức chủ yếu quy sau: ( (a + ab) b* a )*Câu 4 (1.0 điểm): bạn hãy chuyển văn phạm dưới đây về dạng chuẩn chỉnh Chomsky (cho biết rằng vănphạm không có ký hiệu vô ích): S → 0SA | 1SB | 01 A → 0A | 0 B → 1B | 1Câu 5 (1.0 điểm): các bạn hãy chuyển văn phạm dưới đây về dạng chuẩn chỉnh Greibach: S → SA | 0 A → AS | 1Câu 6 (1.5 điểm): chúng ta hãy xây cất một PDA tương tự với văn phạm phi ngữ cảnh bao gồm tập luậtsinh như sau: S → 0SA | 1SB | 0 | 1 A → 0A | 0 B → 1B | 1Câu 7 (2.0 điểm): các bạn hãy thiết kế một đồ vật Turing để tiến hành phép nhân 3 một số nguyên ndương (n > 0). Chú ý: bên trên băng nhập đang được cho trước một ký hiệu X sống đầ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ụ: tiến hành phép nhân 3 mang đến số n = 3 (3 * 3 = 9) Đầu vào (input): X000 hiệu quả (output): 000000000 (9 số 0) - HẾT - ĐHCT, ngày thứ 2 tháng 02 trong năm 2007 Giáo viên ra đề Nguyễn thanh thản ĐÁP ÁNCâu 1 (1.0 điểm): Áp dụng ngã đề bơm, các bạn hãy chứng minh ngôn ngữ sau đây không là ngôn từ i j j ichính quy: L = i, j ≥ 1 mang sử L là ngữ điệu chính quy. Khi ấy sẽ trường tồn một DFA M đồng ý cho ngôn từ L.Gọi n là số tinh thần của DFA M đó. Xét chuỗi z = anb1c1dn . Ta có độ nhiều năm của chuỗi z là: |z| = 2n + 2 > n . Theo vấp ngã đề bơm, ta cóthể để z = uvw , trong các số đó u, v, w là các chuỗi bé của z với đk như sau: |uv| ≤ n, |v| ≥ 1 và với đa số i ≥ 0 ta có uviw ϵ L bởi uv là chuỗi chi phí tố của chuỗi z = anb1c1dn và uv gồm độ nhiều năm chuỗi không to hơn n đề xuất uvchỉ chứa cam kết tự a. Vậy v cũng chỉ chứa ký kết hiệu a (và có ít nhất một cam kết hiệu a). Xét chuỗi uv2w, ta thấy chuỗi uv2w so với chuỗi uvw = z = anb1c1dn có khá nhiều hơn một chuỗiv. Khía cạnh khác, vào chuỗi v chỉ chứa ký hiệu a, bắt buộc ta suy ra vào chuỗi uv2w sẽ sở hữu số cam kết hiệu alớn rộng n (và số ký hiệu d không đổi là n). Vậy trong chuỗi uv2w sẽ sở hữu được số ký kết hiệu a nhiều hơn kýhiệu d, hay chuỗi uv2w ko thuộc ngôn ngữ L. Vậy giả thiết L là ngôn ngữ chính quy sai, giỏi L ko là ngôn từ chính quy.Câu 2 (2.0 điểm): các bạn hãy tìm một DFA tương đương với NFA sau: b a start a, b a, b quận 1 q2 q3 DFA tương đương: b start b b a a a a a b b Câu 3 (1.5 điểm): các bạn hãy vẽ một automata hữu hạn gật đầu cho ngôn ngữ được ký kết hiệu bởibiểu thức bao gồm quy sau: ( (a + ab) b* a )* cách 1: b a start q.1 q2 a a b q3 Cách 2: áp dụng cách vẽ đang học theo định lý 3.3 – Giáo trình Tin học lý thuyết – MSc. VõHuỳnh xoa – Đại học yêu cầu 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 chỉnh Chomsky (cho hiểu được vănphạm không có ký hiệu vô ích): S → 0SA | 1SB | 01 A → 0A | 0 B → 1B | 1 bước 1: bỏ qua mất (vì đề bài xích đã cho biết thêm văn phạm không có ký hiệu vô ích, và nhìn vào vănphạm ta thấy không tồn tại luật sinh ε hay vẻ ngoài sinh đơn vị).

Xem thêm: Công Ty Bánh Kẹo Kinh Đô Phố Nối Hưng Yên Tuyển Dụng Mới Nhất 2022



Xem thêm: Mẫu Đơn Xin Vào Đảng 2015 - Mẫu Đơn Xin Vào Đảng Mới Nhất Năm 2022

Cách 2: sửa chữa các cam kết hiệu hoàn thành ở những luật sinh gồm độ dài vế phải lớn hơn 1 bởi cácbiến tương ứng. S → C0SA | C1SB | C0C1 A → C0A | 0 B → C1B | 1 C0 → 0 C1 → 1 bước 3: sửa chữa thay thế luật sinh bao gồm độ lâu năm vế phải lớn hơn 2 bằng những luật sinh bao gồm độ nhiều năm vế phảibằng 2. S → C0D0 | C1D1 | C0C1 A → C0A | 0 B → C1B | 1 C0 → 0 C1 → 1 D0 → SA D1 → SBCâu 5 (1.0 điểm): các bạn hãy chuyển văn phạm sau đây về dạng chuẩn chỉnh Greibach: S → SA | 0 A → AS | 1 bước 1: văn phạm vẫn ở dạng chuẩn chỉnh Chomsky. Bước 2: thay đổi thay S bởi biến A1, biến hóa A bằng biến A2. Ta có tập lao lý sinh: A1 → A1A2 | 0 A2 → A2A1 | 1 bước 3: khử tính đệ quy trái sinh sống tập hình thức sinh trên: A1 → 0 | 0B1 A2 → 1 | 1B2 B1 → A2 | A2B1 B2 → A1 | A1B2 bước 4: những luật sinh từ thay đổi A1 cùng A2 vẫn thỏa dạng chuẩn Greibach. Bước 5: chuyển những luật sinh từ biến hóa B1 với B2 về dạng chuẩn chỉnh Greibach. A1 → 0 | 0B1 A2 → 1 | 1B2 B1 → 1 | 1B2 | 1B1 | 1B2B1 B2 → 0 | 0B1 | 0B2 | 0B1B2 Tập quy định sinh trên đã thỏa dạng chuẩn chỉnh Greibach.Câu 6 (1.5 điểm): các bạn hãy xây dựng một PDA tương tự với văn phạm phi ngữ cảnh gồm tập luậtsinh như sau: S → 0SA | 1SB | 0 | 1 A → 0A | 0 B → 1B | 1 xây cất PDA M như sau: M (q, 0, 1, S, A, B, δ, q, S, Ø) Với các hàm gửi δ 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): các bạn hãy kiến tạo một đồ vật Turing để triển khai phép nhân 3 một vài nguyên ndương (n > 0). Chú ý: trên băng nhập đang được cho trước một ký kết hiệu X ngơi nghỉ đầu băng. Đầu đọc đang chỉtại vị trí thứ nhất của băng nhập (ký hiệu X). Ý tưởng: a) Đổi X thành B (để làm cho chốt ngăn ở đầu chuỗi) b) gặp số 0 trước tiên đổi thành 1 (đổi thành 1 để lưu lại số 0 này đã được xét) c) di chuyển đến cuối chuỗi, thay đổi 2 ký kết hiệu B thành cam kết hiệu 2. D) dịch rời về đầu chuỗi cho tới khi gặp gỡ ký hiệu 1, dịch phải. 1. Nếu cam kết hiệu tiếp sau là 0, lặp lại bước b. 2. Nếu ký hiệu tiếp theo sau là 2 thì di chuyển về cuối chuỗi (cho cho khi chạm mặt B), tiếp đến dịch trái đổi những ký hiệu 1 với 2 thành 0. Gặp mặt ký hiệu B sống đầ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 q.3 q4 (1, 1, R) (2, 2, R) (2, 0, L) (1, 0, L) (2, 2, R) (B, B, L) quận 5 q6 q7 (B, B, Ø) -- HẾT --