Prvi kolokvijum 2017. godine održan je 28. oktobra i trajao je dva sata. Radna verzija postavke roka je dostupna sa stranice predmeta (arhiva).
1. zadatak
Postavka
Projektovati potisni automat koji prepoznaje sledeći skup sekvenci: 
Iz zadatog skupa izabrati jednu sekvencu dužine veće od tri i prikazati proces njenog prepoznavanja.
Rešenje
Prvo stanje potisne mašine za prepoznavanje sekvence
|
|
a
|
b
|
c
|
─┤
|
| ∇
|
|
REJECT
|
REJECT
|
REJECT
|
| A
|
|
|
|
ACCEPT
|
| B
|
|
|
|
REJECT
|
Drugo stanje potisne mašine za prepoznavanje sekvence
|
|
a
|
b
|
c
|
─┤
|
| A
|
REJECT
|
ADVANCE
|
REJECT
|
ACCEPT
|
| B
|
REJECT
|
ADVANCE
|
|
REJECT
|
Treće stanje potisne mašine za prepoznavanje sekvence
|
|
a
|
b
|
c
|
─┤
|
| A
|
REJECT
|
REJECT
|
REJECT
|
ACCEPT
|
| B
|
REJECT
|
REJECT
|
|
REJECT
|
Rad ovog automata možemo prikazati na sekvenci aabbbc.
| Stek
|
Sekvenca
|
Stanje
|
Operacije
|
| ∇
|
aabbbc─┤
|
1
|
PUSH(A), ADVANCE
|
| ∇A
|
abbbc─┤
|
1
|
PUSH(B), ADVANCE
|
| ∇AB
|
bbbc─┤
|
1
|
ADVANCE, STATE(S2)
|
| ∇AB
|
bbc─┤
|
2
|
ADVANCE
|
| ∇AB
|
bc─┤
|
2
|
ADVANCE
|
| ∇AB
|
c─┤
|
2
|
RETAIN, STATE(S3)
|
| ∇AB
|
c─┤
|
3
|
POP, ADVANCE
|
| ∇A
|
─┤
|
3
|
ACCEPT
|
2. zadatak
Postavka
Stablo iz postavke drugog zadatka.
- Direktno na zadatom sintaksnom stablu jednog regularnog izraza naznačiti poništivost, i funkcije prva i poslednja pozicija.
- Nacrtati tabelu sa vrednostima funkcije sledeća pozicija.
- Na osnovu zadatog stabla i rezultata pod a) odrediti konačni automat. Obavezno navesti postupak. Nije potrebna minimizacija.
Rešenje
Stablo iz rešenja drugog zadatka.
Tabela sledećih pozicija
| Pozicija
|
Sledeća pozicija
|
| 1
|
3
|
| 2
|
3
|
| 3
|
4, 5, 8
|
| 4
|
4, 5, 8
|
| 5
|
6
|
| 6
|
7, 8
|
| 7
|
7, 8
|
| 8
|
-
|
Postupak pretvaranja sintaksnog stabla u deterministički konačni automat
|
|
+
|
-
|
d
|
.
|
Prihvata
|
| 1, 2, 3
|
3
|
3
|
4, 5, 8
|
|
0
|
| 3
|
|
|
4, 5, 8
|
|
0
|
| 4, 5, 8
|
|
|
4, 5, 8
|
6
|
1
|
| 6
|
|
|
7, 8
|
|
0
|
| 7, 8
|
|
|
7, 8
|
|
1
|
Deterministički konačni automat
|
|
+
|
-
|
d
|
.
|
Prihvata
|
| A
|
B
|
B
|
C
|
|
0
|
| B
|
|
|
C
|
|
0
|
| C
|
|
|
C
|
D
|
1
|
| D
|
|
|
E
|
|
0
|
| E
|
|
|
E
|
|
1
|
3. zadatak
Postavka
Nedeterministički konačni automat iz postavke trećeg zadatka pod b.
- Da li su dati automati ekvivalentni? Obavezno prikazati postupak.
- Konvertovati zadati nedeterministički automat u deterministički. Obavezno prikazati postupak. Nije potrebna minimizacija.
Prvi automat iz postavke trećeg zadatka pod a
|
|
0
|
1
|
2
|
Prihvata
|
| → Ax
|
Ax
|
Ax
|
Bx
|
0
|
| Bx
|
Bx
|
Ax
|
Bx
|
1
|
Drugi automat iz postavke trećeg zadatka pod a
|
|
0
|
1
|
2
|
Prihvata
|
| → Az
|
Cz
|
Az
|
Bz
|
0
|
| Bz
|
Bz
|
Az
|
Az
|
1
|
| Cz
|
Cz
|
Az
|
Bz
|
0
|
Rešenje
Postupak provere ekvivalencije automata iz trećeg zadatka pod a
|
|
0
|
1
|
2
|
| Ax, Az
|
Ax, Cz
|
Ax, Az
|
Bx, Bz
|
| Ax, Cz
|
Ax, Cz
|
Ax, Az
|
Bx, Bz
|
| Bx, Bz
|
Bx, Bz
|
Ax, Az
|
Bx, Az
|
Zbog toga što stanja Bx i Az nisu kompatibilna, ova dva automata nisu ekvivalentna.
Postupak pretvaranja nedeterminističkog konačnog automata u deterministički
|
|
+
|
-
|
d
|
.
|
Prihvata
|
| → 1, 2, 4, 7, 8, 9
|
3, 8, 9
|
5, 8, 9
|
9, 10, 11, 12, 17, 18, 19
|
|
0
|
| 3, 8, 9
|
|
|
9, 10, 11, 12, 17, 18, 19
|
|
0
|
| 5, 8, 9
|
|
|
9, 10, 11, 12, 17, 18, 19
|
|
0
|
| 9, 10, 11, 12, 17, 18, 19
|
|
|
9, 10, 11, 12, 17, 18, 19
|
13, 14
|
1
|
| 13, 14
|
|
|
14, 15, 16, 19
|
|
0
|
| 14, 15, 16, 19
|
|
|
14, 15, 16, 19
|
|
1
|
Deterministički konačni automat
|
|
+
|
-
|
d
|
.
|
Prihvata
|
| → A
|
B
|
C
|
D
|
|
0
|
| B
|
|
|
D
|
|
0
|
| C
|
|
|
D
|
|
0
|
| D
|
|
|
D
|
E
|
1
|
| E
|
|
|
F
|
|
0
|
| F
|
|
|
F
|
|
1
|
4. zadatak
Postavka
?????
Rešenje
?????
