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 đề
- Điều kiện tiên quyết: MATH 3106 hoặc MATH 3158 hoặc MATH 3855 hoặc được phép của Khoa.
Điều kiện và thủ tục
- Cũng được liệt kê là COMP 4805.
- Điều kiện tiên quyết: MATH 3106 hoặc MATH 3158 hoặc MATH 3855 hoặc được phép của Khoa.
- Cũng được giảng dạy ở bậc sau đại học, với yêu cầu khác, dưới mã MATH 5605, và việc cộng thêm tín chỉ là không được phép.
- 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): MATH 3106 or MATH 3158 or MATH 3855 or permission of the School.
- Also listed as COMP 4805 .
- Also offered at the graduate level, with different requirements, as MATH 5605 , for which additional credit is precluded.
- 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/MATH/