Automaty a rekurencja 2016/2017
Zadania domowe (ostatnia aktualizacja: 23.12.2016 - obecnie jest 6 zadań)
24.01.2017
Wykład
Udowodniliśmy, że wszystkie grafy w hierarchii Caucala można uzyskać
wykonując interpretacje tylko w drzewach deterministycznych (zamiast we wszystkich).
Ponadto udowodniliśmy, że grafy na n-tym poziomie hierarchii Caucala to dokładnie epsilon-ściągnięcia grafów konfiguraji automatów ze stosem rzędu n (bez collapse).
Według tego artykułu.
Uzasadniliśmy też, że grafy w hierarchii Caucala mają rozstrzygalną logikę MSO, w przeciwieństwie do grafów konfiguracji automatów ze stosem wyższego rzędu z collapse.
Ćwiczenia
- Omówienie zadań zaliczeniowych.
17.01.2017
Wykład
Udowodniliśmy, że deterministyczna hierarchia Caucala jest zamknięta na MSO-transdukcje oraz na operację "treegraph".
Według tego artykułu.
Ćwiczenia
- Istnieje graf G oraz MSO-interpretacja I takie, że grafu I(G) nie da się uzyskać z G za pomocą odwrotnego przekształcenia regularnego.
- Istnieje graf G oraz MSO-transdukcja t takie, że grafu t(G) nie da się uzyskać z G za pomocą MSO-interpretacji.
10.01.2017
Wykład
Zdefiniowaliśmy hierarchię Caucala oraz MSO-interpretacje i MSO-transdukcje.
Według tego artykułu.
Ćwiczenia
- Istnieje graf G oraz MSO-transdukcja t takie, że grafu t(G) nie da się uzyskać z G za pomocą MSO-interpretacji.
20.12.2016
Wykład
Udowodniliśmy, że automaty ze stosem rzędu n (niedeterministyczne / deterministyczne, z collapse lub bez) mogą rozpoznać więcej języków niż automaty ze stosem rzędu n-1.
Udowodniliśmy, że niedeterministyczne automaty ze stosem rzędu n i z wieloma dwukierunkowymi głowicami rozpoznają dokładnie wszystkie języki z klasy (n-1)-EXPTIME.
Według tego artykułu.
Zobacz notatki napisane przez
Rafała Stefańskiego.
Ćwiczenia
- Automat używający dodatkowej pamięci logarytmnicznej można zamienić na automat z wieloma (dwukierunkowymi) głowicami.
- Automaty ze stosem rzędu n (niedeterministyczne / deterministyczne, z collapse lub bez) generują więcej drzew niż automaty ze stosem rzędu n-1.
- Dowolny niedeterministyczny automat ze stosem rzędu 2 można zamienić na automat nie używający operacji collapse.
13.12.2016
Wykład
Udowodniliśmy n-EXPTIME-trudność problemu: czy drzewo generowane przez dany schemat rekurencyjny rzędu n jest akceptowane przez dany automat na drzewach.
Udowodniliśmy (n-1)-EXPTIME-trudność problemu: czy drzewo generowane przez dany schemat rekurencyjny rzędu n zawiera literę a.
Według tego artykułu.
Zobacz notatki.
Ćwiczenia
- Automaty z trywialnym warunkiem akceptacji i z kotrywialnym warunkiem akceptacji rozpoznają klasy języków będących nawzajem swoimi dopełnieniami.
- Język "U" można rozpoznać deterministycznym automatem rzędu 2 z collapse / niedeterministycznym bez collapse.
- Dowolny niedeterministyczny automat ze stosem rzędu 2 można zamienić na automat nie używający operacji collapse.
6.12.2016
Wykład
Znów rozważaliśmy problem: czy drzewo generowane przez dany schemat rekurencyjny jest akceptowane przez dany automat na drzewach.
Tym razem omówiliśmy algorytm, który ma szansę działać w praktyce, na typowych danych wejściowych (czyli nie tworzy od razu obiektów wielokrotnie wykładniczego rozmiaru, w przeciwieństwie do poprzednio poznanego algorytmu).
Według tego artykułu.
Zobacz notatki.
Ćwiczenia
- Przykłady do wykładu (jak algorytm działa dla konkretnego wejścia).
- Automaty z trywialnym warunkiem akceptacji i z kotrywialnym warunkiem akceptacji rozpoznają klasy języków będących nawzajem swoimi dopełnieniami.
29.11.2016
Wykład
Ustalmy jakiś model dla rachunku lambda-Y.
Pokazaliśmy jak wzbogacić dany lambda-Y term tak, aby w każdym wierzchołku generowanego drzewa oprócz oryginalnej etykiety wypisywał wartość w modelu dla poddrzewa zaczynającego się w tym miejscu.
Według tego artykułu, strony 23-24.
Zobacz notatki napisane przez Marka Sommera.
Ćwiczenia
- Rozstrzyganie, czy każde skończone drzewo generowane przez dany niedeterministyczny HORS należy do danego języka regularnego (przez redukcję do pojedynczego drzewa nieskończonego).
22.11.2016
Wykład
Pokazaliśmy jak skonstruować model dla rachunku lambda-Y, który pozwala
stwierdzić, czy dany automat akceptuje drzewo generowane przez term.
Według tego artykułu, strony 7-9.
Zobacz notatki.
Ćwiczenia
- Własność Churcha-Rossera dla rachunku lambda-Y (przemienność redukcji).
- Standaryzacja (zawsze możemy zaczynać od redukcji czołowych).
- Równoważność między HORS i CPDA działa także w przypadku niedeterministycznym (kodowanie języka drzew w jednym drzewie nieskończonym).
15.11.2016
Wykład
Najpierw pokazaliśmy jak zamienić automat CPDA na schemat rekurencyjny (mniej więcej według tego artykułu - strony 14-23).
Następnie zdefiniowaliśmy pewien rodzaj automatów skończonych rozpoznających drzewa nieskończone: niedeterministyczne automaty z trywialnym warunkiem akceptacji.
Zdefiniowaliśmy także czym jest model dla rachunku lambda-Y.
Ta druga część naśladuje nieco to, co jest napisane w tym artykule.
Zobacz notatki.
Ćwiczenia
- Drzewo generowane przez lambda-Y term jest jednoznacznie wyznaczone (nie
zależy od kolejności wykonywania redukcji).
- Jeśli w termie nie ma żadnego Y, to zaczyna się w nim pewien skończony ciąg redukcji, którego nie można przedłużyć.
8.11.2016
Wykład
Idziemy nadal mniej więcej według tego artykułu
(z pewnymi zmianami notacyjnymi). Dzisiaj:
- definicja maszyny Krivine'a (str. 9-10),
- tłumaczenie z termu lambda-Y (a dokładniej z maszyny Krivine'a) do automatu CPDA, rzędu o jeden gorszego niż można (str. 23-26),
- rząd można poprawić o 1 gdy term jest w postaci kanonicznej (str. 29).
Zobacz notatki.
Ćwiczenia
- Transformacja z wykładu na przykładach.
- Drzewo generowane przez lambda-Y term jest jednoznacznie wyznaczone (nie
zależy od kolejności wykonywania redukcji).
25.10.2016
Wykład
Tłumaczenie termu rachunku lambda-Y na równoważny schemat rekurencyjny,
mniej więcej wg tego artykułu,
strony 16-21:
- prostsze tłumaczenie, zwiększające rząd o 1,
- sprawadzanie termu do postaci kanonicznej (nie zmieniające rzędu),
- tłumaczenie dla termów w postaci kanonicznej, nie zmieniające rzędu.
Zobacz notatki napisane przez
Rafała Stefańskiego.
Ćwiczenia
- Transformacja z wykładu na przykładach.
- Drzewo generowane przez lambda-Y term jest jednoznacznie wyznaczone (nie
zależy od kolejności wykonywania redukcji).
18.10.2016
Wykład
- Otypowany rachunek lambda-Y - definicja; drzewo generowane przez term.
- Tłumaczenie schematu rekurencyjnego na równoważny term rachunku
lambda-Y, wg tego artykułu, strona 15.
Zobacz notatki napisane przez
Marka Sommera.
Ćwiczenia
- Skonstruuj schemat rekurencyjny rzędu 2 generujący drzewo, którego gałęzie to
a^k b^{2^k}.
- Skonstruuj schemat rekurencyjny rzędu 3 generujący drzewo, którego gałęzie to
a^k b^{2^{2^k}}.
- Skonstruuj 3-PDA dla {a^(2^(2^n))}.
- Udowodnij poprawność tłumaczenia z wykładu.
11.10.2016
Wykład
Schematy rekurencyjne - definicja i przykłady; drzewo generowane przez
schemat rekurencyjny.
Zobacz notatki napisane przez
Roberta Błaszkiewicza.
Ćwiczenia
Schematy rekurencyjne rzędu 1 i gramatyki bezkontekstowe są równoważne.
Idea: Z gramatyki do schematu - prosto.
W drugą stronę - dokładnie odwrotne tłumaczenie możemy zrobić przy założeniu, że w schemacie mamy tylko nieterminale biorące
co najwyżej jeden argument, przy czym (jeśli argument jest, to) musi on występować po
prawej stronie reguł.
Dla dowolnego schematu musimy najpierw sprowadzić do tej postaci (co jest
możliwe, bo "i tak co najwyżej jeden argument zostanie użyty").
4.10.2016
Wykład
Wprowadzenie - slajdyĆwiczenia
- Języki K, L - bezkontekstowe. Czy są bezkontekstowe:
- dopełnienie L
- L*
- L czytany od tyłu
- suma K i L
- przecięcie K i L
- Czy są rozstrzygalne dla K, L bezkontekstowych:
- czy L niepusty
- czy L=A*
- czy K i L mają niepuste przecięcie
- czy K=L
- czy L regularny
- Czy dla każdego automatu ze stosem istnieje deterministyczny automat ze
stosem rozpoznający ten sam język? (przykład: a^n b^2n + a^n b^n)
- Zad 1 oraz 2a,b,c dla deterministycznych automatów ze stosem.
- Przypomnienie redukcji: automat ze stosem <-> gramatyka bezkontekstowa.
- Skonstruuj 2-PDA dla {a^n b^n c^n}.
- Skonstruuj 3-PDA dla {a^(2^(2^n))}.