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

KockaAdmiralac: Često postavljeno pitanje

2022-10-31T13:28:02Z

Često postavljeno pitanje

← Старија измена		Верзија на датум 31. октобар 2022. у 15:28
Ред 92:		Ред 92:
	=== Rešenje ===		=== Rešenje ===
	[[Datoteka:PPR K1 2019 zadatak 2 stablo.svg\|thumb\|center\|Poziciono stablo u drugom zadatku.]]		[[Datoteka:PPR K1 2019 zadatak 2 stablo.svg\|thumb\|center\|Poziciono stablo u drugom zadatku.]]
			U sintaksnom stablu je čvor + označen kao poništiv jer je njegov podizraz poništiv, pa samim tim može rezultovati praznom sekvencom (prazna sekvenca ponovljena jedan ili više puta je i dalje prazna sekvenca).
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Tabela sledećih pozicija		\|+ Tabela sledećih pozicija

KockaAdmiralac: ADVANCE -> RETAIN

2022-10-29T15:16:39Z

ADVANCE -> RETAIN

← Старија измена		Верзија на датум 29. октобар 2022. у 17:16
Ред 278:		Ред 278:
	! A		! A
	\|		\|
	* ~~ADVANCE~~		* RETAIN
	* STATE(S3)		* STATE(S3)
	\| REJECT		\| REJECT

KockaAdmiralac: Alternativno rešenje

2022-10-28T19:08:48Z

Alternativno rešenje

@@ Ред 179: / Ред 179: @@
 * &lt;B> → c &lt;B> a
 {| class="wikitable"
 |+ Potisni automat za prepoznavanje sekvence zadate u zadatku
@@ Ред 230: / Ред 231: @@
 | REJECT
 | REJECT
 |}
 [[Категорија:Рокови]]
 [[Категорија:Програмски преводиоци 1]]

KockaAdmiralac: Moja rešenja K1 2019

2022-10-28T12:14:22Z

Moja rešenja K1 2019

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

{{tocright}}
'''Prvi kolokvijum 2019. godine''' održan je 28. oktobra i trajao je 90 minuta. Postavka roka dostupna je [http://ir4pp1.etf.rs/Rokovi/2019-2020/pp1-1920-k1k2.zip sa stranice predmeta] (arhiva).

== 1. zadatak ==
=== Postavka ===
Za dati konačni automat navesti:
<div class="abc-list">
# Klasni dijagram koji ilustruje projektni šablon (GoF design pattern) '''Stanje'''.
# Napisati programsku realizaciju datog automata na osnovu šablona iz tačke a).
</div>
{| class="wikitable"
|+ Dati konačni automat
!
! a
! b
! c
! Prihvata
|-
! → S1
| S2
| S1
| S2
| 0
|-
! S2
|
| S2
| S1
| 1
|}

=== Rešenje ===
[[Datoteka:PPR K1 2019 zadatak 1 dijagram.svg|thumb|UML dijagram tražen u stavci pod a prvog zadatka.]]
Rešenje dela pod a se može naći na slici, dok je pod b ispod:
<syntaxhighlight lang="java">
class FSM {
interface State {
boolean accepting();
State handleInput(char input);
}

private StateS1 S1 = new StateS1();
private StateS2 S2 = new StateS2();
private StateError ERROR = new StateError();

class StateS1 implements State {
public boolean accepting() {
return false;
}
public State handleInput(char input) {
switch (input) {
case 'a':
case 'c':
return S2;
case 'b': return S1;
default: return ERROR;
}
}
}

class StateS2 implements State {
public boolean accepting() {
return true;
}
public State handleInput(char input) {
switch (input) {
case 'b': return S2;
case 'c': return S1;
default: return ERROR;
}
}
}

class StateError implements State {
public boolean accepting() {
return false;
}
public State handleInput(char input) {
return ERROR;
}
}

// ...
}
</syntaxhighlight>

== 2. zadatak ==
=== Postavka ===
Metodom pozicija odrediti minimalni deterministički automat koji je opisan sledećim regularnim izrazrom:<sup>[sic]</sup>
b(a | (bc)<sup>*</sup>)<sup>+</sup>

=== Rešenje ===
[[Datoteka:PPR K1 2019 zadatak 2 stablo.svg|thumb|center|Poziciono stablo u drugom zadatku.]]
{| class="wikitable"
|+ Tabela sledećih pozicija
! 1
| 2, 3, 5
|-
! 2
| 2, 3, 5
|-
! 3
| 4
|-
! 4
| 2, 3, 5
|-
! 5
| -
|}
{| class="wikitable"
|+ Pretvaranje nedeterminističkog konačnog automata u deterministički
!
! a
! b
! c
! Prihvata
|-
! → 1
|
| 2, 3, 5
|
| 0
|-
! 2, 3, 5
| 2, 3, 5
| 4
|
| 1
|-
! 4
|
|
| 2, 3, 5
| 0
|}
{| class="wikitable"
|+ Deterministički konačni automat
!
! a
! b
! c
! Prihvata
|-
! → A
|
| B
|
| 0
|-
! B
| B
| C
|
| 1
|-
! C
|
|
| B
| 0
|}

== 3. zadatak ==
=== Postavka ===
Za sve sekvence oblika <math>(ab)^nc^ma^k, n \geq 0, m > k > 0</math> potrebno je:
<div class="abc-list">
# konstruisati gramatiku koja opisuje ovakve sekvence
# konstruisati potisni automat koji opisuje ovakve sekvence
</div>

=== Rešenje ===
Gramatika koja prepoznaje ovakve sekvence može da izgleda ovako:
* <S> → <A> <B>
* <A> → ab <A>
* <A> → ε
* <B> → cca
* <B> → c <B>
* <B> → c <B> a

{| class="wikitable"
|+ Potisni automat za prepoznavanje sekvence zadate u zadatku
!
! a
! b
! c
! ─┤
|-
! ∇
|
* PUSH(A)
* ADVANCE
| REJECT
|
* PUSH(D)
* PUSH(B)
* ADVANCE
| REJECT
|-
! A
| REJECT
|
* POP
* ADVANCE
| REJECT
| REJECT
|-
! B
|
* POP
* ADVANCE
| REJECT
|
* REPLACE(C)
* PUSH(B)
* ADVANCE
| REJECT
|-
! C
|
* POP
* ADVANCE
| REJECT
| REJECT
| ACCEPT
|-
! D
| REJECT
| REJECT
| REJECT
| REJECT
|}

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