Báo cáo tài liệu vi phạm
Giới thiệu
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
THỊ TRƯỜNG NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
Thông tin
Tài liệu Xanh là gì
Điều khoản sử dụng
Chính sách bảo mật
0
Trang chủ
Công Nghệ Thông Tin
Cơ sở dữ liệu
Đề thi môn tin học lý thuyết
Đang chuẩn bị liên kết để tải về tài liệu:
Đề thi môn tin học lý thuyết
Ðức Khang
86
4
pdf
Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG
Tải xuống
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. | TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA CNTT TRUYỀN THÔNG Đề thi môn TIN HỌC LÝ THUYẾT 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 diem Á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 a bJ cJ d i j 1 Câu 2 2.0 diem Bạn hãy tìm một DFA tương đương với NFA sau b start a b a a b Câu 3 1.5 diem 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 diem 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 diem 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 diem 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 diem 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 ở dầ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 ĐÁ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ữ chính quy L a bJ cJ 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ó uv w e 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 . 2 2 ni11in i Ầ-i Xét chuỗi uv w ta thấy chuỗi uv w so với chuỗi uvw z abcd 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 .
TÀI LIỆU LIÊN QUAN
Đề thi học kì 2 môn Tin học lớp 6 năm 2018 có đáp án (Lý thuyết) - Trường THCS Phú Đa
Đề thi học kì 2 môn Tin học lớp 7 năm 2018 (Lý thuyết) - Trường THCS Phú Đa
Bộ đề thi giữa học kì 1 môn Tin học lớp 6 năm 2021-2022 (Có đáp án)
Đề thi học kì 2 môn Tin học 10 năm 2017-2018 - Trường THPT Phan Văn Hùng (Đề lý thuyết)
Đề thi học kì 1 môn Tin học 10 năm 2017-2018 có đáp án - Trường THPT Lý Thường Kiệt - Đề số 1
Đề thi học kì 1 môn Tin học 10 năm 2017-2018 có đáp án - Trường THPT Lý Thường Kiệt - Đề số 2
Đề thi học kì 1 môn Tin học 10 năm 2017-2018 có đáp án - Trường THPT Lý Thường Kiệt - Đề số 3
Đề thi học kì 1 môn Tin học 10 năm 2017-2018 có đáp án - Trường THPT Lý Thường Kiệt - Đề số 4
Đề thi học kì 1 môn Tin học 11 năm 2017-2018 có đáp án - Trường THPT Lý Thường Kiệt - Mã đề 132
Đề thi học kì 1 môn Tin học 11 năm 2017-2018 có đáp án - Trường THPT Lý Thường Kiệt - Mã đề 209
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.