|
|
|
Teoria automatów i języków formalnych
| zajęcia |
liczba godzin |
pkt ECTS |
| wykład |
30 |
|
| ćwiczenia |
15 |
2 |
| egzamin |
|
5 |
Pojęcia wstępne: słowo, słownik, język, gramatyka, wyprowadzalność, forma
zdaniowa, fraza, osnowa. Klasyfikacja Chomskyego. Rozbiór gramatyczny,
algorytm top-down i bottom-up, jednoznaczność gramatyki. Gramatyki regularne,
zbiory regularne, wyrażenia regularne, języki regularne. Automaty skończone,
przekształcenie NFA do DFA, minimalizacja automatu skończonego. Gramatyki
i języki bezkontekstowe. Automat ze stosem. Akceptacja języka bezkontekstowego
przez automat ze stosem. Języki kontekstowe i automat liniowo ograniczony.
Języki bez ograniczeń i maszyna Turinga. |
| |
|
|
|
|