Wykład ,,Automaty i języki formalne”

Treści wykładów:

Pojęcie języka formalnego, automaty skończone i języki regularne, determinizacja skończonego automatu niederministycznego, wyrażenia regularne i konstrukcja odpowiednich automatów skończonych, minimalizacja deterministycznego automatu skończonego, lemat o pompowaniu dla języków regularnych, automaty ze stosem, gramatyki generatywne i hierarchia Chomsky’ego, gramatyki bezkontekstowe i ich postać normalna Chomsky’ego, lemat o pompowaniu dla języków bezkontekstowych, algorytm Cocke’a-Youngera-Kasamiego, związek gramatyk bezkontekstowych z automatami ze stosem, maszyna Turinga.

Sposób zaliczenia:

1) Zaliczenie ćwiczeń (mgr Maria Bulińska)

2) Na podstawie wyników sprawdzianów.

1. J. E. Hopcroft, R. Motwani, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Wydawnictwo Naukowe PWN, Warszawa 2017

2. J. Jędrzejewicz, A. Szepietowski, Języki, automaty, złożoność obliczeniowa, Wydawnictwo Uniwersytetu Gdańskiego, Gdańsk 2008

Literatura pomocnicza:

1. M. Sipser, Wprowadzenie do teorii obliczeń, Wydawnictwa Naukowo-Techniczne, Warszawa 2016

2. M. Foryś, A. Roman, Zbiór zadań z teorii języków formalnych i automatów, Wydawnictwo Uniwersytetu Jagiellońskiego, Kraków 2011

A.D.18.10.2022