Programski prevodioci 1/K1 2022

Овај рок није решен. Помозите SI Wiki тако што ћете га решити.

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

Postavka

Data su tri deterministička automata, M, N i P.

1. Napraviti deterministički konačni automat K koji prihvata sekvence tipa $s_1|(s_2s_3)$, gde su $s_1$ sve sekvence koje automat M odbija, a $s_2$ i $s_3$ sekvence koje automati N i P prihvataju, respektivno.
2. 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

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.

3. zadatak

Postavka

Konačni automat iz postavke zadatka.

Napisati fragment programskog koda koji implementira konačni automat sa slike:

1. eksplicitnom predstavom funkcije stanja
2. implicitnom predstavom funkcija stanja