Početna stranicaVisoka učilištaKorisničke stranice

Sadržaj predmeta

Automati, formalni jezici i jezični procesori I ->
Kratica: RAČ02O5Opterećenje: 45 + 15 + 15 + 0
Nositelji: prof. dr. sc. Siniša Srbljić
Konačni automati. Regularni izrazi, regularni jezici i regularna gramatika. Konačni automati s izlazom. Potisni automat. Kontekstno neovisni jezici i konteksno neovisna gramatika. Nejednoznačnost. Tehnike parsiranja. Turingov stroj i gramatika s neograničenim produkcijama. Rekurzivni i rekurzivno prebrojivi jezici. Linearno ograničeni automat. Konteksno ovisni jezici i konteksno ovisna gramatika. Univerzalni Turingov stroj. Chomskyeva hijerarhija jezika. Odlučivi i neodlučivi problemi. Složenost automata i jezika. Klase i hijerarhija jezika s obzirom na složenost prihvaćanja.
Literatura:
1. J.E. Hopcroft and J.D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing Company, 1979.
2. R.N. Moll, M.A. Arbib and A.J. Kfoury: An Introduction to Formal Language Theory, Spring-Verlang New York Inc., 1988.
3. R. McNaughton: Elementary Computability, Formal Languages, and Automata, Prentice-Hall Inc., 1982.
Srce - Sveučilišni računski centar Sveučilišta u Zagrebu