EGZ-LIC MIMUW JAO
Języki, automaty i obliczenia
16 flashcards · Computer Science · by Wojciech Rzepliński
Lemat o pompowaniu
Języki regularne zamknięte na:
Sumę, konkatenację, gwiazdkę Kleene'ego, przecięcie (automat produktowy), dopełnienie (zamiana akceptujące na nieakceptujące), odwrócenie automatu, zamianę litery na język regularny, homomorfizm, ilorazy prawo i lewostronne
Algorytmy NFA i DFA. Algorytmy pustości, zawierania i pełności
DFA O(n) NFA O(n * k + i) Algorytm pustość i- szukanie ścieżki w grafie (DFS) Pełności i zawierania -> przepisać na przecięcie języków
Tw. Myhilla-Nerodego
Język L jest regularny wtedy i tylko wtedy, gdy jest relacja syntaktyczna ~L ma skończenie wiele klas abstrakcji. Każdy automat ma przynajmniej tyle stanów ile liczba klas abstrakcji L. Każdy automat o tej samej liczbie klas abstrakcji jest izomorficzny z automatem sytaktycznym A_L
Algorytm rafinacji podziałów
Wejście: automat deterministyczny Wyjście: automat syntaktyczny O(n^2 * s) - s - liczba liter, n - liczba stanów
Lemat o pompowaniu dla języków bezkontekstowych
Lemat Ogdena
Czy operacje są zamknięte na językach bezkontekstowych? Suma Konkratencaja Gwiazdka Kleene'go Odwrócenie Przecięcie Przecięcie z regularnym
Tak; Suma Konkratencaja Gwiazdka Kleene'go Odwrócenie Przecięcie z regularnym Nie: Przecięcie
Czym się różnią języki deterministyczne bezkontekstowe od bezkontekstowych?
Języki deterministyczne bezkontekstowe są zamknięte na dopełnenie, a nie są na sumę. Dla bezkontekstowych jest odwrotnie
Algorytmy na gramatykach: pustość gramatyk problem uniwersalności gramatyk parsowanie słów względem gramatyki
jest spoko nie istnieje, to problem nierostrzygalny tak, w czasie O(|G|^2 * n^3). G - gramatyka, n - długośc słowa
Maszyna turinga co trzyma w krotce przejścia
Język obliczalny
jeżeli istnieje maszyna Turinga która dla dowolnego słowa wejściowego terminuje oraz dla słowa należącego do języka daje 1, w przeciwnym wypadku daje 0 Zamknięte na sumy, przecięcie, dopełnienia
Język częściowo obliczalny
Dla należących do języka terminuje, a dla nienależących nieterminuje. Są zamknięte na sumy, przecięcia, obrazy i przeciwopbrazy
Język jest częściowo obliczalny twedy i tylko wtedy, gdy język L jak i jego dopełnienie są częściowo obliczalne
Algorytm działa na dwóch maszynaj jednocześnie aż jedna się skończy
Podaj przykłady problemów nierostrzygalnych
HALT HALT_Eps Czy dany program P wykona daną instrukcję? (osiągalność instrukcji) Układ wielomianów, czy ma rozwiązanie całkowitoliczbowe? Kafelkowanie nieograniczonego kwadratu (częściowo obliczalne) Kafelkowanie płaszczyzny (dopełneinie jest częściowo obliczalne) (Rober Berger) Problem uniwersalności gramatyk Problem jednoznaczności gramatyk (czy jeden ciąg derywacji dla każdego słowa) Problem czy gramatyka zawiera palindrom Problem Posta (Emil Post)
Tw. Godla o niezupełności