SI Wiki - Кориснички доприноси [sr]

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

2025-12-01T13:53:54Z

Kiu: Поништена измена бр. 8164 корисника Kiu (разговор)

{{tocright}}
'''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 ==
{{delimično rešeno}}
=== Postavka ===
Data su tri deterministička automata, M, N i P.
<div class="abc-list">
# Napraviti deterministički konačni automat K koji prihvata sekvence tipa <math>s_1|(s_2s_3)</math>, gde su <math>s_1</math> sve sekvence koje automat M odbija, a <math>s_2</math> i <math>s_3</math> sekvence koje automati N i P prihvataju, respektivno.
# Od automata iz tačke pod a napraviti desno-linearnu gramatiku, a zatim iz nje izbaciti sve nedostižne ili mrtve neterminale.
</div>
{| class="wikitable"
|+ Automat M
!
! 0
! 1
! Prihvata
|-
! A
| A
| B
| 0
|-
! B
| B
| C
| 1
|-
! C
| A
| C
| 1
|}
{| class="wikitable"
|+ Automat N
!
! 1
! 2
! Prihvata
|-
! D
| E
|
| 1
|-
! E
| D
| E
| 0
|-
! F
| F
| E
| 1
|}
{| class="wikitable"
|+ Automat P
!
! 0
! a
! Prihvata
|-
! 1
| 1
| 2
| 1
|-
! 2
|
| 1
| 0
|}

=== Rešenje ===
{| class="wikitable"
|+ Nedeterminstički automat koji prihvata s2s3
!
! 1
! 2
! 0
! a
! Prihvata
|-
! D
| E
|
|
|
| 0
|-
! E
| D,1
| E
|
|
| 0
|-
! F
| F,1
| E
|
|
| 0
|-
! 1
|
|
| 1
| 2
| 1
|-
! 2
|
|
|
| 1
| 0
|}

{| class="wikitable"
|+ Determinstički automat koji prihvata s2s3
!
! 1
! 2
! 0
! a
! Prihvata
|-
! D,1
| E
|
| 1
| 2
| 1
|-
! E
| D,1
| E
|
|
| 0
|-
! 1
|
|
| 1
| 2
| 1
|-
! 2
|
|
|
| 2
| 0
|}

{| class="wikitable"
|+ Nedeterministički automat koji prihvata traženu sekvencu
|-
!
! 0
! 1
! 2
! a
! Prihvata
|-
| A
| A
| B
|
|
| 1
|-
| B
| B
| C
|
|
| 0
|-
| C
| A
| C
|
|
| 0
|-
| D,1
| 1
| E
|
| 2
| 1
|-
| E
|
| D,1
| E
|
| 0
|-
| 1
| 1
|
|
| 2
| 1
|-
| 2
|
|
|
| 1
| 0
|}

{| class="wikitable"
|+ Deterministički automat koji prihvata traženu sekvencu
|-
!
! 0
! 1
! 2
! a
! 1
|-
| {A,D,1}, S0
| A,1
| B,E
|
| 2
| 1
|-
| {A,1}, S1
| A,1
| B
|
| 2
| 1
|-
| {B,E}, S2
| B
| C,D,1
| E
|
| 0
|-
| {2}, S3
|
|
|
| 1
| 0
|-
| {B}, S4
| B
| C
|
|
| 0
|-
| {C,D,1}, S5
| A,1
| C,E
|
| 2
| 1
|-
| {E}, S6
|
| D,1
| E
|
| 0
|-
| {1}, S7
| 1
|
|
| 2
| 1
|-
| {C}, S8
| A
| C
|
|
| 0
|-
| {C,E}, S9
| A
| C,D,1
| E
|
| 0
|-
| {D,1}, S10
| 1
| E
|
| 2
| 1
|-
| {A}, S11
| A
| B
|
|
| 1
|}

== 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.

=== Rešenje ===
[[Datoteka:PPR K1 2022 zadatak 2 stablo.svg|thumb|center|Poziciono stablo u drugom zadatku.]]

{| class="wikitable"
|+ Tabela sledećih pozicija
|-
! Pozicija
! Sledeća pozicija
|-
| 1
| 1,2,3,5
|-
| 2
| 4
|-
| 3
| 4
|-
| 4
| 1,2,3,4,5
|-
| 5
| /
|}

{| class="wikitable"
|+ Deterministički konačni automat za traženi regularni izraz
|-
!
! CIFRA
! +
! -
! Prihvata
|-
| 1,5
| 1,2,3,5
|
|
| 1
|-
| 1,2,3,5
| 1,2,3,5
| 4
| 4
| 1
|-
| 4
| 1,2,3,4,5
|
|
| 0
|-
| 1,2,3,4,5
| 1,2,3,4,5
| 4
| 4
| 1
|}

== 3. zadatak ==
=== Postavka ===
[[Datoteka:PPR K1 2022 zadatak 3 automat.svg|thumb|Konačni automat iz postavke zadatka.]]
Napisati fragment programskog koda koji implementira konačni automat sa slike:
<div class="abc-list">
# eksplicitnom predstavom funkcije stanja
# implicitnom predstavom funkcija stanja
</div>

=== Rešenje ===

a) <syntaxhighlight lang="java">
class FSM
{

enum State {
S0( false ),
S1( true ),
ERROR( false );

final boolean accepting;

State( boolean accepting ) {
this.accepting = accepting;
}
}

static State state;

static void handleInput(int ch)
{
switch( state )
{
case S0:
if ( ch==0 )
state = State.S1;
else
state = State.ERROR;
break;

case S1:
if ( ch==0 )
state = State.S1;
else if ( ch==1 )
state = State.S0;

break;

case ERROR:
state = State.ERROR;
break;
}
}

public static void main(String[] args) throws java.io.IOException
{
int ch;
state = State.S0;
while ((ch = System.in.read ()) != '\n')
handleInput(ch);

if (state.accepting)
System.out.println("Prihvata");
else
System.out.println("Odbija");
}
}
</syntaxhighlight>
b) <syntaxhighlight lang="java">

class FSM_TT
{

enum State {
S0( false ),
S1( true ),
ERROR( false );

final boolean accepting;

State( boolean accepting ) {
this.accepting = accepting;
}
}

static State state;
static State transition[3][2] =
{
{ State.S1, State.ERROR},
{ State.S1, State.S0},
{ State.ERROR, State.ERROR}
};
static void handleInput(int ch)
{
int index;
switch( ch )
{
case 0:
index=0;
break;
case 1:
index=1;
break;
default:
state=State.ERROR;
return;
}
state = transition[state.ordinal()][index];
}

public static void main(String[] args) throws java.io.IOException
{
int ch;
state = State.S0;
while ((ch = System.in.read ()) != '\n')
handleInput(ch);

if (state.accepting)
System.out.println("Prihvata");
else
System.out.println("Odbija");
}
}
</syntaxhighlight>

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

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

2025-12-01T13:50:03Z

Kiu: /* Rešenje */

{{tocright}}
'''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 ==
{{delimično rešeno}}
=== Postavka ===
Data su tri deterministička automata, M, N i P.
<div class="abc-list">
# Napraviti deterministički konačni automat K koji prihvata sekvence tipa <math>s_1|(s_2s_3)</math>, gde su <math>s_1</math> sve sekvence koje automat M odbija, a <math>s_2</math> i <math>s_3</math> sekvence koje automati N i P prihvataju, respektivno.
# Od automata iz tačke pod a napraviti desno-linearnu gramatiku, a zatim iz nje izbaciti sve nedostižne ili mrtve neterminale.
</div>
{| class="wikitable"
|+ Automat M
!
! 0
! 1
! Prihvata
|-
! A
| A
| B
| 0
|-
! B
| B
| C
| 1
|-
! C
| A
| C
| 1
|}
{| class="wikitable"
|+ Automat N
!
! 1
! 2
! Prihvata
|-
! D
| E
|
| 1
|-
! E
| D
| E
| 0
|-
! F
| F
| E
| 1
|}
{| class="wikitable"
|+ Automat P
!
! 0
! a
! Prihvata
|-
! 1
| 1
| 2
| 1
|-
! 2
|
| 1
| 0
|}

