kolos2

1. Przedstaw graf reprezentujący działanie maszyny Turinga analizującej nieskończony ciąg złożony z liter {a,b,c}. Jeżeli maszyna napotka literę 'b' zamienia ją miejscami z poprzednią literą w ciągu.

np. cbab => cabb => cbba => bbca

2. Napisz algorytm, wybierz instrukcję kluczową, oszacuj złożoność czasową algorytmu. Podaj rząd złożoności oraz dowody dla dużego O oraz omegi.

Tablica n x n, gdzie n-parzyste
(tablica w załączniku)



3. Napisz wyrażenie regularne definiujące wszystkie l. nieparzyste w kodzie dziesiętnym zawierające co najwyżej dwie czwórki.

4. Dla podanego wyrażenia regularnego narysuj automat z epsilon przejściami oraz napisz równorzędną gramatykę:

[(ABC)+| 010]*


5.  Dla podanej gramatyki przedstaw 3 przebiegi generacji elementów do zbioru jęz. użytych w kategoriach syntaktycznych,

<a> --> <a><b><c>
<a> --> 8
<b> --> <a> + <b>
<b> --> epsilon
<c> --> 5|7


Wyszukiwarka

Podobne podstrony:
kolos2 rozw id 242277 Nieznany
kolos2grunty, mechanika gruntów, mechanika gruntów
kolos2
fizy2 kolos2
lach kolos2 opracowane
kolos2
Przykłady do rozwiązania - tablica korelacyjna, Informatyka i Ekonometria SGGW, Semestr 2, Statystyk
kolos2
HMS kolos2
ekologia kolos2
Algorytmy kolos2
gotowe kolos2
sip 2 kolos sem 7, sip7 kolos2, SIP VII sem kolos2
sip 2 kolos sem 7, sip7 kolos2, SIP VII sem kolos2
mat kolos2
lach kolos2 opracowane
Mathcad, kolos2

więcej podobnych podstron