7738996299

Zadania

Zadanie 2.1. Pokazać, że każdy niedeterministyczny automat z warunkiem Mullera jest równoważny pewnemu NBA. Rozwiązanie na stronie 72.

Zadanie 2.2. Pokazać, że języki rozpoznawane przez deterministyczne automaty z warunkiem Buchiego są zamknięte na przecięcie. Rozuńązanie na stronie 73.

Zadanie 2.3. Pokazać, że następujący język nie jest w-regularny:

{aⁿ'baⁿ²b- ■ ■ : lim n, = oo}.

Rozwiązanie na stronie 74-

Zadanie 2.4. Słowo ostatecznie okresowe to słowo postaci uw^u dla w,v £ A⁺. Pokazać, że jeśli dwa języki ui-regulame zawierają te same słowa ostatecznie okresowe, to muszą być równe. Rozwiązanie na stronie 75.

Zadanie 2.5. Wskazać język w-regularny, który nie jest różnicą dwóch języków rozpoznawanych przez deterministyczne automaty z warunkiem Buchiego. Rozwiązanie na stronie 77.

Zadanie 2.6. Zaprojektować algorytm, który sprawdza czy język rozpoznawany przez dany NBA jest przeliczalny. Rozuńązanie na stronie 78.

Zadanie 2.7. Rozważmy trzy relacje a la Myhill Nerode, które są zadane przez język słów nieskończonych L C A°, ale porównują słowa skończone w,w¹ £ A*.

w w' jeśli uwv € L <=> uw'v € L dla każdych u € A* ,v £ A^u

w

(uwv € L •*=*• uw'v € L 1 u(wv)^u € L •*==> u(w'v)^u £ L

dla każdych u £ .A*,v € A? dla każdych u,v £ A*

gdzie u' € A^u otrzymano zu€ A“

w w¹ jeśli u € L <=$■ u' £ L przez zamienienie (skończonej lub nie) ilości rozłącznych wystąpień w naw'.

Niech i = 1,2. Wskazać język L, który ma skończenie wiele klas abstrakcji w relacji w relacji ale nieskończenie wiele klas abstrakcji w relacji ~£^ł_1. Wskazać język L, który nie jest w-regularny, ale dla którego ma skończenie wiele klas abstrakcji.

18