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


Wykład, realizacja - jesień 2018

  • 5 X 2018. Informacje organizacyjne. Przypomnienia: indukcja matematyczna, indukcyjna definicja drzewa, wysokość drzewa a liczba liści. Pojęcia podstawowe: alfabet, słowo nad alfabetem, język nad alfabetem, porządek kanoniczny, przeliczalność zbioru słów, nieprzeliczalność zbioru języków, konkatenacja słów, operacje językach: suma, przecięcie, dopełnienie, konkatenacja, domknięcie Kleene'go. Wyrażenia regularne.
  • 12 X 2018. Języki generowane przez wyrażenia regularne, języki regularne. Lemat o pompowaniu i lemat Myhill-Nerode (bez dowodów), zastosowania lematów. Gramatyki, wywód bezpośredni, wywód, wywód lewostronny i prawostronny, język generowany przez gramatykę.
  • 19 X 2018. Gramatyki bezkontekstowe, usuwanie symboli bezużytecznych, produkcji wycieralnych i produkcji jednostkowych.
  • 26 X 2018. Postaci normalne Chomskiego i Greibach, sprowadzanie gramatyk do postaci normalnych. Lematy o pompowaniu i Ogdena z dowodami.
  • 9 XI 2018. Lemat o pompowaniu, przykład. Algorytm CYK. Gramatyki z translacją, gramatyki LL(1), przykład gramatyki LL(1) generującej wyrażenia arytmetyczne.
  • 16 XI 2018. Gramatyki z translacją, przykład gramatyki LL(1) generującej wyrażenia arytmetyczne i konwertującej wyrażenia do odwrotnej notacji polskiej. Gramatyki kontekstowe i nieograniczone, języki kontekstowe i rekurencyjnie przeliczalne, postać normalna gramatyki kontekstowej, metoda przekształcenia gramatyki kontekstowej do postaci normalnej, przykład gramatyki kontekstowej.
  • 23 XI 2018. Maszyny Turinga, definicja, obliczenie, obliczanie funkcji, przykład. Modele maszyn Turinga: konfiguracja podstawowa, maszyna z wartownikiem, maszyna z taśmą wielościeżkową, równoważność modeli.
  • 30 XI 2018. Maszyny Turinga, modele i ich równoważność: z taśmą dwustronnie nieograniczoną, wielotaśmowy, koszt symulacji maszyny wielotaśmowej za pomocą maszyny jednotaśmowej.
  • 7 XII 2018. Maszyny Turinga niedeterministyczne, równoważność klas maszyn Turinga deterministycznych i niedeterministycznych.
  • 14 XII 2018. Automaty ze stosem, podsumowanie. Automaty skończone deterministyczne i niedeterministyczne, konfiguracja, ruch automatu, obliczenie, akceptacja wejścia i język akceptowany.
  • 21 XII 2018. Automaty skończone z e-przejściami, konfiguracja, ruch automatu, obliczenie. Równoważność klas automatów skończonych deterministycznych, niedeterministycznych i z e-przejściami.
  • 4 I 2019. Równoważność klasy automatów skończonych i klasy wyrażeń regularnych, dowód. Lemat o pompowaniu dla języków regularnych, dowód. Twierdzenie Myhill-Nerode, dowód.
  • 11 I 2019. Równoważność klas: gramatyk bezkontekstowych i automatów ze stosem, gramatyk kontekstowych i automatów liniowo ograniczonych, gramatyk nieograniczonych i maszyn Turinga. Hierarchia Chomskiego, inkluzje. Kodowanie maszyn Turinga, język przekątniowy i jego miejsce w hierarchii Chomskiego.
  • 18 I 2019. Język uniwersalny i jego przynależność do klasy języków rekurencyjnie przeliczalnych i wykluczenie z klasy języków rekurencyjnie przeliczalnych, dowód. Język przekątniowy w klasie języków kontekstowych, jego miejsce w hierarchii Chomskiego. Podstawienie, definicja i jej uogólnienia, homomorfizm. Domkniętość klasy języków regularnych ze względu na operacje na językach.
  • 25 I 2019. Domkniętość klas języków bezkontekstowych i kontekstowych ze względu na operacje na językach.

Ćwiczenia, realizacja - jesień 2018

Informacje o ćwiczeniach są na stronach internetowych prowadzących: dr inż. Janusz Rafałko i mgr inż. Aleksander Cisłak


Laboratoria, realizacja - jesień 2018

Informacje o laboratoriach są na stronach internetowych prowadzących: dr inż. Janusz Rafałko, mgr inż. Aleksander Cisłak, lic. Jarosław Miller

 


 

