- Part I. Finite Automata and Regular Languages: determinisation, regular expressions, state minimization, proving non-regularity with the pumping lemma, Myhill-Nerode relations.
- Part II. Pushdown Automata and Context-Free Languages: context-free grammars and languages, normal forms, proving non-context-freeness with the pumping lemma, pushdown automata.
- Part III. Turing Machines and Effective Computability: Turing machines, recursive sets, universal Turning machines, decidable and undecidable problems, reduction, other models of computability.
DD2371 Automatteori 6,0 hp
Denna kurs är avvecklad.
Sista planerade examination: VT 2011
Avvecklingsbeslut:
Ingen information tillagdInnehåll och lärandemål
Kursinnehåll
Lärandemål
The overall aim of the course is to provide students with a profound understanding of computation and effective computability through the abstract notion of automata and the language classes they recognize.
Along with this, the students will get acquainted with the important notions of state, nondeterminism and minimization.
After the course, the successful student will be able to perform the following constructions:
1. Determinize and minimize automata;
2. Construct an automaton for a given regular expression;
3. Construct a pushdown automaton for a given context-free language;
4. Construct a Turing machine deciding a given problem,
5. Prove whether a language is or isn't regular or context-free by using the Pumping Lemma;
6. Prove that a given context-free grammar generates a given context-free language;
7. Prove undecidability of a given problem by reducing from a known undecidable problem,
8. Apply the fundamental theorems of the course: Myhill-Nerode, Chomsky-Schützenberger, and Rice's theorems.
For passing the course, a student has to be proficient at problems of type 1-5; for the highest grade he/she has to be equally proficient at the remaining types of problems.
Kurslitteratur och förberedelser
Särskild behörighet
Rekommenderade förkunskaper
5B1118/SF1610 Discrete Mathematics, mandatory
5B1928/SF1642 Logic, recommended
Utrustning
Kurslitteratur
Dexter Kozen: Automata and Computability, Springer, 1997.
Examination och slutförande
När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.
Betygsskala
Examination
- TEN1 - Tentamen, 6,0 hp, betygsskala: A, B, C, D, E, FX, F
Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.
Examinator får medge annan examinationsform vid omexamination av enstaka studenter.
Övriga krav för slutbetyg
Examination (TEN1; 6 university credits).
Möjlighet till komplettering
Möjlighet till plussning
Examinator
Etiskt förhållningssätt
- Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
- Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
- Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.
Ytterligare information
Kursrum i Canvas
Ges av
Huvudområde
Utbildningsnivå
Påbyggnad
Kontaktperson
Övrig information
Kursen har ersatts av DD2372 Automater och språk.