Formal Languages and Automata Theory (FLAT)
Please join the RocketChat Room for the class.
Back to live! This semester we will be meeting every week on Friday starting at 10:30 in 23.21.U1.48.
There is no obligation of presence, but the classes include a mixture of theory and exercises, and I strongly believe I can teach much more this way.
In case you do not want or cannot participate on-site, you can work with the book ("Introduction to the Theory of Computation" by Michael Sipser) and submit homework.
For those, who absolutely cannot attend, I would try to turn on the streaming in BBB,
but my focus and priority will be on on-site teaching.In order to access it, you need to join the class in moodle
and click on the link there.
At the bottom of the page you would find a dropbox folder with materials. Numbered exercises are exercises from the book by Sipser that you will find in that folder.
Tentative course schedule
- 15 October -- Introduction, Mathematical preliminaries: infinities. Finite state automata, Deterministic automata.
- 22 October -- Closure properties of regular languages, DFA to RL, RL to FA, NDFA, equivalence of NFA and DFA.
- 29 October -- Pumping lemma for regular languages.
- 12 November -- Pushdown automata. Pumping lemma for PDA/context-free languages.
- 19 November -- Equivalence of CFGs and PDAs, DCFLs, Context-Free Language Closure Properties.
- 26 November -- Maybe a substitution by someone else or by personal meetings.
- 3 December -- Turing Machine.
- 10 December -- more Turing machines.
- 17 December -- Time complexity.
- 14 January -- P vs NP. NP-complete problems presentations.
- 21 January -- NP-complete problems presentations. Summary (take-away from the class), example tasks for the test.
- 28 January -- Test (for AP and/or BN). Either in class or from home.
- 4 February -- Test discussion, Blockchain & Bitcoin, feedback round.
Homework Rules
- Exercises are taken from the book that you can find in the materials folder at the bottom of the page
- Homeworks can be done individually or in pairs
- Homeworks are always due at the next class. You can submit them via email, at the secretary or in person at the beginning of the class.
- Homeworks are discussed at the beginning of the next class, so no late submissions are allowed. In case of illness please contact me personally.
- Unless otherwise indicated, homework assignment numbers refer to exercises in the course book. The book is available if you are in the university network, individual pages can be printed out/saved.
- If you submit via email, please observe the following rules:
- use either .hhu address or my gmail address.
- you file name should clearly indicate you name/names and the assignment number (e.g. Ex1-Zinova.pdf);
- inside the file, both you name and your Matrikelnummer should be provided (I usually print your exercises out)
- in the theme of the email, write "FLAT21 - Homework 1 by A (and B)". This will ensure that it does not get lost.
Grading
For both BN and AP:
- all homework submitted in a reasonable condition.
- alternative: exam at the class on 4.02
For an AP (if needed):
Links
Interactive Automaton Simulator
More beautiful simulator (uses .json files)
Turing Machine Simulator
Materials appear here