URL study guide
https://tue.osiris-student.nl/onderwijscatalogus/extern/cursus?cursuscode=2IRR90&collegejaar=2025&taal=enOmschrijving
Premaster CSE students and master CSE students with 2IRR90 as recommended homologation course should contact their academic advisor (premaster CSE: [email protected] Or master CSE: [email protected]) to ask them to register them for the courseThis course covers fundamental concepts and theory in the fields of Automata Theory and Formal Language Theory including regular languages, context-free languages, and decidable languages and their computational models, viz. NFAs, PDAs, and TMs. In addition DFA-minimization and parsing are treated. The above is mainly covered by Chapters 1 to 5 of the textbook for this course.
Doelstellingen
Premaster CSE students and master CSE students with 2IRR90 as recommended homologation course should contact their academic advisor (premaster CSE: [email protected] Or master CSE: [email protected]) to ask them to register them for the courseAfter completion of the course the student knows the concepts of a
deterministic finite automaton (DFA) and of a non-deterministic finite
automaton (NFA) with silent moves, is able to identify the languages
accepted by these automata and is able to construct an automaton of
either kindthat accepts a given language. The student understands
the equivalence of regular expressions, DFAs and NFAs. The student can apply the table-filling method and Hopcroft’s algorithm to minimize the number of states of a DFA.
The student knows the concepts of a push-down automaton (PDA) and of a
context-free grammar (CFG), is able to identify the languages accepted
by a PDA and generated by a CFG. The student understands the notion of
a parse tree and the notions of top-down and bottom-up parsing. The student understands the equivalence of PDAs and
CFGs, a number of closure properties of the class of context-free languages.
The student is able to apply and prove the pumping lemma for the classes
of regular languages and context-free languages. The student understands the notion of Chomsky normal form and can perform CYK-parsing.
The student understands the notion of a Turing machine (TM), of a
decidable language and of a recognizable language. The student is able to proof that a specific language is or is not decidable or recognizable. The student is able to perform reductions from A_TM and PCP to various decision problems.