Mikołaj Bojańczyk > Języki, Automaty i Obliczenia (wykład 2012) > Egzamin ustny

Egzamin ustny

Na sali są egzaminowane jednocześnie trzy czy cztery osoby. Każda osoba dostaje jedno czy dwa zadania z poniższej listy pytań teoretycznych. Jest czas na przygotowanie się. Po udzieleniu odpowiedzi, następują jedno czy dwa dodatkowe pytania o charakterze zadania, zazwyczaj związane z poprzednim pytaniem teoretycznym.

• Determinizacja automatów skończonych. Należy sformułować i najlepiej udowodnić twierdzenie o determinizacji. Pokazać przykład, że automat może wzrosnąć wykładniczo przy determinizacji.
• Jak z wyrażenia regularnego zrobić automat niedeterministyczny.
• Jak z automatu niedeterministycznego zrobić wyrażenie regularne.
• Sformułowć i udowodnić lemat o pompowaniu dla języków regularnych.
• Podać definicję gramatyki bezkontekstowej i generowanego przez nią języka (drzewo wyprowadzenia).
• Pokazać algorytm, który sprawdza, czy gramatyka generuje przynajmniej jedno słowo.
• Sformułować i udowodnić lemat o pompowaniu dla języków bezkontekstowych.
• Zdefiniować automat ze stosem. Jak z gramatyki zrobić automat ze stosem.
• Opisać algorytm CYK, który pozwala rozpoznawać języki bezkontekstowe w czasie sześciennym, ze względu na długość słowa.
• Zdefiniować całkowitą rozstrzygalność, zarówno w terminach maszyn deterministycznych jak i niedeterministycznych. Pokazać, że obie definicje są równoważne. Podobnie dla częściowej roztrzygalnośći.
• Pokazać przykład dwóch języków, które nie są całkowicie rozstrzygalne.
• Zdefiniować klasę NP i podać problem dla niej zupełny (np. SAT) <
• Zdefiniować klasę PSPACE i podać problem dla niej zupełny (np. QBF)