Teoria automatów i języków formalnych

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.

Ć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

Wykład, realizacja - jesień 2023

1. 4 X 2023. 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. 11 X 2023. Relacja indukowana przez język, uzupełnienia. 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
3. 18 X 2023. Lemat Myhill-Nerode, lemat o pompowaniu dla języków regularnych. Gramatyki bezkontekstowe, drzewa wywodu, jednoznaczność wywodu słów, jednoznaczność gramatyk i języków. Symbole bezużyteczne, ich identyfikacja i usuwanie.
4. 25 X 2023. Gramatyki bezkontekstowe, symbole wycieralne, produkcje jednostkowe. Upraszczanie gramatyk. Postacie normalne Chomskiego i Greibach gramatyk bezkontekstowych.
5. 8 XI 2023. Algorytm Cocke-Younger-Kasami, zastosowania (prznależność słowa do języka, drzewa wywodu). Języki bezkontekstowe: lemat o pompowaniu, lemat Ogdena, dowody.
6. 15 XI 2023. Lemat o pompowaniu, lemat Ogdena, zastosowania. Nie obowiązuje na zaliczenie: Zastosowania praktyczne gramatyk bezkontekstowych: gramatyki LL(1), gramatyka generacji wyrażeń arytmetycznych i translacji do postaci przyrostkowej.
7. 22 XI 2023. Gramatyki kontekstowe i nieograniczone, przykłady. Klasy jęzzyków kontekstowych i rekurencyjnie przeliczalnych. Postać normalna gramatyk kontekstowych.
8. 29 XI 2023. Maszyny Turinga.
9. 20 XII 2023. Maszyny Turinga. Automaty liniowo ograniczone.
10. 3 I 2024. Równoważność maszyn Turinga i gramatyk nieograniczonych. Klasy języków rekurencyjnych i rekurencyjnie przeliczalnych, języki przekątniowy, uniwersalny i ich dopełnienia. Równoważność automatów liniowo ograniczonych i gramatyk kontekstowych.
11. 9 I 2024. Język przekątniowy w klasie języków kontekstowych. Automaty ze stosem, determinizm, akceptacja stanem akceptującym oraz pustym wejściem i pustym stosem. Równoważność klasy gramatyk bezkontekstowych i klasy automatów ze stosem.
12. 10 I 2024. Automaty skończone deterministyczne, niedeterministyczne i z e-przejściami. Równoważność klas automatów skończonych deterministycznych, niedtereministycznych i z e-przejściami. Uogólnienie funkcji przejścia.
13. 16 I 2024. Równoważność klasy automatów skończonych, klasy wyrażeń regularnych i klasy gramatyk regularnych. Lemat o pompowaniu dla języków regularnych, twierdzenie Myhill-Nerode, dowody, minimalne deterministyczne automaty skończone.
14. 17 I 2024. Domkniętość klas języków ze względu na operacje na językach.
15. 24 I 2024. Egzamin zerowy.

Ćwiczenia, realizacja - jesień 2023

Informacje o ćwiczeniach są na stronie internetowej prowadzącego: dr inż. Janusz Rafałko

Wykład, realizacja - jesień 2022

1. 5 X 2022. 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ę.
2. 12 X 2022. Definicje relacji prawostronnie niezmienniczej i indukowanej przez język (z ćwiczeń). 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 - przykłady zastosowania.
3. 19 X 2022. Lemat Myhill-Nerode, lemat o pompowaniu dla języków regularnych. Gramatyki bezkontekstowe, drzewa wywodu, jednoznaczność wywodu słów, jednoznaczność gramatyk i języków. Symbole bezużyteczne, ich identyfikacja i usuwanie.
4. 26 X 2022. Gramatyki bezkontekstowe, symbole wycieralne, produkcje jednostkowe. Upraszczanie gramatyk. Postacie normalne Chomskiego i Greibach gramatyk bezkontekstowych.
5. 2 XI 2022. Języki bezkontekstowe: lemat o pompowaniu, lemat Ogdena, dowody, zastosowania; algorytm Cocke-Younger-Kasami, zastosowania (prznależność słowa do języka, drzewa wywodu). Zastosowania praktyczne gramatyk bezkontekstowych: gramatyki z translacją - nie obowiązuje na zaliczenie.
6. 16 XI 2022. Zastosowania praktyczne gramatyk bezkontekstowych: gramatyki LL(1), gramatyka generacji wyrażeń arytmetycznych i translacji do postaci przyrostkowej - nie obowiązuje na zaliczenie. Gramatyki kontekstowe i nieograniczone, przykłady.
7. 23 XI 2022. Postać normalna gramatyk kontekstowych. Maszyny Turinga, model podstawowy.
8. 30 XI 2022. Maszyny Turinga: modyfikacje modelu podstawowego, maszyny z taśmą wielościeżkową i ich równoważność z maszynami w modelu podstawowym, maszyny wielotaśmowe.
9. 7 XII 2022. Maszyny Turinga wielotaśmowe - dowód równoważności z maszynami jednotasmowymi. Maszyny Turinga niedeterministyczne.
10. 10 XII 2022. Równoważność klas maszyn Turinga niedeterministycznych i deterministycznych, koszt deterministycznej symulacji. Automaty liniowo ograniczone. Automaty ze stosem, definicja, konfiguracja, obliczenie, przykłady.
11. 21 XII 2022. Automaty ze stosem, determinizm, akceptacja stanem akceptującym oraz pustym wejściem i stosem, automaty ze stosem jako ograniczone maszyny Turinga. Deterministyczne automaty skończone, definicja, konfiguracja, obliczenie, przykłady.
12. 4 I 2023. Niedeterministyczne automaty skończone, definicja, konfiguracja, obliczenie, przykłady. Równoważność klas automatóe deterministycznych i niedeterministycznych. Automaty skończone z e-przejściami, definicja, e-domknięcie, konfiguracja, obliczenie, przykłady.
13. 11 I 2023. Równoważność klasy automatów skończonych i klasy wyrażeń regularnych. Lemat o pompowaniu dla języków regularnych, twierdzenie Myhill-Nerode, dowody, minimalne deterministyczne automaty skończone.
14. 18 I 2023. Równoważność klas automatów ze stosem i gramatyk bezkontekstowych, automatów liniowo ograniczonych i gramatyk kontekstowych, maszyn Turinga i gramatyk nieograniczonych. Podstawienie i homorfizm. Domkniętość klas języków regularnych i bezkontekstowych ze względu na operacje na językach.

Ćwiczenia, realizacja - jesień 2022

Informacje o ćwiczeniach są na stronie internetowej prowadzącego: 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 zaliczą ćwiczenia, 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, 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, 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.