Języki, automaty i obliczenia/Test 8: Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wskaż, które z poniższych struktur są monoidami:

, gdzie

, gdzie jest zbiorem wszystkich liczb pierwszych


Wskaż stwierdzenia prawdziwe:


Wskaż, które z poniższych odwzorowań są homomorfizmami:

,

,

,

, ,

, ,


Dany niech będzie system przepisujący oraz niech . Wskaż stwierdzenia prawdziwe:


Wyrażenie regularne

reprezentuje język:

, ,

, ,


Niech oraz . Wskaż zdania prawdziwe:

minimalny automat akceptujący ma 5 stanów

ilość klas równoważności prawej kongruencji syntaktycznej wyznaczonej przez jest równa 4

monoid przejśc minimalnego automatu akceptującego ma 6 elementów


Niech będzie dowolnym językiem regularnym. Wskaż zdania prawdziwe:

jest rozpoznawany przez pewien niedeterministyczny automat skończenie stanowy z pustymi przejściami

jest rozpoznawany przez automat deterministyczny skończenie stanowy

jest rozpoznawany przez niedeterministyczny automat z pustymi przejściami o jednoelementowym zbiorze stanów początkowych

Nie istnieje automat niedeterministyczny z pustymi przejściami rozpoznający i taki, że zbiór stanów początkowych jest jednoelementowy

Nie istnieje gramatyka lewoliniowa generująca


Niech , będą językami rozpoznawanymi odpowiednio przez automaty o i stanach. Aby stwierdzić, dla dowolnego słowa , czy jest ono rozpoznawane przez oba automaty, wystarczy skonstruować odpowiedni automat mający

stanów

stanów

stanów

stanów

3 stany


Język składa się ze wszystkich słów nad alfabetem nie zawierających podsłowa . Wskaż wyrażenie regularne reprezentujące :


Wskaż warunki równoważne temu, by język był akceptowany przez automat skończenie stanowy:

Istnieje liczba naturalna taka, że każde słowo o długości można przedstawić jako katenację , gdzie , oraz .

Istnieje skończony monoid i homomorfizm taki, że .

jest sumą wybranych klas równoważności pewnej

kongruencji na :

.

jest akceptowany przez deterministyczny automat skończenie stanowy z jednym stanem końcowym.


Automat , gdzie , , ,

jest automatem minimalnym

rozpoznaje język ,

rozpoznaje język ,

rozpoznaje język ,

rozpoznaje język ,


Które z poniższych równości dla wyrażeń regularnych są prawdziwe?


Wskaż języki regularne:

lub


Dany jest automat , gdzie , , ,


Wskaż zdania prawdziwe:

.

Równoważny automat minimalny ma 2 stany.

Jeśli , to dla każdych takich, że zachodzi dla pewnego .

.

Jeśli , to jest podsłowem słowa .


Dany niech będzie automat niedeterministyczny , gdzie , , ,


Wskaż zdania prawdziwe:

.

.

Równoważny automat deterministyczny posiada 3 stany.

.

Równoważny minimalny automat deterministyczny posiada 4 stany.


Twierdzenie orzekające o równości zachodzącej pomiędzy rodziną języków regularnych a rodziną języków rozpoznawanych przez automaty o skończonej liczbie stanów znane jest jako:

twierdzenie Nerode'a

teza Churcha

lemat Ardena

lemat o pompowaniu

twierdzenie Kleene'ego


Wskaż monoid przejść automatu o następującej funkcji przejścia:



Niech będą językami regularnymi. Wskaż problemy rozstrzygalne.

nieskończoność


Algorytm determinizacji automatu:

jest deterministyczny

działa w czasie wielomianowym

może się zapętlić

działa w czasie eksponencjalnym

kończy działanie błędem, jeśli na wejściu podany został automat deterministyczny


Wskaż zdania prawdziwe:

istnieje algorytm minimalizacji automatu działający w czasie

żaden algorytm minimalizacji nie może działać szybciej niż w czasie

algorytm minimalizacji zawsze zwróci automat o mniejszej liczbie stanów niż automat podany na wejściu

algorytmy minimalizacji są algorytmami niedeterministycznymi

algorytmy minimalizacji nie działają dla automatów jednostanowych