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

Prvi kolokvijum 2015. godine održan je 25. oktobra i trajao je 90 minuta. Postavka je dostupna sa stranice predmeta (arhiva).

1. zadatak

Postavka

1. Opisati korake generalnog postupka kojim se za dva proizvoljna deterministička automata sa istim ulaznim azbukama konstruiše automat koji prihvata sve sekvence koje prihvata i prvi automat i dodatno sve sekvence koje NE prihvata drugi automat (i nijednu više).
2. Konstruisati minimalni deterministički konačni automat prema postupku opisanom pod a) za sledeća dva automata. Prikazati svaki korak postupka.

Prvi automat

	x	y	Prihvata
→ 0	1	0	1
1	2	1	0
2	2	0	0

Drugi automat

	x	y	Prihvata
→ A	B	A	0
B	A	B	1

Rešenje

Generalni postupak konstruisanja takvog automata jeste da se dva deterministička automata samo spoje, nova početna stanja postaju početna stanja oba automata a na drugom automatu se obrne šta su stanja prihvatanja a šta neprihvatanja kako bi se prihvatale sekvence koje drugi automat ne prihvata. Kako se ovim postupkom dobija nedeterministički konačni automat, potrebno je pretvoriti nedeterministički u deterministički konačni automat. Početno stanje se sastoji od početnih stanja oba automata, a stanja prihvatanja su sva stanja koje sadrže neko od stanja prihvatanja prethodnih automata.

Ispod je prikazan postupak konverzije gorenavedenih automata.

Spojeni automati u jedan nedeterministički konačni automat

	x	y	Prihvata
→ 0	1	0	1
1	2	1	0
2	2	0	0
→ A	B	A	0
B	A	B	1

Konverzija nedeterminističkog u deterministički konačni automat

	x	y	Prihvata
0, A	1, B	0, A	1
1, B	2, A	1, B	0
2, A	2, B	0, A	1
2, B	2, A	0, B	0
0, B	1, A	0, B	1
1, A	2, B	1, A	1

Konačni deterministički automat

	x	y	Prihvata
A	B	A	1
B	C	B	0
C	D	A	1
D	C	E	0
E	F	E	1
F	D	F	1

2. zadatak

Postavka

Konstruisati regularnu gramatiku koja generiše tačno iste sekvence kao regularni izraz a* | b*.

Rešenje

• <S> → <A>
• <S> → <B>
• <A> → a <A>
• <A> → ε
• <B> → b <B>
• <B> → ε

3. zadatak

Postavka

Napisati beskontekstnu gramatiku koja opisuje sve sekvence koje pripadaju sledećem jeziku: $L(G) = \left\{ a^n c^m \left(b c^k\right)^n | m, k \geq 0, n > 0 \right\}$, gde $\Sigma = \{a, b, c\}$ predstavlja skup simbola alfabeta.

Rešenje

• <S> → a <S> b <A>
• <S> → a <A> b <A>
• <A> → c <A>
• <A> → ε

Ovo rešenje nije ispravno, jer ne garantuje da će pri svakom ponavljanju $b c^k$ biti podjednak broj slova $c$. Ipak, nije poznato da li je uopšte moguće napisati bezkontekstnu gramatiku za jezik iz postavke zadataka, pa je ovo rešenje možda prihvatljivo.

4. zadatak

Postavka

1. Na osnovu regularnog izraza $(a* | b*) c+$, konstruisati minimalni deterministički automat metodom pozicija.
2. Nacrtati graf NKA dobijenog transformacijom regularnog izraza $(a* | b*)+$ primenom Tompsonovog algoritma. Nije potrebno konstruisati minDKA.

Rešenje

• 

  Sintaksno stablo u stavci pod a.

• 

  Graf nedeterminističkog konačnog automata u stavci pod b.

Tabela sledećih pozicija u stavci pod a

Pozicija	Sledeća pozicija
1	1, 3
2	2, 3
3	3, 4
4	-

Konverzija nedeterminističkog konačnog automata u deterministički u stavci pod a

	a	b	c	Prihvata
1, 2, 3	1, 3	2, 3	3, 4	0
1, 3	1, 3		3, 4	0
2, 3		2, 3	3, 4	0
3, 4			3, 4	1