Course Notes, Practice Problems, and Solutions
Week 9: Formal Languages/Automata Theory intro,
Regular expressions
Language intro, Regular Expressions
Reg exprs are not always useful, problem given to me:
Reg expr for language: Even number of a's, b's, c's
Humorous cartoon:
Saving the day with regular expressions
When stuck writing a reg expr, drawing its finite state machine helps me:
Languages, Finite Automata
(not responsible for)
Week 10: Context-free grammars, Turing machines
Languages, Context-free Grammars
Compiler phases example and parse tree
Video (me describing example 2 in the notes):
Developing a grammar for declaration list
There is a small mistake on the video at the very end.
For the non-terminal <type>, I show the rule:
<type> --> <int> | <float> | <char> | <bool>
Showing <int>, <float>, <char>, <bool> as non-terminals
is wrong.
They are terminals, just the actual characters.
It's correct in the notes; the rule should be:
<type> --> int | float | char | bool
For week 10, focus on the grammars. I will go over Turing machines
during lecture (you don't need to know them in detail - only what they are
in general and what they are good for):
Alan Turing, the man
-- history and accomplishments
Summary
UK apology to Turing
Languages, Turing Machines
Turing Machine example
What are Turing machines good for?
Supplementary material
Video (University course: CSC 236):
Regular expression examples
Video (University course: CSC 236):
Regular expression tips
Video (Matthew Might):
Interesting way to look at context-free grammars
Video (EngMicroLectures):
Turing machines
Practice Problems
Regular Expression problems
..................
solutions
Context-free Grammar practice problems
...........
solutions