TAILIEUCHUNG - Một số bài toán không giải được đối với ngôn ngữ tuyến tính

Đề tài được tiến hành nhằm nghiên cứu về tính khả giải của một số bài toán trong lý thuyết ngôn ngữ hình thức. Cụ thể là, tác giả sẽ chứng minh các bài toán sau đây là không giải được đối với ngôn ngữ tuyến tính: Bài toán tương đương của hai ngôn ngữ tuyến tính bất kỳ, bài toán đồng nhất của một ngôn ngữ tuyến tính với một ngôn ngữ chính quy, bài toán liệu có hay không L = Σ*, đối với ngôn ngữ tuyến tính L cho trước trên bảng chữ cái Σ. | Taïp chí Kinh teá - Kyõ thuaät Kỹ thuật - Công nghệ MỘT SỐ BÀI TOÁN KHÔNG GIẢI ĐƯỢC ĐỐI VỚI NGÔN NGỮ TUYẾN TÍNH Nguyễn Xuân Dũng* TÓM TẮT Việc nghiên cứu về tính khả giải của các bài toán (hoặc các lớp bài toán) đóng một vai trò rất quan trọng không chỉ đối với sự phát triển của Toán học nói riêng mà còn ảnh hưởng lớn đến sự phát triển của khoa học công nghệ nói chung. Trong bài này chúng tôi tiến hành nghiên cứu về tính khả giải của một số bài toán trong lý thuyết ngôn ngữ hình thức. Cụ thể là, chúng tôi sẽ chứng minh các bài toán sau đây là không giải được đối với ngôn ngữ tuyến tính: Bài toán tương đương của hai ngôn ngữ tuyến tính bất kỳ. Bài toán đồng nhất của một ngôn ngữ tuyến tính với một ngôn ngữ chính quy. Bài toán liệu có hay không L = Σ*, đối với ngôn ngữ tuyến tính L cho trước trên bảng chữ cái Σ. LA = { ui1 ui2 .uim aim aim−1 .ai1

• Toán học
• Kỹ thuật công nghệ
• Ngôn ngữ tuyến tính
• Hai ngôn ngữ tuyến tính bất kỳ
• Bài toán đồng nhất ngôn ngữ tuyến tính
• Ngôn ngữ giải toán chính quy
• An toàn hệ thống kỹ thuật công nghệ
• Hệ thống kỹ thuật công nghệ
• Đánh giá an toàn của kỹ thuật công nghệ
• Chỉ thị kỹ thuật công nghệ
• Luận văn Công nghệ kỹ thuật ô tô
• Công nghệ kỹ thuật ô tô
• Công nghệ ô tô
• Tài liệu tham khảo về công nghệ ô tô
• Công nghệ lai trên ô tô
• Công nghệ lai trên xe máy
• Đề thi học kỳ
• Công nghệ xử lý ảnh kỹ thuật số
• Xử lý ảnh kỹ thuật số
• Đề thi Công nghệ xử lý ảnh kỹ thuật số
• Bài tập Công nghệ xử lý ảnh kỹ thuật số
• Kỹ thuật chế biến món ăn
• Nghệ thuật cắm hoa
• Giáo trình Nghệ thuật cắm hoa
• Kỹ thuật trang trí cắm hoa
• Đặc điểm của nghệ thuật cắm hoa
• Kỹ thuật cắm hoa trên bình cao
• Giáo trình Công nghệ kỹ thuật ô tô
• Nhập môn Công nghệ kỹ thuật ô tô
• Kỹ thuật ô tô
• Cấu tạo tổng quát ô tô
• Phát triền ngành công nghiệp ô tô
• Giáo trình Công nghệ sản xuất gỗ kỹ thuật
• Công nghệ sản xuất gỗ kỹ thuật
• Gia công gỗ kỹ thuật
• Phối hợp màu gỗ tự nhiên
• Sản xuất phôi gỗ kỹ thuật trang sức
• Sản phẩm gỗ kỹ thuật chịu lực
• Kỹ thuật công trình trong công nghệ hóa học
• Kỹ thuật công trình
• Công nghệ hóa học
• Hệ thống phụ trợ
• Kỹ thuật an toàn xí nghiệp
• Đề cương chi tiết học phần
• Chương trình đào tạo
• Ngành Công nghệ Dệt may
• Công nghệ may 4
• Kỹ thuật công nghệ may
• Kỹ thuật công nghệ may mã hàng mới
• Công nghệ may mã hàng áo sơ mi
• Giáo trình Công nghệ CAD/CAM
• Công nghệ CAD/CAM
• Công nghệ CAD/CAM nâng cao
• Công nghệ kỹ thuật cơ khí
• Lệnh tạo khối
• Lập trình gia công
• Chương trình kỹ thuật ô tô
• Giáo dục kỹ thuật ô tô
• Kiến thức công nghệ ô tô
• Công nghệ sinh học
• Kỹ thuật công nghệ sinh học
• Đề thi Kỹ thuật công nghệ sinh học
• Bài tập Kỹ thuật công nghệ sinh học
• Bài giảng Công nghệ trong kỹ thuật ô tô
• Công nghệ trong kỹ thuật ô tô
• Công nghệ chế tạo ô tô
• Gia công cắt gọt
• Cô nghệ đúc
• kỹ thuật số
• giáo trình điện tử số
• kỹ thuật điện tử
• công nghệ điện tử số
• bài tập kỹ thuật số
• tín hiệu số
• ứng dụng kỹ thuật số
• công nghệ kỹ thuật số
• Giáo trình Vẽ kỹ thuật
• Vẽ kỹ thuật
• Vẽ hình học
• Lập bản vẽ kỹ thuật
• Bản vẽ kỹ thuật
• Hình chiếu cơ bản
• Công nghê cơ khí
• Công nghệ gia công
• Văn bản công trình
• Kỹ thuật công trình hóa học
• Hoàn thành hồ sơ dự án
• Kỷ yếu hội thảo khoa học
• Kiểm định chương trình Công nghệ kỹ thuật ô tô
• Đào tạo chương trình Công nghệ kỹ thuật ô tô
• Lộ trình triển khai CDIO
• Mô hình chất lượng AUN QA
• Kỹ thuật chung ô tô và công nghệ sửa chữa
• Giáo trình Kỹ thuật chung ô tô
• Công nghệ sửa chữa ô tô
• Phân loại động cơ đốt trong
• Động cơ nhiều xy lanh
• Kỹ thuật truyền số liệu
• Kỹ thuật công nghệ truy nhập
• Bài giảng Công nghệ truy nhập
• Kỹ thuật đa truy nhập
• Công nghệ truy nhập
• Kỹ thuật giảm tác động của nhiễu
• Mô hình họa
• Bản vẽ Kỹ thuật Công nghệ
• Ký hiệu trong Kỹ thuật Công nghệ
• Sơ đồ trong Kỹ thuật Công nghệ
• Thông số trong Kỹ thuật Công nghệ
• Hình ảnh mô hình họa
• Kỹ thuật công nghệ GSM
• Công nghệ GSM
• Ứng dụng kỹ thuật công nghệ GSM
• Chương trình tổng đài nhắn tin
• Khoa học máy tính
• Luận văn thạc sĩ
• Luận văn thạc sĩ kỹ thuật
• Luận văn khoa học máy tính
• Ngành Công nghệ kỹ thuật ô tô
• Đào tạo Công nghệ kỹ thuật ô tô
• Chương trình Công nghệ kỹ thuật ô tô
• Vận hành thiết bị ô tô
• Bảo dưỡng ô tô
• Sửa chữa ô tô
• Bài giảng Công nghệ 8 bài 1
• Bài giảng điện tử Công nghệ 8
• Bài giảng điện tử lớp 8
• Bài giảng môn Công nghệ lớp 8
• Vai trò của bản vẻ kỹ thuật
• Bản vẽ kỹ thuật với đời sống
• Bản vẽ kỹ thuật với sản xuất
• Giáo án Công nghệ 8 bài 1
• Giáo án điện tử Công nghệ 8
• Giáo án điện tử lớp 8
• Giáo án môn Công nghệ lớp 8