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

Giả sử L là ngôn từ thiết yếu quy. lúc này sẽ mãi sau một DFA M chấp nhận đến ngữ điệu L.Điện thoại tư vấn n là số tâm trạng của DFA M kia.Xét chuỗi z = anb1c1dn . Ta có độ nhiều năm của chuỗi z là: |z| = 2n + 2 n . Theo bửa đề bơm, ta cóthể đặt z = uvw , trong những số ấy u, v, w là những chuỗi nhỏ của z cùng với ĐK như sau:|uv| ≤ n, |v| ≥ 1 và với đa số i ≥ 0 ta tất cả uviw ϵ L




You watching: 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 kỳ 1 – Năm học 06 - 07 Thời gian có tác dụng bài: 1đôi mươi phút ít NỘI DUNG ĐỀCâu 1 (1.0 điểm): Áp dụng vấp ngã đề bơm, các bạn hãy chứng tỏ ngôn từ tiếp sau đây không là ngôn ngữ i j j ithiết yếu quy: L = a b c d Câu 2 (2.0 điểm): Bạn hãy search một DFA tương tự với NFA sau: b a start a, b a, b q1 q2 q3Câu 3 (1.5 điểm): quý khách hàng hãy vẽ một automata hữu hạn gật đầu đồng ý đến ngôn ngữ được cam kết hiệu bởibiể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 dưới đây về dạng chuẩn chỉnh Chomsky (cho thấy thêm rằng vănphạm không có ký kết hiệu vô ích): S → 0SA | 1SB | 01 A → 0A | 0 B → 1B | 1Câu 5 (1.0 điểm): quý khách hãy đưa văn uống phạm tiếp sau đây về dạng chuẩn chỉnh Greibach: S → SA | 0 A → AS | 1Câu 6 (1.5 điểm): Quý Khách hãy xây cất một PDA tương tự với văn uống phạm phi ngữ chình ảnh bao gồm tập luậtsinch nhỏng sau: S → 0SA | 1SB | 0 | 1 A → 0A | 0 B → 1B | 1Câu 7 (2.0 điểm): Bạn hãy thiết kế một trang bị Turing nhằm triển khai phép nhân 3 một số trong những nguyên ndương (n > 0). Crúc ý: bên trên băng nhập đã có mang lại trước một ký kết hiệu X nghỉ ngơi đầu băng. Đầu hiểu đã chỉtrên địa chỉ thứ nhất 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 trái (output): 000000000 (9 số 0) - HẾT - ĐHCT, ngày 02 tháng 0hai năm 2007 Giáo viên ra đề Nguyễn Tkhô hanh Bình ĐÁP ÁNCâu 1 (1.0 điểm): Áp dụng bổ đề bơm, các bạn hãy chứng minh ngữ điệu dưới đây ko là ngữ điệu i j j ichính quy: L = a b c d Giả sử L là ngôn ngữ chủ yếu quy. Khi này sẽ lâu dài một DFA M đồng ý đến ngôn ngữ L.Call n là số trạng thái của DFA M đó. Xét chuỗi z = anb1c1dn . Ta tất cả độ dài của chuỗi z là: |z| = 2n + 2 > n . Theo xẻ đề bơm, ta cóthể đặt z = uvw , trong số đó u, v, w là các chuỗi nhỏ của z với điều kiện như sau: |uv| ≤ n, |v| ≥ 1 cùng với mọi i ≥ 0 ta có uviw ϵ L Do uv là chuỗi chi phí tố của chuỗi z = anb1c1dn với uv bao gồm độ lâu năm chuỗi ko to hơn n buộc phải uvchỉ cất cam kết trường đoản cú a. Vậy v cũng chỉ cất ký hiệu a (cùng bao gồm tối thiểu một cam kết hiệu a). Xét chuỗi uv2w, ta thấy chuỗi uv2w đối với chuỗi uvw = z = anb1c1dn có khá nhiều rộng một chuỗiv. Mặt không giống, vào chuỗi v chỉ đựng ký hiệu a, buộc phải ta suy ra vào chuỗi uv2w sẽ sở hữu số cam kết hiệu alớn hơn n (và số ký kết hiệu d ko đổi là n). Vậy vào chuỗi uv2w sẽ có số ký hiệu a nhiều hơn thế kýhiệu d, hay chuỗi uv2w không thuộc ngữ điệu L. Vậy trả thiết L là ngữ điệu chính quy không nên, tốt L không là ngôn từ thiết yếu quy.Câu 2 (2.0 điểm): quý khách hàng hãy tra cứu một DFA tương đương cùng với NFA sau: b a start a, b a, b q1 q2 q3 DFA tương đương: b start b b a a a a a b b Câu 3 (1.5 điểm): quý khách hàng hãy vẽ một automata hữu hạn đồng ý cho ngữ điệu được ký hiệu bởibiểu thức chủ yếu quy sau: ( (a + ab) b* a )* Cách 1: b a start q1 q2 a a b q3 Cách 2: sử dụng giải pháp vẽ đang 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): quý khách hàng hãy gửi vnạp năng lượng phạm dưới đây về dạng chuẩn Chomsky (cho biết thêm rằng vănphạm không có cam kết hiệu vô ích): S → 0SA | 1SB | 01 A → 0A | 0 B → 1B | 1 Bước 1: làm lơ (vì đề bài xích sẽ cho biết vnạp năng lượng phạm không tồn tại ký kết hiệu ăn hại, cùng nhìn vào vănphạm ta thấy không tồn tại dụng cụ sinh ε tuyệt qui định sinc đơn vị).

