CS 462Formal Languages and Parsing
- Units
- 0.50
- Faculty
- Mathematics
- Subject
- Computer Science
When it runs
- F24
- W25
- S25
- F25
- W26
- S26
- F26
- W27
- S27
Ran in 0 of the last 7 terms. Winter 2027: not on the schedule. Spring 2027: schedule not out yet.
Languages and their representations. Grammars --Chomsky hierarchy. Regular sets and sequential machines. Context-free grammars -- normal forms, basic properties. Pushdown automata and transducers. Operations on languages. Undecidable problems in language theory. Applications to the design of programming languages and compiler construction.
Prerequisites
- Complete all of the following
- Must have completed at least 1 of the following:
- Enrolled in H-BBA & BCS Double Degree, H-Computer Science (BCS), H-Computer Science (BMath), JH-Computer Science (BCS), JH-Computer Science (BMath), H-Computing & Financial Management, H-Data Science (BCS), or H-Software Engineering
Antirequisites
None listed.
Leads to
No course lists it as a requisite.
Resources
Around the web
Found by uwloo’s link finder, which checks that each page names CS 462.
- CS 462 | SCS Course website · cs.uwaterloo.ca · from Jonathan Buss’s site Remove
Reviewed on UW Flow
50% liked it60% easy33% useful
From 10 ratings and 3 comments on UW Flow. The most helpful comments, quoted as written, without names. Read them all on UW Flow.
If you liked CS 360/365, you mustn't miss this course.
Oct 2020 · liked itOn UW FlowRemove this
Lowest mark since 1A.
Apr 2019 · liked itOn UW FlowRemove this
One of the highest marks I've had in the last four years. There were a lot of bonus marks and extra questions to keep marks high. The work is actually tough, but it's a good kind of tough if you like proofs. The assignments are pretty manageable if you start early.
Apr 2016On UW FlowRemove this
Discussed on r/uwaterloo
36 posts and comments in 34 threads mention CS 462, July 2015 to December 2024. Quoted word for word, newest first; each reply sits under the post and the comment that started its branch. Search r/uwaterloo for newer posts.
Spring 2024
I just retired from UW after 34 years of teaching CS (and 40 years of teaching total). Ask me anything. 503 points, 282 comments
“I just retired from UW after 34 years of teaching CS (and 40 years of teaching total). Summary: \ I published several books on number theory, combinatorics on words, and automata theory \ I published …”
u/Gauss_given_order: “Congratulations on your retirement! Has Dr. Lubiw also retired? Do you think anyone from the current faculty would be willing to take over CS 462 or CS 763? I wish I had the chance to take 462 with you :(”
u/Impossible_Ebb2433: “Since CS462 will probably never be offered again and you’re the go-to instructor for it, are there any text or notes you would recommend?”
u/Gauss_given_order: “Whom do you regard as your most brilliant collaborator? What do you think sets them apart? Are you interested in the busy beaver problem? …”
u/shallit: “… The busy beaver problem is a fun one that I've talked about in CS 360/365/462 from time to time. It illustrates the kind of astonishingly complex behavior that even the simplest systems can produce. …”
Spring 2022
CS students, what courses have you taken each term 9 points, 21 comments
“Inspired by https://www.reddit.com/r/uwaterloo/comments/v3b8nj/can\any\current\mathcs\students\let\me\know\their/ but recognizing that one term is a very narrow view, What courses have you taken each …”
u/BubblesfromSunnyvale: “… 442, PMATH 340, ECON 371, CO 487 3B: CO 250, MUSIC 140, CS 360, CS 458, CS 370 4A: CS 444, CS 462, CO 331, MUSIC 246 4B: CS 486, CO 342, CO 380, GEOG 181 In 4B now, would be happy to talk about courses with anyone interested.”
Theoretical CS courses 4 points, 4 comments
“Are there any other CS courses similar to CS 365 or CS 467? Basically, CS courses that are more theoretical rather than applied. …”
u/COCS2022: “CS 462: Formal Languages and Parsing CS 466: Algorithm Design and Analysis CS 485: Foundations of Machine Learning”
Fall 2021
What would you say are they most math heavy courses in CS? 5 points, 7 comments
“Trying to plan out my degree and be all organized and whatever. What are the most math heavy required courses? Don’t want too much math in one term. …”
u/tendstofortytwo: “MATH 239 is the heaviest. The least amount of math, I imagine, would be to take MATH 135/136, 127/128, 239, STAT 230/231 (bare minimum math courses), and then not take CS360/365, 370/371, or any CS 462 ≤ x < 490 (not-required math-y CS courses).”
3rd year/4th year CS courses with no final exams 16 points, 11 comments
“Are there any upper year courses that don't have finals?”
u/BubblesfromSunnyvale: “The big 3 are almost entirely project based I believe, and CS 462 has a week-long take home final.”
Is CS245 important for upper years 3 points, 11 comments
“Can I bs my way to a credit or should I actually try to form a long term sustainable understanding of this gong show of a class”
u/og_darcy: “Useful for CS 360/365 -> CS 462 And CS 348”
[deleted by user] 33 points, 14 comments
u/tendstofortytwo: “Yes, and yes.”
u/ffrosteh: “… 457 System Performance Evaluation Course Description CS 458 Computer Security and Privacy CS 462 Formal Languages and Parsing CS 466 Algorithm Design and Analysis Course Description CS 467 Introduction to Quantum Information Processing CS 475 Computational Linear Algebra CS 476 …”
Winter 2021
CS245 online vs in-person 6 points, 10 comments
“I heard CS245 is not very organized online. People who took the course recently, would you recommend taking CS245 online? TIA. …”
u/og_darcy: “Imo the only reason ppl are having it so bad rn is cuz Shai is the only prof. Usually there are 3 profs total (including Shai) and before covid you could just go to the other profs’ lectures instead. …”
u/og_darcy: “… as things like formal languages which you’ll overlap a bit with in CS 241 and CS 360/365 -> CS 462 Actually, I think in this aspect, Shai goes a little deeper than other profs and (maybe) his approach is better for preparing you for those later courses”
CS courses on complexity, logic, Courcelles theorem PCP 3 points, 1 comment
“Looking for one or more CS courses covering complexity, logic, Courcelles theorem, and PCP possible other theoretical cs essentials Grad student in Math”
u/BubblesfromSunnyvale: “CS 245 covers propositional and predicate logic plus some other content, CS 365 would be a classic theoretical computer science course as well as covering some complexity theory at the end. CS 462 covers formal languages and parsing which is also pretty theoretical.”
Are there upper year CS courses that don't require a computer? 3 points, 7 comments
“I chugged lazeez white sauce and now bright displays makes me nauseous, so I can't use a computer. Thats not the real problem, I want to keep it to myself. …”
u/CaptainHatsGregor: “CS462. Formal languages and parsing. The "Formal" means math. I don't know how Dr. Shallit is teaching it online, but one certainly doesn't write software in 462, and in a typical term, everything could and would be handwritten. …”
Fall 2020
Easy Math Courses 6 points, 4 comments
u/anjoanjo8: “… I'm currently looking at CO 353, CS 462, CS 487, but not sure if those fit the bill. …”
Have you ever got 100 in a course? 10 points, 27 comments
“Is it possible to get 100% in a math, cs, or eng course? How rare is it?”
u/M_Onasi: “Not sure if this counts but >= 1 students have 100 in cs462 (and maybe cs360?) By solving or improving work on open problem(s) in the field”
Check it elsewhere for Fall 2026
- Undergraduate Calendar, 2026–27The official entry
- Requirements for Fall 2026Waterloo’s requisite checker
- Schedule of Classes, Fall 2026Instructors, rooms, live seats
- Quest Class SearchWhere you enrol
- Course outlinesSyllabi from past terms (UW login)
- UW FlowStudent ratings and reviews
- WClassesPast sections back to 2004, and who taught them