Mô tả
Tự động hữu hạn và biểu thức chính quy, tính chất của các tập hợp chính quy, ngữ pháp phi ngữ cảnh, ngăn xếp tự động, ngôn ngữ ngữ cảnh xác định. Máy Turing, hệ phân cấp Chomsky. Tính không quyết định được, các bài toán khó xử lý.
Tiền đề
- Tiền đề: COMP 3805 hoặc MATH 3106 hoặc MATH 3158 (hoặc MATH 3100) hoặc sự cho phép của Khoa.
Điều kiện và thủ tục
- Cũng được liệt kê là MATH 4805 .
- Loại trừ tín chỉ bổ sung cho Loại trừ tín chỉ bổ sung cho MATH 5605 .
- Tiền đề: COMP 3805 hoặc MATH 3106 hoặc MATH 3158 (hoặc MATH 3100) hoặc sự cho phép của Khoa.
- Ba giờ giảng mỗi tuần.
Văn bản tham chiếu bằng ngôn ngữ gốc
Finite automata and regular expressions, properties of regular sets, context-free grammars, pushdown automata, deterministic context-free languages. Turing machines, the Chomsky hierarchy. Undecidability, intractable problems.
- Prerequisite(s): COMP 3805 or MATH 3106 or MATH 3158 (or MATH 3100) or permission of the School.
- Also listed as MATH 4805 .
- Precludes additional credit for Precludes additional credit for MATH 5605 .
- Lectures three hours a week.
Nguồn và tham khảo
Ngày và nguồn được giữ lại để giúp bạn kiểm tra thông tin. Các bản dịch được cung cấp để dễ đọc; nguồn chính thức là tham chiếu cho các điều kiện và yêu cầu.
Nguồn tham khảo : https://calendar.carleton.ca/undergrad/courses/COMP/