Languages and Automata

A tantárgy neve magyarul / Name of the subject in Hungarian: Nyelvek és automaták

Last updated: 2020. július 9.

Budapest University of Technology and Economics
Faculty of Electrical Engineering and Informatics
Course ID Semester Assessment Credit Tantárgyfélév
VISZMA04 1,2 3/0/0/f 4  
3. Course coordinator and department Dr. Friedl Katalin,
Web page of the course cs.bme.hu/la
4. Instructors

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 

5. Required knowledge Basic algorithms
6. Pre-requisites
Kötelező:
NEM ( TárgyEredmény( "BMEVISZM104" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZM104", "FELVETEL", AktualisFelev()) > 0
VAGY
TárgyEredmény( "BMEVISZMA12", "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZMA12", "FELVETEL", AktualisFelev()) > 0)

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ó.

7. Objectives, learning outcomes and obtained knowledge
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. 
8. Synopsis

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

 

 

 

9. Method of instruction 3 hours lecture per week
10. Assessment Two tests during the semester. For a passing grade one has to achieve at least 40% on each. 
11. Recaps There are three retake occasions: one for each tests, and at the end of the semester a third when either one (but only one) can be  taken.
12. Consultations By appointment
13. References, textbooks and resources Michael Sipser: Introduction to the theory of computation, Thomson Course Techn., 2006.
14. Required learning hours and assignment
Kontakt óra42
Félévközi készülés órákra42
Felkészülés zárthelyire36
Házi feladat elkészítése
Kijelölt írásos tananyag elsajátítása
Vizsgafelkészülés
Összesen120
15. Syllabus prepared by Dr Katalin  Friedl associate professor, Department of Computer Science and Information Theory