=== Rešenje ===
{| class="wikitable"
|+ Nedeterminstički automat koji prihvata s2s3
!
! 1
! 2
! 0
! a
! Prihvata
|-
! D
| E
|
|
|
| 0
|-
! E
| D,1
| E
|
|
| 0
|-
! F
| F,1
| E
|
|
| 0
|-
! 1
|
|
| 1
| 2
| 1
|-
! 2
|
|
|
| 1
| 0
|}

{| class="wikitable"
|+ Determinstički automat koji prihvata s2s3
!
! 1
! 2
! 0
! a
! Prihvata
|-
! D,1
| E
|
| 1
| 2
| 1
|-
! E
| D,1
| E
|
|
| 0
|-
! 1
|
|
| 1
| 2
| 1
|-
! 2
|
|
|
| 2
| 0
|}

{| class="wikitable"
|+ Nedeterministički automat koji prihvata traženu sekvencu
|-
!
! 0
! 1
! 2
! a
! Prihvata
|-
| A
| A
| B
|
|
| 1
|-
| B
| B
| C
|
|
| 0
|-
| C
| A
| C
|
|
| 0
|-
| D,1
| 1
| E
|
| 2
| 1
|-
| E
|
| D,1
| E
|
| 0
|-
| 1
| 1
|
|
| 2
| 1
|-
| 2
|
|
|
| 1
| 0
|}

