Your browser doesn't support this content. You can turn it off by clicking on/off icon on the footer area of the page.


Teoria automatów i języków formalnych: studium praktyczne



Wykład prowadzony w latach 2014 - 2016



Wykład, realizacja - wiosna 2016

  • 3 III 2016. Informacje organizacyjne. Podstawowe definicje: alfabet, słowa nad alfabetem, język nad alfabetem, gramatyka, wywód słowa w gramatyce. Przeliczalność zbioru słów nad alfabetem, porządek kanoniczny, nieprzeliczalność klasy języków nad alfabetem. Gramatyki regularne, bezkontekstowe, kontekstowe, nieograniczone, hierarchia Chomsky'ego języków.
  • 10 III 2016. Automaty skończone deterministyczne i niedeterministyczne, funkcja przejścia, konfoguracja, obliczenie, akceptacja słowa wejściowego, równoważność klas automatów deterministycznych i niedterministycznych, automaty z e-ruchami, e-domknięcie.
  • 17 III 2016. Obliczenie automatu z e-ruchami, równoważność klas automatów z e-ruchami i niedeterministycznych. Automaty ze stosem, wersja podstawowa (deterministyczne bez e-ruchów), funkcja przejścia, konfiguracja, obliczenie, akceptacja słowa wejściowego.
  • 7 IV 2016. Automaty ze stosem cd., e-przejścia, warunek konieczny determinizmu. Postaci normalne gramatyk bezkontekstowych Chomskiego i Greibach, automat ze stosem równoważny gramatyce w postaci Greibach, wyrażenia arytmetyczne w notacji przyrostkowej.
  • 14 IV 2016. Gramatyka z translacją generacji wyrażeń arytmetycznych i konwersji do notacji przyrostkowej.
  • 21 IV 2016. Charakteryzacje przestrzeni języków: lematy o pompowaniu, twierdzenie Myhill-Nerode.
  • 5 V 2016. Maszyny Turinga, definicja, obliczenie, model jednotaśmowy i wielotaśmowy, przykłady.
  • 12 V 2016. Maszyny Turinga, kodowanie, przeliczalność zbioru maszyn Turinga, język przekątniowy, języki rekurencyjne, języki rekurencyjnie przeliczalne.
  • 19 V 2016. Zaliczenie/egzamin.
  • 2 VI 2016. Zaliczenie/egzamin.