Program przedmiotu:



Przedmiot Teoria automatów i języków
Kierunek/Semestr Informatyka / sem V
Rodzaj przedmiotu obowiązkowy
Prowadzący dr hab. inż. Władysław Homenda
Godziny tygodniowo i sposób zaliczenia 2 / 1 / 1 / 0 / E
Kod przedmiotu ----

Program wykładu:

  • Wiadomości wstępne - przypomnienie: relacje, indukcja zupełna.
  • Wyrażenia i języki regularne, lemat o pompowaniu, lemat Myhill-Nerode.
  • Gramatyki i języki, gramatyki i języki bezkontekstowe, lemat o pompowaniu, lemat Ogdena.
  • Gramatyki i języki kontekstowe.
  • Gramatyki nieograniczone i języki rekurencyjnie przeliczalne.
  • Maszyny Turinga i ich odmiany, jezyki rekurencyjnie przeliczalne i rekurencyjne.
  • Automaty liniowo ograniczone i jezyki kontekstowe
  • Automaty ze stosem i jezyki bezkontekstowe.
  • Automaty skonczone i jezyki regularne, twierdzenie Myhill-Nerode.
  • Hierarchia Chomsky’ego jezyków .
  • Uwagi o rozstrzygalności.

Literatura podstawowa:

  • Hopcroft J.E. Ullman J.D., Wprowadzenie do teorii automatów, jezyków i obliczen, WNT
  • W. Homenda, Elementy lingwistyki matematycznej i teorii automatów, WPW

Przedmioty poprzedzajace:

Podstawy matematyki – algebra, wstep do logiki i teorii mnogosci.
 

Regulamin zaliczenia przedmiotu (18 października 2016):

  • zaliczenie przedmiotu uzyskuje się przez zaliczenie egzaminu w terminach wyznaczonych przez dziekanat (dwa terminy w sesji zimowej, jeden termin w sesji jesiennej),
  • zaliczenie egzaminu wymaga uzyskania zaliczenia części praktycznej i części teoretycznej egzaminu (uzyskania ponad 50% punktów za każdą część) uzyskanych w tym samym terminie wyznaczonym przez dziekanat,
  • osoby, które zaliczą bieżące prace laboratoryjne, mogą skorzystać z jednokrotnego zwolnienia z części praktycznej przy pierwszym przystąpieniu do egzaminu w dowolnym z trzech terminów wyznaczonych przez dziekanat,
  • ocena końcowa jest średnią z ocen za część praktyczną (lub uzyskaną z laboratoriów) i teoretyczną, oceny z każdej części odpowiadają punktom uzyskanym z tych części według zwykłej skali (dst za >50% punktów, dst+ za >60% punktów itd.),
  • obie części egzaminu mają formę sprawdzianów pisemnych i są organizowane według reguł przygotowanych przez dziekanat, ponadto: na części praktycznej egzaminu można mieć własnoręcznie zapisaną kartkę formatu A5, na części teoretycznej nie można korzystać z żadnych pomocy.


Regulamin zaliczenia przedmiotu (1 października 2015):

  • zaliczenie przedmiotu wymaga uzyskania zaliczenia części praktycznej i części teoretycznej, zaliczenie obu części musi być uzyskane w bieżącym roku akademickim,
  • zaliczenie części praktycznej można uzyskać a) na ćwiczeniach przez zaliczenie bieżących prac laboratoryjnych, b) w pierwszym terminie egzaminu wyznaczonym przez dziekanat,
  • do zaliczenia części teoretycznej można przystąpić po wcześniejszym zaliczeniu części praktycznej, zaliczenie części teoretycznej uzyskuje się przystępując do egzaminu w terminach wyznaczonych przez dziekanat (dwa terminy w sesji zimowej, jeden termin w sesji jesiennej),
  • ocena z części teoretycznej jest oceną z pierwszej próby lub ndst i ocena z drugiej próby (wpisana ocena niedostateczna z pierwszej próby i ocena z drugiej próby) lub ndst, ndst i ocena według formuły max(2,floor(o3)-1), gdzie o3 jest oceną z trzeciej próby (5 października 2015),
  • końcowa ocena jest średnią ocen z części praktycznej i teoretycznej,
  • sprawdziany są organizowane według reguł przygotowanych przez dziekanat, ponadto: na sprawdzianach części praktycznej można mieć własnoręcznie zapisaną kartkę formatu A5, na sprawdzianach części teoretycznej nie można korzystać z żadnych pomocy.