Prvi kolokvijum 2022. godine održan je 31. oktobra i trajao je 90 minuta. Postavka roka još uvek nije zvanično dostupna sa stranice predmeta.
1. zadatak
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Postavka
Data su tri deterministička automata, M, N i P.
- Napraviti deterministički konačni automat K koji prihvata sekvence tipa
, gde su 
sve sekvence koje automat M odbija, a 
i 
sekvence koje automati N i P prihvataju, respektivno.
- Od automata iz tačke pod a napraviti desno-linearnu gramatiku, a zatim iz nje izbaciti sve nedostižne ili mrtve neterminale.
Automat M
|
|
0
|
1
|
Prihvata
|
| A
|
A
|
B
|
0
|
| B
|
B
|
C
|
1
|
| C
|
A
|
C
|
1
|
Automat N
|
|
1
|
2
|
Prihvata
|
| D
|
E
|
|
1
|
| E
|
D
|
E
|
0
|
| F
|
F
|
E
|
1
|
Automat P
|
|
0
|
a
|
Prihvata
|
| 1
|
1
|
2
|
1
|
| 2
|
|
1
|
0
|
Rešenje
Nedeterminstički automat koji prihvata s2s3
|
|
1
|
2
|
0
|
a
|
Prihvata
|
| D
|
E
|
|
|
|
0
|
| E
|
D,1
|
E
|
|
|
0
|
| F
|
F,1
|
E
|
|
|
0
|
| 1
|
|
|
1
|
2
|
1
|
| 2
|
|
|
|
1
|
0
|
Determinstički automat koji prihvata s2s3
|
|
1
|
2
|
0
|
a
|
Prihvata
|
| D,1
|
E
|
|
1
|
2
|
1
|
| E
|
D,1
|
E
|
|
|
0
|
| 1
|
|
|
1
|
2
|
1
|
| 2
|
|
|
|
2
|
0
|
Nedeterministički automat koji prihvata traženu sekvencu
|
|
0
|
1
|
2
|
a
|
Prihvata
|
| A
|
A
|
B
|
|
|
1
|
| B
|
B
|
C
|
|
|
0
|
| C
|
A
|
C
|
|
|
0
|
| D,1
|
1
|
E
|
|
2
|
1
|
| E
|
|
D,1
|
E
|
|
0
|
| 1
|
1
|
|
|
2
|
1
|
| 2
|
|
|
|
1
|
0
|
Deterministički automat koji prihvata traženu sekvencu
|
|
0
|
1
|
2
|
a
|
1
|
| {A,D,1}, S0
|
A,1
|
B,E
|
|
2
|
1
|
| {A,1}, S1
|
A,1
|
B
|
|
2
|
1
|
| {B,E}, S2
|
B
|
C,D,1
|
E
|
|
0
|
| {2}, S3
|
|
|
|
1
|
0
|
| {B}, S4
|
B
|
C
|
|
|
0
|
| {C,D,1}, S5
|
A,1
|
C,E
|
|
2
|
1
|
| {E}, S6
|
|
D,1
|
E
|
|
0
|
| {1}, S7
|
1
|
|
|
2
|
1
|
| {C}, S8
|
A
|
C
|
|
|
0
|
| {C,E}, S9
|
A
|
C,D,1
|
E
|
|
0
|
| {D,1}, S10
|
1
|
E
|
|
2
|
1
|
| {A}, S11
|
A
|
B
|
|
|
1
|
2. zadatak
Postavka
Aritmetički izraz se sastoji iz nula ili više brojeva, gde je broj niz cifara, sa aritmetičkim operacijama sabiranja ili oduzimanja između njih. Ukoliko su terminali u datoj azbuci jedna cifra ("CIFRA"), znak za sabiranje ("+") i znak za oduzimanje ("-") napisati regularni izraz koji opisuje date aritmetičke izraze, a zatim ga pretvoriti u deterministički konačni automat korišćenjem metoda pozicija.
Rešenje
Poziciono stablo u drugom zadatku.
Tabela sledećih pozicija
| Pozicija
|
Sledeća pozicija
|
| 1
|
1,2,3,5
|
| 2
|
4
|
| 3
|
4
|
| 4
|
1,2,3,4,5
|
| 5
|
/
|
Deterministički konačni automat za traženi regularni izraz
|
|
CIFRA
|
+
|
-
|
Prihvata
|
| 1,5
|
1,2,3,5
|
|
|
1
|
| 1,2,3,5
|
1,2,3,5
|
4
|
4
|
1
|
| 4
|
1,2,3,4,5
|
|
|
0
|
| 1,2,3,4,5
|
1,2,3,4,5
|
4
|
4
|
1
|
3. zadatak
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Postavka
Konačni automat iz postavke zadatka.
Napisati fragment programskog koda koji implementira konačni automat sa slike:
- eksplicitnom predstavom funkcije stanja
- implicitnom predstavom funkcija stanja
Rešenje
