Teoria automatów i języków formalnych

Wykład, realizacja - jesień 2025

1. 8 X 2025. Wyrażenia regularne. Języki generowane przez wyrażenia regularne. Równoważność wyrażeń regularnych. Lemat Myhill-Nerode, lemat o pompowaniu dla języków regularnych. Gramatyki regularne (prawostronnie liniowe i lewostronnie liniowe) - definicja.

Wykład, realizacja - jesień 2024

1. 2 X 2024. Informacje organizacyjne. Pojęcia podstawowe: alfabet, słowo nad alfabetem, zbiór wszystkich słów nad alfabetem, porządek kanoniczny, przeliczalność zbioru słów, język nad alfabetem, nieprzeliczalność zbioru języków. Gramatyka, wywód, język generowany przez gramatykę. Definicje relacji prawostronnie niezmienniczej i indukowanej przez język.
2. 9 X 2024. Wyrażenia regularne. Języki generowane przez wyrażenia regularne. Równoważność wyrażeń regularnych. Lemat Myhill-Nerode, lemat o pompowaniu dla języków regularnych. Gramatyki regularne (prawostronnie liniowe i lewostronnie liniowe) - definicja.
3. 16 X 2024. Gramatyki bezkontekstowe, drzewa wywodu, jednoznaczność wywodu słów, jednoznaczność gramatyk i języków. Symbole bezużyteczne, ich identyfikacja i usuwanie. Symbole wycieralne, produkcje jednostkowe. Upraszczanie gramatyk. Postać normalna Chomskiego, przekształacnie gramatyki bezkontekstowej do postaci normalnej Chomskiego.
4. 23 X 2024. Języki bezkontekstowe: lemat o pompowaniu, dowód, zastosowanie. Lemat Ogdena, dowód. Algorytm Cocke-Younger-Kasami, zastosowania (prznależność słowa do języka, drzewa wywodu).
   - - - 30 X 2024. Wykład odwołany.
5. 6 XI 2024. Języki bezkontekstowe: postać normalna Greibach. Gramatyki kontekstowe i nieograniczone, postać normalna gramatyk kontekstowych, metoda przekształcania do postaci normalnej.
6. 13 XI 2024. Klasa języków rekurencyjnie przeliczalnych - definicja. Gramatyki kontekstowe i nieograniczone, przykłady. Maszyny Turinga, model podstawowy, modyfikacje modelu podstawowego, maszyny z taśmą wielościeżkową, równoważność modyfikacji z modelem podstawowym, maszyny wielotaśmowe. (ML)
7. 20 XI 2024. Maszyny Turinga z wielotaśmowe, przykład, wnoważność z maszynami jednotaśmowymi, dowód. Maszyny Turinga niedeterministyczne.
8. 27 XI 2024. Równoważność klas maszyn Turinga niedeterministycznych i niedeterministycznych. Automaty liniowo ograniczone. Automaty ze stosem, definicja, przykład.
9. 4 XII 2024. Automaty ze stosem, warunki determinizmu, równoważność akceptacji stanem akceptującym oraz pustymi stosem i wejściem, automaty ze stosem jako ograniczone maszyny Turinga. Automaty skończone deterministyczne i niedeterministyczne, konfiguracja, obliczenie, przykłady.
10. 11 XII 2024. Automaty skończone deterministyczne, niedeterministyczne i z e-przejściami, obliczenie, przykłady. Domknięcie funkcji przejścia. Równoważność klas automatów deterministycznych i niedeterministycznych.
11. 18 XII 2024. Równoważność klas automatów deterministycznych, niedeterministycznych i z e-przejściami. Równoważność klas wyrażeń regularnych, automatów skończonych i gramatyk regularnych. Domkniętość klasy języków regularnych ze względu na operacje na językach.
12. 15 I 2025. Lemat o pompowaniu dla języków regularnych, twierdzenie Myhill-Nerode, dowody, minimalne deterministyczne automaty skończone. Kodowanie gramatyk, kodowanie maszyn Turinga. Język przekątniowy w klasie języków kontekstowych.
13. 22 I 2025. Hierarchia Chomskiego: ścisłe zawieranie klas języków, język przekątniowy w klasie języków rekurencyjnie przeliczalnych, język uniwersalny, język przekątniowy w klasie języków kontekstowych - wyjasnienie, języki i ich dopełnienia, gramatyki a maszyny Turinga i automaty liniowo ograniczone.
14. 29 I 2025. Zastosowania praktyczne gramatyk bezkontekstowych: gramatyki LL(1), gramatyka generacji wyrażeń arytmetycznych i translacji do postaci przyrostkowej (nie obowiązuje na egzaminie).
15. 31 I 2025. Egzamin zerowy.

Ćwiczenia, realizacja - jesień 2024

Informacje o ćwiczeniach są na stronach internetowych prowadzących: prof. Anna Zamojska-Dzienio, prof. Konstanty Junosza-Szaniawski, dr inż. Janusz Rafałko

Program przedmiotu:

Program wykładu:

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

Literatura podstawowa:

1. Hopcroft J.E. Ullman J.D., Wprowadzenie do teorii automatów, jezyków i obliczen, WNT
2. W. Homenda, Elementy lingwistyki matematycznej i teorii automatów, WPW
3. W. Homenda, W. Pedrycz, Automata Theory and Formal Languages, De Gruyter, pp. 1-231, 2022.

Przedmioty poprzedzajace:

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

Regulamin zaliczenia przedmiotu (5 października 2021):

1. zaliczenie przedmiotu uzyskuje się przez zaliczenie egzaminu w terminach wyznaczonych przez dziekanat (dwa terminy w sesji zimowej, jeden termin w sesji jesiennej),
2. zaliczenie egzaminu wymaga uzyskania zaliczenia części praktycznej i części teoretycznej egzaminu (uzyskania ponad 50% punktów za każdą część) w tym samym terminie wyznaczonym przez dziekanat,
3. osoby, które dobrze zaliczą ćwiczenia (uzyskają wynik powyżej progu zwolnienia), mogą skorzystać z jednokrotnego zwolnienia z części praktycznej przy pierwszym przystąpieniu do egzaminu w dowolnym z trzech terminów wyznaczonych przez dziekanat,
4. ocena końcowa jest średnią z ocen za część praktyczną (lub uzyskaną z ćwiczeń) 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.),
5. 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, do części teoretycznej można przystąpić po zaliczeniu części praktycznej, na części teoretycznej nie można korzystać z żadnych pomocy.

Regulamin zaliczenia przedmiotu (18 października 2016):

1. zaliczenie przedmiotu uzyskuje się przez zaliczenie egzaminu w terminach wyznaczonych przez dziekanat (dwa terminy w sesji zimowej, jeden termin w sesji jesiennej),
2. zaliczenie egzaminu wymaga uzyskania zaliczenia części praktycznej i części teoretycznej egzaminu (uzyskania ponad 50% punktów za każdą część) w tym samym terminie wyznaczonym przez dziekanat,
3. osoby, które zaliczą część laboratoryjną, mogą skorzystać z jednokrotnego zwolnienia z części praktycznej przy pierwszym przystąpieniu do egzaminu w dowolnym z trzech terminów wyznaczonych przez dziekanat,
4. ocena końcowa jest średnią z ocen za część praktyczną (lub uzyskaną z części laboratoryjnej) 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.),
5. 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, do części teoretycznej można przystąpić po zaliczeniu części praktycznej, 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, do części teoretycznej można przystąpić po zaliczeniu części praktycznej, na sprawdzianach części teoretycznej nie można korzystać z żadnych pomocy.