Informatyka stacjonarna, 1 st., sem. 3 rok akad. 2008/2009 Teoretyczne Podstawy Informatyki zadania, zestaw 2 Automaty skończone, wyrażenia regularne, własności języków regularnych 1. Które z poniższych tożsamości dla wyrażeń regularnych są prawdziwe, a które nie a) a (b | c) = ab | ac b) (a*)* = a* c) a* = ( | a)+ d) (ab)c = (ba)c e) bb | ab | bab = (b (|a) | a) b f) a* | a = (a+ | a)* g) (ab | a)* a = a (ba | a)* h) b (ab | b)* a = aa* b (aa* b)* i) (a | b)* = a* | b* j) (a | b)* = a* b* k) ab*c | b* = (a | ) b*(c | ) l) (a | b)*=((aa | bb) | (ba | ab))* m) (a | b)* b = (a* b)* n) (ab | a)* ab = (aa* b)* o) a(c | ba)+ = ab(a | ac | acba)+ | ac p) (a(ab)*b)* = (ab)* | aa (ba)* bb 2. Podać wyrażenia regularne realizujące następujące języki regularne a) L(W)={0120, 01120, 011120, 0111120, ...} b) L(W)={ab, bc, abb, bbc, abbb, bbbc, abbbb, bbbbc, ...} c) L(W)={abb, aaabb, aaaaabb, ... , abbbb, aaabbbb, aaaaabbbb, & , abbbbbb, aaabbbbbb, aaaaabbbbbb, ...} d) L(W)={00, 00111, 0011100, 0011100111, 001110011100, ...} e) zbiór wszystkich łańcuchów zawierających na pozycjach parzystych "1"; Ł={0,1} f) zbiór wszystkich łańcuchów, w których dwa pierwsze symbole są takie same jak dwa ostatnie; Ł={a,b} g) zbiór wszystkich łańcuchów zawierających dwa kolejne zera po których w dalszej części łańcucha są dwie kolejne jedynki - są to jedyne powtórzenia symboli; Ł={0,1} h) zbiór wszystkich łańcuchów zawierających co najwyżej jedną parę kolejnych zer i co najwyżej jedną parę kolejnych jedynek; Ł={0,1} i) zbiór wszystkich łańcuchów, w których nie występują więcej niż dwa zera po kolei; Ł={0,1} 3. Podać wyrażenia regularne akceptujące języki podane w zadaniu 3 z poprzedniego zestawu zadań 4. W trzypiętrowym bloku przejazd windy z dowolnego piętra na piętro położone o jeden poziom wyżej oznaczamy symbolem "G", natomiast przejazd na piętro położone o jeden poziom niżej oznaczamy "D". Podać wyrażenie regularne opisujące wszystkie możliwe trasy windy rozpoczynające i kończące się na parterze. Narysować także równoważny AS. 5. Podać wyrażenia regularne akceptujące języki podane w zadaniu 5 z poprzedniego zestawu zadań Informatyka stacjonarna, 1 st., sem. 3 rok akad. 2008/2009 6. Podać wyrażenia regularne definiujące poprawne łańcuchy reprezentujące w języku C a) komentarz b) deklarację jednej zmiennej lub kilku kolejnych zmiennych typu całkowitego c) deklarację tablicy znaków bez inicjalizacji jej zawartości lub z inicjalizacją za pomocą łańcucha tekstowego d) deklarację jednowymiarowej tablicy całkowitoliczbowej z zainicjowanymi wartościami początkowymi dla elementów tablicy 7. Skonstruować deterministyczne automaty skończone równoważne podanym wyrażeniom regularnym. Zastosować konwersję WR -NAS NAS DAS. a) 10 | (00 | 11) 1* 0 b) (( (00)* | 11)* | 0) 1 c) (a | bba)* ( | b | bb) d) (a*bc* | ab*c)* e) ((0 | 1) (0 | 1))* | ((0 | 1) (0 | 1) (0 | 1))* 8. Podać wyrażenia regularne równoważne podanym automatom skończonym. Zastosować metodę eliminacji stanów. a) start q0 q1 1 1 1 0 0 1 0 q2 q3 0 b) 0 0 0 start 1 1 0 q0 q1 q2 q3 1 1 c) a b b a start b q3 q0 q1 q2 b a c d) start q0 0 q1 1 0 1 0 1 0 q2 1 q3 Informatyka stacjonarna, 1 st., sem. 3 rok akad. 2008/2009 9. Zminimalizować podane automaty skończone a) DAS=({q0, q1, q2, q3, q4, q5}, {0, 1}, , q0, {q5}) q0 q1 q2 q3 q4 q5
0 q0 q2 q5 q4 q5 q5 1 q1 q3 q1 q3 q1 q1 10. Podać automaty z wyjściem Moore'a lub Mealy'ego realizujące następujące języki: a) automat zwracający resztę z dzielenia przez 3 dla ciągu wejściowego interpretowanego jako liczba binarna; Ł={0,1}, "={0,1,2} b) j/w tylko że resztę z dzielenia przez 6; Ł={0,1}, "={0,1,2,3,4,5} c) automat podający jakie z trzech symboli "f", "i", "e" wystąpiły w ciągu wejściowym; Ł={a,b, ..., z}, "={0,f,i,e,x,y,z,a}. Alfabet wyjściowy należy interpretować następująco: 0 żaden z symboli "f", "i", "e" nie wystąpił w łańcuchu f wystąpił tylko symbol "f" i wystąpił tylko symbol "i" e wystąpił tylko symbol "e" x wystąpiły symbole "f" i "i", nie wystąpił symbol "e" y wystąpiły symbole "f" i "e", nie wystąpił symbol "i" z wystąpiły symbole "e" i "i", nie wystąpił symbol "f" a wystąpiły wszystkie trzy symbole "f", "i", "e" d) automat podający maksymalną ilość powtórzeń dowolnego z symboli alfabetu; Ł={0,1}, "={J,D,T,C}. Alfabet wyjściowy należy interpretować następująco: J pojedyncze wystąpienie symbolu 0 lub 1, D dwukrotne powtórzenie dowolnego symbolu, T trzykrotne powtórzenie, C czterokrotne lub wielokrotne powtórzenie; np. dla ciągu 01011010001010110 odpowiedzią automatu powinien być symbol "T". e) automat podający czy na pozycjach parzystych i nieparzystych w łańcuchu występują te same symbole; Ł={0,1}, "={a,b,c,d,p,r,s,t,w}. Alfabet wyjściowy należy interpretować następująco: a na pozycjach nieparzystych 0, na parzystych 0 b na pozycjach nieparzystych 0, na parzystych 1 c na pozycjach nieparzystych 1, na parzystych 0 d na pozycjach nieparzystych 1, na parzystych 1 p na pozycjach nieparzystych 0, na parzystych dowolny symbol r na pozycjach nieparzystych 1, na parzystych dowolny symbol s na pozycjach parzystych 0, na nieparzystych dowolny symbol t na pozycjach parzystych 1, na nieparzystych dowolny symbol w dowolny ciąg symboli np. dla ciągu 01011101 odpowiedzią automatu powinien być symbol "t". Informatyka stacjonarna, 1 st., sem. 3 rok akad. 2008/2009 11. Korzystając z własności zamkniętości języków regularnych skonstruować: a) DAS realizujący sumę teoriomnogościową języków L*"M; L(W)=010*1*; M={w; przedostatni symbol w jest różny od ostatniego} b) DAS realizujący iloczyn teoriomnogościowy języków L)"M; L={w; w zawiera "011"}; M={w; w zawiera "100"} c) WR realizujące dopełnienie języka L ; i) L={w; w zawiera łańcuch o postaci 101 } ii) L={w; dwa pierwsze symbole w są takie same jak dwa ostatnie} d) DAS lub WR realizujące różnicę języków L M; L={w; w zaczyna i kończy się "1" }; M(W)=(00|11)+ e) WR realizujące odwrócenie języka LR; L(W)=(001|1)*101 12. Jeżeli L jest językiem, natomiast a symbolem, to iloraz L przez a oznaczany jako L/a jest zbiorem łańcuchów w takich, że wa"L. Definiuje się także pochodną a\L (dL/da) jako zbiór łańcuchów w takich, że aw"L. Podać kilka przykładowych języków, symboli i ich ilorazów oraz pochodnych. Które z poniższych tożsamości są prawdziwe: a) (L/a)a = L b) a(a\L) = L c) (La)/a = L d) a\(aL) = L 13. Definiuje się następujące operatory na językach: a) min(L) = {w"L; żaden właściwy prefiks w nie należy do L} b) max(L) = {w"L; wx "L dla dowolnego x `" } c) pocz(L) = {w"L; wx"L dla pewnego x} d) pol(L) = {w; wx"L dla pewnego x dla którego |x|= |w|} e) alt(L,M) = {w; zbiór wszystkich kombinacji słów z języków L i M, rozmieszczonych w taki sposób, że na nieparzystych pozycjach znajdują się kolejne symbole ze słów należących do języka L, a na parzystych pozycjach symbole ze słów należących do języka M} Zadanie rozwiązać dla języków: L1=a*ba, L2=(01)+, L3=ab+, L4=10+1, L5=(0|1)*1; a operator alt zastosować dla par języków: L1 i L2, L1 i L3, L4 i L5 14. Korzystając z lematu o pompowaniu wykazać, że następujące języki są lub nie są regularne a) L={0n1m; n,m e" 1} b) L={0n1n; n e" 1} c) L={0n; n=k2, k e" 1} d) L={0n1m; n `" m, n,m e" 1} e) L={wwR}