UL/FRI/UNI-RI/TOR1
Iz E-študij, proste zakladnice študentskega znanja
| Abecedni seznam zapiskov
Predava: Boštjan Slivnik Vaje vodi: Uroš Čibej Povezave: http://ucilnica.fri.uni-lj.si/
(Za kolokvije ustvari stran) Izpitni red: Ostalo: Ključne besede: TOR1, teoretično računalništvo, izračunljivost |
Vsebina |
Snov
Uvod v teorijo izračunljivosti
Regularni jeziki in končni avtomati
- Regularni izrazi
- Končni avtomati
- Nedeterministični končni avtomati z ε-prehodi (ε-NKA)
- Nedeterministični končni avtomati (NKA)
- Deterministični končni avtomati (DKA)
- Regularne gramatike
- Levo in desno linearne gramatike (LLG in DLG)
- Osnovne lastnosti regularnih jezikov
- Operacije nad regularnimi jeziki
- Lema o napihovanju za regularne jezike
- Izrek Myhill-Nerode
- Minimizacija determinističnega končnega avtomata
Kontekstno neodvisni jeziki in skladovni avtomati
- Kontekstno neodvisne gramatike (KNG)
- Normalne oblike gramatik
- Algoritem CYK
- Skladovni avtomati
- Lema o napihovanju za kontekstno neodvisne jezike
- Ogdenova lema
Povezave
- JFLAP - program za eksperimentiranje z nekaterimi koncepti teorije formalnih jezikov
- Lema o napihovanju za regularne jezike (MaFiRa wiki)
- Lema o napihovanju za kontekstno neodvisne jezike (MaFiRa wiki)
- Zapiski 2011 (v nastajanju)
Literatura
Boštjan Slivnik: Uvodna poglavja v teorijo izračunljivosti (delovni osnutek)
John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation (2. in 3. izdaja), Addison-Wesley, 2001, 2007
John E. Hopcroft, Jeffrey D. Ullman: Uvod v teorijo avtomatov, jezikov in izračunov (delen in prirejen prevod), Univerza v Ljubljani, 1986.
Michael Sipser: Introduction to the Theory of Computation, PWS Publishing Company, 1997.
Poleg učbenikov profesor priporoča še nekaj bolj poljudnih knjig:
Douglas R. Hofstadter: Godel, Escher, Bash: An Eternal Golden Braid, Basic Books, 1999.
Roger Penrose: The Emperor's New Mind: Concerning Computers, Minds, and The Laws of Physics, Oxford University Press, 1989.
Christos Papadimitriou: Turing (a Novel about Computation), MIT Press, 2003.