See more: 24 Sự Thật Thú Vị Về Nước Pháp Nổi Tiếng Về Cái Gì Thú Vị? Nước Pháp Có Gì Nổi Bật Để Đi Du Lịch



See more: Cho Hình Thang Có 2 Đường Chéo Vuông Góc, Hình Thang Là Gì

Cách 2: sửa chữa thay thế những ký kết hiệu xong xuôi sống những chính sách sinc bao gồm độ lâu năm vế bắt buộc to hơn 1 bởi cácbiến đổi tương xứng. S → C0SA | C1SB | C0C1 A → C0A | 0 B → C1B | 1 C0 → 0 C1 → 1 Bước 3: thay thế chế độ sinc có độ nhiều năm vế nên lớn hơn 2 bởi những hiện tượng sinch bao gồm độ lâ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): Quý Khách hãy đưa vnạp năng lượng phạm sau đây về dạng chuẩn chỉnh Greibach: S → SA | 0 A → AS | 1 Bước 1: vnạp năng lượng phạm vẫn nghỉ ngơi dạng chuẩn Chomsky. Bước 2: cầm cố đổi thay S bằng vươn lên là A1, thay đổi A bởi trở nên A2. Ta bao gồm tập giải pháp sinh: A1 → A1A2 | 0 A2 → A2A1 | 1 Cách 3: khử tính đệ quy trái sống tập mức sử dụng sinh trên: A1 → 0 | 0B1 A2 → 1 | 1B2 B1 → A2 | A2B1 B2 → A1 | A1B2 Cách 4: các chế độ sinch từ bỏ phát triển thành A1 và A2 đang thỏa dạng chuẩn chỉnh Greibach. Bước 5: đưa những công cụ sinch từ vươn lên là B1 và 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 chính sách sinch bên trên đang thỏa dạng chuẩn Greibach.Câu 6 (1.5 điểm): Quý khách hàng hãy kiến tạo một PDA tương tự cùng với văn phạm phi ngữ chình họa gồm tập luậtsinh nlỗi sau: S → 0SA | 1SB | 0 | 1 A → 0A | 0 B → 1B | 1 Xây dựng PDA M nlỗi sau: M (q, 0, 1, S, A, B, δ, q, S, Ø) Với những hàm đưa δ nlỗi 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): quý khách hàng hãy thi công một đồ vật Turing nhằm thực hiện phxay nhân 3 một trong những nguyên ndương (n > 0). Crúc ý: trên băng nhập đã làm được đến trước một ký hiệu X sinh hoạt đầu băng. Đầu gọi vẫn chỉtrên địa điểm thứ nhất của băng nhập (ký kết hiệu X). Ý tưởng: a) Đổi X thành B (để làm chốt chặn làm việc đầu chuỗi) b) Gặp số 0 thứ nhất đổi thành 1 (đổi thành 1 để ghi lại số 0 này đã được xét) c) Di gửi mang đến cuối chuỗi, đổi 2 cam kết hiệu B thành cam kết hiệu 2. d) Di đưa về đầu chuỗi cho đến Khi chạm chán ký kết hiệu 1, dịch cần. 1. Nếu ký hiệu tiếp theo là 0, lặp lại bước b. 2. Nếu ký kết hiệu tiếp theo sau là 2 thì dịch rời về cuối chuỗi (cho tới khi gặp gỡ B), sau đó dịch trái đổi các cam kết hiệu 1 và 2 thành 0. Gặp ký kết hiệu B sinh hoạt đầu chuỗi thì hoàn thành. (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 --

Chuyên mục: Giải Trí