{| class="wikitable"
|+ Deterministički automat koji prihvata traženu sekvencu
|-
!
! 0
! 1
! 2
! a
! 1
|-
| {A,D,1}, S0
| A,1
| B,E
|
| 2
| 1
|-
| {A,1}, S1
| A,1
| B
|
| 2
| 1
|-
| {B,E}, S2
| B
| C,D,1
| E
|
| 0
|-
| {2}, S3
|
|
|
| 1
| 0
|-
| {B}, S4
| B
| C
|
|
| 0
|-
| {C,D,1}, S5
| A,1
| C,E
|
| 2
| 1
|-
| {E}, S6
|
| D,1
| E
|
| 0
|-
| {1}, S7
| 1
|
|
| 2
| 1
|-
| {C}, S8
| A
| C
|
|
| 0
|-
| {C,E}, S9
| A
| C,D,1
| E
|
| 0
|-
| {D,1}, S10
| 1
| E
|
| 2
| 1
|-
| {A}, S11
| A
| B
|
|
| 1
|}

== 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.

=== Rešenje ===
[[Datoteka:PPR K1 2022 zadatak 2 stablo.svg|thumb|center|Poziciono stablo u drugom zadatku.]]
Zadato rešenje nije tačno jer ne prihvata jedan Broj (bez aritmetičkih operacija).
{| class="wikitable"
|+ Tabela sledećih pozicija
|-
! Pozicija
! Sledeća pozicija
|-
| 1
| 1,2,3,5
|-
| 2
| 4
|-
| 3
| 4
|-
| 4
| 1,2,3,4,5
|-
| 5
| /
|}

{| class="wikitable"
|+ Deterministički konačni automat za traženi regularni izraz
|-
!
! CIFRA
! +
! -
! Prihvata
|-
| 1,5
| 1,2,3,5
|
|
| 1
|-
| 1,2,3,5
| 1,2,3,5
| 4
| 4
| 1
|-
| 4
| 1,2,3,4,5
|
|
| 0
|-
| 1,2,3,4,5
| 1,2,3,4,5
| 4
| 4
| 1
|}

== 3. zadatak ==
=== Postavka ===
[[Datoteka:PPR K1 2022 zadatak 3 automat.svg|thumb|Konačni automat iz postavke zadatka.]]
Napisati fragment programskog koda koji implementira konačni automat sa slike:
<div class="abc-list">
# eksplicitnom predstavom funkcije stanja
# implicitnom predstavom funkcija stanja
</div>

=== Rešenje ===

a) <syntaxhighlight lang="java">
class FSM
{

enum State {
S0( false ),
S1( true ),
ERROR( false );

final boolean accepting;

State( boolean accepting ) {
this.accepting = accepting;
}
}

static State state;

static void handleInput(int ch)
{
switch( state )
{
case S0:
if ( ch==0 )
state = State.S1;
else
state = State.ERROR;
break;

case S1:
if ( ch==0 )
state = State.S1;
else if ( ch==1 )
state = State.S0;

break;

case ERROR:
state = State.ERROR;
break;
}
}

public static void main(String[] args) throws java.io.IOException
{
int ch;
state = State.S0;
while ((ch = System.in.read ()) != '\n')
handleInput(ch);

if (state.accepting)
System.out.println("Prihvata");
else
System.out.println("Odbija");
}
}
</syntaxhighlight>
b) <syntaxhighlight lang="java">

class FSM_TT
{

enum State {
S0( false ),
S1( true ),
ERROR( false );

final boolean accepting;

State( boolean accepting ) {
this.accepting = accepting;
}
}

static State state;
static State transition[3][2] =
{
{ State.S1, State.ERROR},
{ State.S1, State.S0},
{ State.ERROR, State.ERROR}
};
static void handleInput(int ch)
{
int index;
switch( ch )
{
case 0:
index=0;
break;
case 1:
index=1;
break;
default:
state=State.ERROR;
return;
}
state = transition[state.ordinal()][index];
}

public static void main(String[] args) throws java.io.IOException
{
int ch;
state = State.S0;
while ((ch = System.in.read ()) != '\n')
handleInput(ch);

if (state.accepting)
System.out.println("Prihvata");
else
System.out.println("Odbija");
}
}
</syntaxhighlight>

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