Automaty i języki formalne 3.4.KRK.12TX.AiJFo
A. Problematyka wykładu i konwersatorium
Podstawowe pojęcia lingwistyki matematycznej. Niedeterministyczne automaty skończone. Języki regularne. Niedeterministyczne automaty skończone a języki regularne. Deterministyczne automaty skończone. Równoważność niedeterministycznych i deterministycznych automatów skończonych. Ograniczenia na liczbę stanów automatów deterministycznych. Algorytmy wyszukiwania wzorca przy użyciu automatów skończonych. Algorytmy kanonizacji automatu deterministycznego. Problemy decyzyjne w językach regularnych i ich złożoność. Prawa algebraiczne dla wyrażeń regularnych. Zastosowania wyrażeń regularnych w analizie leksykalnej. Równoważność deterministycznych automatów skończonych i wyrażeń regularnych . Języki bezkontekstowe, drzewa wyprowadzeń, wieloznaczność gramatyk. Zastosowania gramatyk bezkontekstowych, podstawy budowy kompilatorów, gramatyki o ograniczonej wieloznaczności. Translacja sterowana składnią – zastosowania. Stosowanie lematu o pompowaniu dla języków regularnych lub metod kombinatorycznych pokazujących nieregularność zadanych języków. Postacie normalne gramatyk bezkontekstowych – zastosowania. Własności zamkniętości dla języków regularnych i bezkontekstowych. Hierarchia Chomsky’ego.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
Wiedza
W01 Zna pojęcia niedeterministycznego i deterministycznego automatu skończonego, formuły regularnej, języka regularnego, automatu kanonicznego oraz podstawowe twierdzenia dotyczące tego aparatu pojęciowego
W02 Zna pojęcia gramatyki bezkontekstowej, języka bezkontekstowego, drzewa wyprowadzenia, gramatyki jednoznacznej, postaci normalnej gramatyki bezkontekstowej, zna możliwości zastosowań języków regularnych i bezkontekstowych
W03 Zna podstawowe problemy decyzyjne dotyczące języków formalnych oraz ich złożoność czasową. Zna podstawowe prawa algebraiczne dla języków formalnych.
W04 Zna metody pokazywania, ze język nie należy do klasy. Zna hierarchię Chomsky’ego.
Umiejętności
U01 Potrafi definiować języki przy pomocy pojęć niedeterministycznego i deterministycznego automatu skończonego oraz formuły regularnej. Potrafi minimalizować automat skończony.
U02 Potrafi definiować gramatyki i języki bezkontekstowe, potrafi konstruować gramatyki jednoznaczne dla prostych języków
U03 Potrafi stosować lematy o pompowaniu lub metody kombinatoryczne w celu, np. dokonania klasyfikacji języków zgodnie z hierarchią Chomsky’ego
U04 Potrafi korzystać z bibliotek wykorzystywanych do generowania analizatorów leksykalnych. Potrafi zaimplementować algorytm wyszukiwania wzorca od podstaw lub przy wykorzystaniu gotowych narzędzi.
Kompetencje społeczne (postawy)
K01 Zna ograniczenia własnej wiedzy, rozumie potrzebę dalszego kształcenia, systematycznego poszerzania pogłębiania zdobytej wiedzy i śledzenia literatury
K02 Potrafi analizować działania, ustalać priorytety w celu realizacji określonego zadania
Kryteria oceniania
Na ogólnych zasadach określonych w programie kształcenia, a w szczególności
A. Sposób zaliczenia
• zaliczenie z oceną (konwersatorium)
• zaliczenie z oceną (wykład)
B. Formy zaliczenia
• (W) ustalenie oceny zaliczeniowej na podstawie sprawdzianów, samodzielnie sporządzonych streszczeń wykładów, zadań teoretycznych rozwiązywanych na konwersatorium
• (K) ustalenie oceny zaliczeniowej na podstawie ocen cząstkowych otrzymywanych w trakcie trwania semestru za zadań teoretycznych i praktycznych rozwiązywanych na konwersatorium
C. Podstawowe kryteria
• (W) (K) uzyskanie pozytywnej oceny zaliczeniowej
Literatura
A. Literatura wymagana
A.1. wykorzystywana podczas zajęć
1. J. E. Hopcroft, R. Motwani, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN, 2005.
A.2. studiowana samodzielnie przez studenta
1. A. V. Aho, R. Sethi, J. D. Ullman, Kompilatory, WNT, 2001.
B. Literatura uzupełniająca
1. M. Foryś, W. Foryś, Teoria automatów i języków formalnych, AOW EXIT, Warszawa 2005.
2. inne podręczniki dostępne on-line poprzez Bibliotekę Główną UO („ibuk”)
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: