Програмски преводиоци 1/К1 2017 - Историја измена

Etfsibg: /* Rešenje */

2025-09-25T13:51:37Z

Rešenje

← Старија измена		Верзија на датум 25. септембар 2025. у 15:51
Ред 32:		Ред 32:
	* ADVANCE		* ADVANCE
	* STATE(S2)		* STATE(S2)
	\|
	\| REJECT		\| REJECT
	\| ACCEPT		\| ACCEPT

Etfsibg: /* Rešenje */

2025-09-25T13:51:07Z

Rešenje

← Старија измена		Верзија на датум 25. септембар 2025. у 15:51
Ред 33:		Ред 33:
	* STATE(S2)		* STATE(S2)
	\|		\|
	* REJECT		\| REJECT
	\| ACCEPT		\| ACCEPT
	\|-		\|-

Etfsibg: /* Rešenje */

2025-09-25T13:48:51Z

Rešenje

← Старија измена		Верзија на датум 25. септембар 2025. у 15:48
Ред 33:		Ред 33:
	* STATE(S2)		* STATE(S2)
	\|		\|
	* ~~RETAIN~~		* REJECT
	* STATE(S3)
	\| ACCEPT		\| ACCEPT
	\|-		\|-
Ред 45:		Ред 44:
	* STATE(S2)		* STATE(S2)
	\|		\|
	* ~~RETAIN~~		* POP
			* ADVANCE
	* STATE(S3)		* STATE(S3)
	\| REJECT		\| REJECT
Ред 67:		Ред 67:
	\| ADVANCE		\| ADVANCE
	\|		\|
	* ~~RETAIN~~		* POP
			* ADVANCE
	* STATE(S3)		* STATE(S3)
	\| REJECT		\| REJECT

SrdjanKuzmanovic: /* Rešenje */

2022-10-29T20:33:30Z

Rešenje

← Старија измена		Верзија на датум 29. октобар 2022. у 22:33
Ред 345:		Ред 345:
	\| Bx, Bz		\| Bx, Bz
	\| Ax, Az		\| Ax, Az
	\| '''Bz, Az'''		\| '''Bx, Az'''
	\|}		\|}
	Zbog toga što stanja Bz i Az nisu kompatibilna, ova dva automata '''nisu ekvivalentna'''.		Zbog toga što stanja Bx i Az nisu kompatibilna, ova dva automata '''nisu ekvivalentna'''.

	{\| class="wikitable"		{\| class="wikitable"

Vasilevska: /* Rešenje */

2022-10-29T13:38:46Z

Rešenje

← Старија измена		Верзија на датум 29. октобар 2022. у 15:38
Ред 164:		Ред 164:
	\|-		\|-
	! 3		! 3
	\| 4, 5		\| 4, 5, 8
	\|-		\|-
	! 4		! 4
	\| 4, 5		\| 4, 5, 8
	\|-		\|-
	! 5		! 5
Ред 193:		Ред 193:
	\| 3		\| 3
	\| 3		\| 3
	\| 4, 5		\| 4, 5, 8
	\|		\|
	\| 0		\| 0
Ред 200:		Ред 200:
	\|		\|
	\|		\|
	\| 4, 5		\| 4, 5, 8
	\|		\|
	\| 0		\| 0
	\|-		\|-
	! 4, 5		! 4, 5, 8
	\|		\|
	\|		\|
	\| 4, 5		\| 4, 5, 8
	\| 6		\| 6
	\| 0		\| 1
	\|-		\|-
	! 6		! 6
Ред 253:		Ред 253:
	\| C		\| C
	\| D		\| D
	\| 0		\| 1
	\|-		\|-
	! D		! D

KockaAdmiralac: \leq -> \geq

2022-10-29T13:18:41Z

\leq -> \geq

← Старија измена		Верзија на датум 29. октобар 2022. у 15:18
Ред 4:		Ред 4:
	== 1. zadatak ==		== 1. zadatak ==
	=== Postavka ===		=== Postavka ===
	Projektovati potisni automat koji prepoznaje sledeći skup sekvenci: <math>\left\{a^k b^m c^{k-1}\right\} k > 0, m \~~leq~~ 0</math>		Projektovati potisni automat koji prepoznaje sledeći skup sekvenci: <math>\left\{a^k b^m c^{k-1}\right\} k > 0, m \geq 0</math>

	Iz zadatog skupa izabrati jednu sekvencu dužine veće od tri i prikazati proces njenog prepoznavanja.		Iz zadatog skupa izabrati jednu sekvencu dužine veće od tri i prikazati proces njenog prepoznavanja.

KockaAdmiralac: Dupli red u tabeli sledećih pozicija

2022-10-29T08:12:23Z

Dupli red u tabeli sledećih pozicija

← Старија измена		Верзија на датум 29. октобар 2022. у 10:12
Ред 164:		Ред 164:
	\|-		\|-
	! 3		! 3
	~~\| 4, 5~~
	\|-
	~~! 4~~
	\| 4, 5		\| 4, 5
	\|-		\|-

KockaAdmiralac: Moja rešenja K1 2017

2022-10-28T23:04:45Z

Moja rešenja K1 2017

Нова страница

{{tocright}}
'''Prvi kolokvijum 2017. godine''' održan je 28. oktobra i trajao je dva sata. Radna verzija postavke roka je [http://ir4pp1.etf.rs/Rokovi/2017-2018/si4pp1-1718-k1k2.zip dostupna sa stranice predmeta] (arhiva).

== 1. zadatak ==
=== Postavka ===
Projektovati potisni automat koji prepoznaje sledeći skup sekvenci: <math>\left\{a^k b^m c^{k-1}\right\} k > 0, m \leq 0</math>

Iz zadatog skupa izabrati jednu sekvencu dužine veće od tri i prikazati proces njenog prepoznavanja.

=== Rešenje ===
{| class="wikitable"
|+ 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
|}
{| class="wikitable"
|+ Drugo stanje potisne mašine za prepoznavanje sekvence
!
! a
! b
! c
! ─┤
|-
! A
| REJECT
| ADVANCE
| REJECT
| ACCEPT
|-
! B
| REJECT
| ADVANCE
|
* RETAIN
* STATE(S3)
| REJECT
|}
{| class="wikitable"
|+ 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'''.
{| class="wikitable"
! 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 ===
[[Datoteka:PPR K1 2017 zadatak 2 postavka.svg|thumb|Stablo iz postavke drugog zadatka.]]
<div class="abc-list">
# Direktno na zadatom sintaksnom stablu jednog regularnog izraza naznačiti poništivost, i funkcije prva i poslednja pozicija.
# Nacrtati tabelu sa vrednostima funkcije sledeća pozicija.
# Na osnovu zadatog stabla i rezultata pod a) odrediti konačni automat. Obavezno navesti postupak. Nije potrebna minimizacija.
</div>

=== Rešenje ===
[[Datoteka:PPR K1 2017 zadatak 2 rešenje.svg|thumb|Stablo iz rešenja drugog zadatka.]]
{| class="wikitable"
|+ Tabela sledećih pozicija
! Pozicija
! Sledeća pozicija
|-
! 1
| 3
|-
! 2
| 3
|-
! 3
| 4, 5
|-
! 4
| 4, 5
|-
! 4
| 4, 5
|-
! 5
| 6
|-
! 6
| 7, 8
|-
! 7
| 7, 8
|-
! 8
| -
|}
{| class="wikitable"
|+ Postupak pretvaranja sintaksnog stabla u deterministički konačni automat
!
! +
! -
! d
! .
! Prihvata
|-
! 1, 2, 3
| 3
| 3
| 4, 5
|
| 0
|-
! 3
|
|
| 4, 5
|
| 0
|-
! 4, 5
|
|
| 4, 5
| 6
| 0
|-
! 6
|
|
| 7, 8
|
| 0
|-
! 7, 8
|
|
| 7, 8
|
| 1
|}
{| class="wikitable"
|+ Deterministički konačni automat
!
! +
! -
! d
! .
! Prihvata
|-
! A
| B
| B
| C
|
| 0
|-
! B
|
|
| C
|
| 0
|-
! C
|
|
| C
| D
| 0
|-
! D
|
|
| E
|
| 0
|-
! E
|
|
| E
|
| 1
|}

== 3. zadatak ==
=== Postavka ===
[[Datoteka:PPR K1 2017 zadatak 3 postavka.svg|thumb|Nedeterministički konačni automat iz postavke trećeg zadatka pod b.]]
<div class="abc-list">
# Da li su dati automati ekvivalentni? Obavezno prikazati postupak.
# Konvertovati zadati nedeterministički automat u deterministički. Obavezno prikazati postupak. Nije potrebna minimizacija.
</div>
{| class="wikitable"
|+ Prvi automat iz postavke trećeg zadatka pod a
!
! 0
! 1
! 2
! Prihvata
|-
! → Ax
| Ax
| Ax
| Bx
| 0
|-
! Bx
| Bx
| Ax
| Bx
| 1
|}
{| class="wikitable"
|+ 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 ===
{| class="wikitable"
|+ 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'''.

{| class="wikitable"
|+ 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
|}
{| class="wikitable"
|+ 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 ===
?????

[[Категорија:Рокови]]
[[Категорија:Програмски преводиоци 1]]