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ń 2017

  • 6 X 2017. Informacje organizacyjne. Przypomnienia: relacje, relacja równoważnosci i klasy równoważności, relacja prawostronnie niezmiennicza, domknięcie relacji, 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, relacja indukowana przez język. Wyrażenia regularne, języki regularne.
  • 13 X 2017. Lemat o Myhill-Nerode, lemat o pompowaniu, przykłady zastosowania. Gramatyki, definicja, przykład, wywód bezpośredni, wywód, język generowany. Wywody lewostronne, prawostronne i mieszane, drzewa wywodu.
  • 20 X 2017. Gramatyki bezkontekstowe, usuwanie symboli bezużytecznych, produkcji wycieralnych i produkcji jednostkowych, postaci normalne Chmoskiego (Chomsky'ego) i Greibach, przekształcanie gramatyk do postaci normalnych.
  • 27 X 2017. Przekształcanie gramatyki do postaci normalnej Greibach, kontynuacja. Lemat o pompowaniu, dowód, algorytm CYK - przkład, sformułowanie algorytmu jako zadanie domowe.
  • 3 XI 2017. Lemat o pompowaniu dla języków bezkontekstowych. Gramatyki kontekstowe i nieogranioczone, przykłady generacji języków. Postać normalna gramatyk kontekstowych, przekształcenie gramatyki kontekstowej do postaci normalnej, dowód.
  • 10 XI 2017, 9.00, 329. Maszyny Turinga, definicja, obliczenie, akeptacja języków, obliczanie funkcji, przykład. Modele maszyn Turinga: konfiguracja podstawowa, maszyna z wartownikiem, maszyna z taśmą wielościżkową, równoważność modeli.
  • 10 XI 2017, 10.30, 329. Modele masson Turinga: maszyna z taśmą dwostronnie nieograniczoną, maszyna wielotśmowa, równoważność modeli z modelem podstawowym, koszt symulacji maszyny wielotaśmowej.
  • 24 XI 2017.
  • 1 XII 2017.
  • 15 XII 2017.
  • 22 XII 2017.
  • 5 I 2018.
  • 12 I 2018.
  • 19 I 2018.
  • 26 I 2018.

Ćwiczenia, realizacja - jesień 2017

ćwiczenia prowadzą: dr inż. M. Luckner, dr inż. Janusz Rafałko, mgr inż. Aleksander Cisłak, mgr Tomasz Penza


Laboratoria, realizacja - jesień 2017

laboratoria prowadzą: dr inż. M. Luckner, dr inż. Janusz Rafałko i mgr inż. Aleksander Cisłak, mgr Tomasz Penza

 


Wykład, realizacja - jesień 2016

  • 7 X 2016. Informacje organizacyjne. Pojęcia podstawowe: alfabet, słowo nad alfabetem, język nad alfabetem, porządek kanoniczny, przeliczalność zbioru słów, nieprzeliczalność zbioru języków, operacje na słowach i językach. Wyrażenia regularne, języki regularne, przykłady. Lemat o pompowaniu.
  • 14 X 2016. Lemat o Myhill-Nerode, przykłady zastosowania. Gramatyki, definicja, wywód bezpośredni, wywód, język generowany. Gramatyki regularne. Gramatyki bezkontekstowe, wywody lewostronne, prawostronne i mieszane, drzewa wywodu.
  • 21 X 2016. Symbole bezużyteczne, symbole i produkcje wycieralne, zmiana statusu symboli wycieralnych, usuwanie produkcji wycieralnych, usuwanie produkcji jednostkowych
  • 28 X 2016. Postaci normalne gramatyk bezkontekstowych Chomskiego i Greibach ze szkicami dowodów, lemat o pompowaniu dla języków bezkontekstowych z dowodem.
  • 4 XI 2016. Sprawdzenie przynależności słowa do języka generowanego przez gramatykę bezkontekstową: algorytm i jego złożoność dla postaci Greibach, algorytm CYK i jego złożoność dla postaci Chomskiego (opis algorytmu do domu). Gramatyki z translacją i LL(1).
  • 10 XI 2016. Gramatyki z translacją i LL(1), dokończenie. Gramatyki i języki kontekstowe, postać normalna gramatyki kontekstowej. Gramatyki nieograniczone i języki rekurencyjnie przeliczalne.
  • 17 XI 2016. Gramatyki nieograniczone i kontekstowe, przykład. Maszyny Turinga, konfiguracja, obliczenie, akceptacja wejścia, przykład, model podstawowy, model z wartownikiem, równoważność modeli podstawowego i z wartownikiem.
  • 25 XI 2016. Maszyny Turinga, modele z taśmą wielościeżkową, z taśmą dwustronnie nieograniczoną, z wieloma taśmami, równoważność modeli, koszt symulacji.
  • 2 XII 2016. Maszyny Turinga niedeterministyczne, równoważność klas maszyn deterministycznych i niedeterministycznych, koszt deterministycznej symulacji.
  • 9 XII 2016. Automaty liniowo ograniczone. Automaty ze stosem, akceptacja stanem końcowym, akceptacja pustymi wejściem i pustym stosem, równoważność obu typów akceptacji, automaty ze stosem jako ograniczone modele maszyn Turinga.
  • 16 XII 2016. Automaty skończone deterministyczne i niedeterministyczne, funkcja przejścia, konfiguracja, obliczenie, akceptacja wejścia, domknięcie funkcji przejścia, równoważność klas automatów deterministycznych i niedeterministycznych.
  • 21 XII 2016. Automaty z e-ruchami, funkcja przejścia, konfiguracja, obliczenie, akceptacja wejścia, domknięcie funkcji przejścia, równoważność klas automatów z e-ruchami i niedeterministycznych. Domkniętość klasy języków regularnych ze względu na operacje na językach: sumy, iloczynu, dopełnienia, konkatenacji, domknięcia Kleene'go
  • 13 I 2017. Równoważność klas wyrażeń regularnych i automatów skończonych. Domkniętość/niedomkniętość klasy języków bezkontekstowych ze względy na operacje na językach: sumy, iloczynu, dopełnienia, konkatenacji, domknięcia Kleene'go.
  • 20 I 2017. Równoważność klas gramatyk nieograniczonych i maszyn Turinga. Domkniętość/niedomkniętość klasy języków rekurencyjnie przeliczalnych ze względy na operacje na językach: sumy, iloczynu, dopełnienia, konkatenacji, domknięcia Kleene'go, język przekątniowy, język uniwersalny. Klasa języków rekurencyjnych, domkniętość klasy ze względu na operacje na językach: sumy, iloczynu, dopełnienia, konkatenacji, domknięcia Kleene'go.
  • 27 I 2017. Równoważność klas gramatyk kontekstowych i automatów liniowo ograniczonych, język przekątniowy w klasie języków kontekstowych, zawieranie klasy języków kontekstowych w klasie języków rekurencyjnych.

Ćwiczenia, realizacja - jesień 2016

ćwiczenia prowadzą: dr inż. M. Luckner, dr inż. Janusz Rafałko i mgr inż. Aleksander Cisłak


Laboratoria, realizacja - jesień 2016

laboratoria prowadzą: dr inż. M. Luckner, dr inż. Janusz Rafałko i mgr inż. Aleksander Cisłak, mgr Tomasz Penza

 

 

Wykład, realizacja - jesień 2015

  • 2 X 2015. Informacje organizacyjne. Powtórzenie materiału: indukcja matematyczna, drzewa - definicja indukcyjna, lemat o liczbie liści w k-drzewie z dowodem, relacje, relacje binarne, relacje równowaznosci. Pojęcia podstawowe: alfabet, słowo nad alfabetem, język nad alfabetem, operacje na słowach i językach, relacje prawostronnie niezmiennicze i indukowane przez język.
  • 9 X 2015. Wyrażenia regularne, języki regularne, lemat Myhill-Nerode, lemat o pompowaniu.
  • 16 X 2015. Gramatyki, wywód słowa, język generowany. Gramatyki regularne. Gramatyki bezkontekstowe, wywód lewostronny i prawostronny, drzewo wywodu, symbole bezużyteczne: metoda wyznaczania, usuwanie z gramatyki.
  • 23 X 2015. Symbole i produkcje wycieralne, zmiana statusu symboli wycieralnych, usuwanie produkcji wycieralnych, usuwanie produkcji jednostkowych, postaci normalne Chomskiego (Chomsky'ego) i Greibach, sprowadzanie gramatyki do postaci normalnych.
  • 30 X 2015. Uzasadnienie poprawności rozpętlania gramatyki. Lemat o pompowaniu, algorytm CYK.
  • 6 XI 2015. Gramatyki kontekstowe, postać normalna. Gramatyki nieograniczone. Hierarchia Chomskyego. Maszyny Turinga, definicja, interpretacja modelu podstawowego, przykład maszyny, obliczenie maszyny.
  • 20 XI 2015. Modyfikacje modelu podstawowego maszyn Turinga: maszyny z wartownikiem, maszyny z własnością stopu ze stanem akceptującym i odrzucającym, maszyny ze stanem akceptującym, maszyny z taśmą wielościeżkową, maszyny z taśmą dwustronnie nieograniczoną. Równoważność klas maszyn Turinga po modyfikacjach z modelem podstawowym.
  • 27 XI 2015. Maszyny Turinga wielotaśmowe, równoważność klasy maszyn wielotaśmowych i klasy maszyn w modelu podstawowym, koszt symulacji obliczenia maszyny wielotaśmowej za pomocą maszyny jednotaśmowej. Maszyny Turinga niedeterministyczne, definicja, przykład.
  • 4 XII 2015. Maszyny Turinga niedeterministyczne, obliczenie, równoważność klas maszyn deterministycznych i niedeterministycznych. Automaty liniowo ograniczone.
  • 11 XII 2015. Automaty ze stosem, definicja, konfiguracja, obliczenie, przykłady, e-ruchy, warunki determinizmu automatu ze stosem, równoważność akceptacji za pomocą stanu akceptującego i za pomocą pustych wejścia i stosu, automaty ze stosem jako ograniczone maszyn Turinga, równoważność klasy automatów ze stosem i klasy gramatyk bezkontekstowych.
  • 18 XII 2015. Automaty skończone deterministyczne i niedeterministyczne, konfiguracja, obliczenie, akceptacja wejścia, domknięcie funkcji przejścia.
  • 8 I 2015. Równoważność klas automatów skończonych: deterministycznych, niedeterministycznych i z e-ruchami.
  • 15 I 2016. Równoważność klasy automatów skończonych i klasy wyrażeń regularnych. Podstawienie, homomorfizm, ilorazy języków, definicje, przykłady. Domkniętość klasy języków regularnych ze względu na operacje na językach: operacje teoriomnogościowe, konkatenacja i domknięcie Kleene'ego - dowodami, podstawienie, homomorfizm, ilorazy - bez dowodów. Automat deterministyczny akceptujacy dany język regularny - konstrukcja za pomocą ilorazów języków.
  • 22 I 2016. Lemat o pompowaniu dla języków regularnych, twierdzenie Myhill-Nerode - dowody. Domkniętość klasy języków regularnych ze wzgledu na podstawienie i iloraz lewostronny - szkice dowodów. Domknietośc klasy języków bezkontekstowych ze względu na sumę teoriomnogościową, konkatenację, domkniecie Kleene'ego, podstawienie, brak domkniętości ze względu na przecięcie i dopełnienie, uzasadnienia.
  • 29 I 2016. Hierarchia Chomsky'ego, ścisłe zawieranie klasy języków kontekstowych w klasie języków rekurencyjnych. Domkniętość klasy języków ze względu na operacje na językach.

Ćwiczenia, realizacja - jesień 2015

ćwiczenia prowadzą: dr inż. Janusz Rafałko i lic. Anna Grzesik
 

Wykład, realizacja - jesień 2014

  • 3 X 2014. Informacje organizacyjne. Pojęcia podstawowe: alfabet, słowo nad alfabetem, język nad alfabetem, operacje na słowach i językach, relacje prawostronnie niezmiennicze i indukowane przez język. Wyrażenia regularne, języki regularne, cdn.
  • 10 X 2014. Języki regularne, lemat o pompowaniu, lemat Myhill-Nerode. Gramatyki, gramatyki regularne.
  • 17 X 2014. Gramatyki bezkontekstowe, wywody lewostronne i prawostronne, drzewa wywodu, niejednoznaczność gramatyk, symbole bezużyteczne, symbole i produkcje wycieralne, produkcje jednostkowe, upraszczanie gramatyk bezkontekstowych, postacie normalne Chomskiego i Greibach, algorytm CYK.
  • 24 X 2014. Lemat o pompowaniu dla języków bezkontekstowych, lemat Ogdena, szkic dowodu, zastosowanie. Postać normalna Greibach, metoda przekształcania gramatyk bezkontekstowych do tej postaci.
  • 31 X 2014. Gramatyki bezkontekstowe i nieograniczone, postać normalna gramatyk bezkontekstowych, przkłady gramatyk kontekstowych i nieograniczonych. Hierarchia Chomskiego (Chomsky'ego).
  • 14 XI 2014. Maszyny Turinga, konfiguracja, obliczenie, przykład. Modele maszyn Turinga i ich równoważność: podstawowy, z wartownikiem, wielościeżkowy, z taśmą dwustronnie nieograniczoną.
  • 21 XI 2014. Masyny Turinga wielotaśmowe, równoważność klas maszyn wielotaśmowych i jednotaśmowych, koszt jednotaśmowej symulacji. Maszyny Turinga niedetereministyczne, akceptacja słowa wejściowego, obliczenie maszyny, interpretacja niedeterminizmu.
  • 24 XI 2014. Równoważność klas maszyn Turinga niedeterministycznych i deterministycznych, koszt symulacji niedeterministycznej, automaty liniowo ograniczone.
  • 28 XI 2014. Automaty ze stosem, konfiguracja, obliczenie, determinizm i niedeterminizm, akceptacja stanem akceptującym oraz pustym stosem i pustym wejściem, automaty ze stosem jako maszyny Turinga.
  • 5 XII 2014. Automaty skończone deterministyczne, niedeterministycze i z e-przejściami, konfiguracja, obliczenie, akceptacja wejścia, uogólnienie funkcji przejścia na słowa - wprowadzenie intuicyjne.
  • 15 XII 2014. Równowżność klas automatów skończonych deterministycznych, niedeterministycznych i z e-przejściami. Równoważność klasy wyrażeń regularnych i klasy automatów skończonych.
  • 19 XII 2014. Dowód lematu o pompowaniu dla języków regularnych. Twierdzenie Myhill-Nerode, dowód. Domkniętość klas języków regularnych, bezkontekstowych i kontekstowych ze względu na operacje na językach.
  • 16 I 2015. Domkniętość klas języków rekurencyjnych i rekurencyjnie przeliczalnych ze względu na operacje sumy, przecięcia, dopełnienia, konkatenacji, domknięcia Kleeniego, języki uniwersalny i przekątniowe.
  • 23 I 2015. Operacje na językach: podstawienie, homomorfizm i ilorazy (ćwiczenia). Domkniętość klas języków ze względu na podstawienie i homomorfizm.
  • 30 I 2015. Przygotowanie do egzaminu, termin zerowy egzaminu.

 

 

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 / 2 / 0 / 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.