Gramatyki i teoria automatów

Opis

Na warsztatach będziemy zajmować się przede wszystkim językami formalnymi. Nie są to jednak języki w rozumieniu takim, z jakim mieliście dotychczas do czynienia. W skrócie języki to zbiory słów, natomiast słowa to ciągi liter pochodzące z pewnego skończonego zbioru zwanego alfabetem. Litery również niekoniecznie pokrywają się z definicją jaką znacie, bo może być to w zasadzie jakikolwiek znak. W każdym razie, tak utworzone języki mogą mieć różne ciekawe własności i właśnie je będziemy badać. Przede wszyskim będziemy sprawdzać, czy należą one do pewnych klas zwanych językami regularnymi i bezkontekstowymi.

W tym celu poznamy różne narzędzia oraz własności tychże klas. Jednym z kluczowych narzędzi z jakich będziemy korzystać będą automaty. Są to takie abstrakcyjne maszyny pobierające słowa litera po literze i zmieniające stany w zależności od połkniętych liter. Jeśli automat jest w jednym ze specjalnych stanów, zwanych akceptującymi, może zakończyć wczytywanie słowa i słowo to jest wtedy nazwane akceptowanym przez dany automat.

W zależności od tempa warsztatów, zapoznamy się z:

1. Językami regularnymi i automatami
2. Językami bezkontekstowymi
3. Automatami ze stosem
4. Maszynami Turinga

Wymagania

Warto się zapoznać z definicjami języka formalnego, automatu, języka regularnego oraz z lematem o pompowaniu. Przydatna będzie również podstawowa wiedza z zakresu zbiorów.

Zadania kwalifikacyjne powinny weryfikować zrozumienie tych pojęć. Pamiętajcie, że zadania muszą być przesłane przez stronę warsztatów.

Przydatne rzeczy

Pomocne powinny być materiały ze strony https://brilliant.org/wiki/regular-languages/.

Dla ambitnych można się zapoznać z książką 200 Problems in Formal Languages and Automata Theory Niwińskiego i Ryttera, ale nie jest to niezbędne.

W razie wątpliwości/pytań/uwag piszcie do nas na a.wojciecho2@student.uw.edu.pl lub m.wysoglad@student.uw.edu.pl .