Languages and Automata

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

Last updated: 2012. november 24.

Budapest University of Technology and Economics
Faculty of Electrical Engineering and Informatics
Course ID Semester Assessment Credit Tantárgyfélév
VISZM104 1 3/0/0/f 4  
3. Course coordinator and department Dr. Friedl Katalin,
6. Pre-requisites
Kötelező:
NEM ( TárgyEredmény( "BMEVISZMA04" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZMA04", "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ó.

8. Synopsis Finite automata (deterministic and non-deterministic), regular expressions, regular languages, closure properties, pumping lemma for regular languages. Push-down automata, context-free languages, Chomsky and Greibach normal forms, closure properties, pumping lemma for context-free languages. Turing-machines, recursive and recursively enumerable languages, linear bounded automata. Parsers for context-free languages. Time- and space-complexity: P, PSPACE, EXPTIME language classes. Non-deterministic Turing machines, NP language class, NP completeness, NPcomplete languages. Kolmogorov complexity: incomputability, Kolmogorov randomness.
14. Required learning hours and assignment
Kontakt óra
Félévközi készülés órákra
Felkészülés zárthelyire
Házi feladat elkészítése
Kijelölt írásos tananyag elsajátítása
Vizsgafelkészülés
Összesen