TPI zadania zestaw 2


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 q1 q3 q5 q3 q3 q5
1 q2 q5 q4 q5 q5 q1
b) DAS=({q0, q1, q2, q3, q4, q5, q6}, {0, 1}, , q0, {q6})
q0 q1 q2 q3 q4 q5 q6

0 q2 q2 q1 q6 q6 q5 q6
1 q1 q3 q4 q5 q5 q5 q5
c) 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}


Wyszukiwarka