Languages and Automata
A tantárgy neve magyarul / Name of the subject in Hungarian: Nyelvek és automaták
Last updated: 2020. július 9.
Dr Judit Csima, associate professor, Department of Computer Science and Information Theory
Dr Katalin Friedl associate professor, Department of Computer Science and Information Theory
László Kabódi, associate lecturer, Department of Computer Science and Information Theory
A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.
A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.
To learn the basics of the theory of automata, the abstract definition, mathematical properties. To learn about formal languages and their connection to automata. To learn about the computational and practical consequences of Turing-machines. Emphasis is on theory and mathematical proofs.
Deterministic finite automaton (DFA)
Regular languages, their properties.
Nondeterministic finite automaton (NFA), algorithm to convert it to DFA
Minimal DFA construction. Regular expressions and their connection to NFA
The existence of non-regular languages, pumping lemma
Formal grammars, Chomsky hierarchy. Regular grammars
Algorithm to construct NFA from regular grammar, and regular grammar from NFA. Context free 8CF9 grammars and languages, parse trees, ambiguous words, grammars, and languages.
Standardization of CF grammars: algorithms to remove epsilon rules, unit rules, unneeded symbols
Chomsky normal form. Closure properties of CF languages
The existence of non CF languages. Pumping lemma for CF languages
Closure properties of CF languages. A simple parser: Cocke-Younger-Kasami algorithm. Pushdown automata (PDA)
Equivalence of PDA and CF grammars
Turing machine variations (one tape/multitape, deterministic/non-deterministic), their equivalence
Universal Turing machine. The notion of recursive (decidable) languages and recursively enumerable (recognizable) languages, examples. Diagonal language, universal language, halting problem.
The language classes R, RE, coRE, their connections, closure properties
The complement of the diagonal language. Theorem of Rice
Post correspondence problem. Time complexity and space complexity of languages