Програмски преводиоци 1/К1 2017

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: $\left\{a^k b^m c^{k-1}\right\} k > 0, m \geq 0$

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	─┤
∇	PUSH(A) ADVANCE	REJECT	REJECT	REJECT
A	PUSH(B) ADVANCE	ADVANCE STATE(S2)	RETAIN STATE(S3)	ACCEPT
B	PUSH(B) ADVANCE	ADVANCE STATE(S2)	RETAIN STATE(S3)	REJECT

Drugo stanje potisne mašine za prepoznavanje sekvence

	a	b	c	─┤
A	REJECT	ADVANCE	REJECT	ACCEPT
B	REJECT	ADVANCE	RETAIN STATE(S3)	REJECT

Treće stanje potisne mašine za prepoznavanje sekvence

	a	b	c	─┤
A	REJECT	REJECT	REJECT	ACCEPT
B	REJECT	REJECT	POP ADVANCE	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.

1. Direktno na zadatom sintaksnom stablu jednog regularnog izraza naznačiti poništivost, i funkcije prva i poslednja pozicija.
2. Nacrtati tabelu sa vrednostima funkcije sledeća pozicija.
3. 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.

1. Da li su dati automati ekvivalentni? Obavezno prikazati postupak.
2. 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	Bz, Az

Zbog toga što stanja Bz 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

?????