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
|
|
|
|
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
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
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
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
