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

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

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Postavka

Data su tri deterministička automata, M, N i P.

1. Napraviti deterministički konačni automat K koji prihvata sekvence tipa $s_1|(s_2s_3)$, gde su $s_1$ sve sekvence koje automat M odbija, a $s_2$ i $s_3$ sekvence koje automati N i P prihvataju, respektivno.
2. Od automata iz tačke pod a napraviti desno-linearnu gramatiku, a zatim iz nje izbaciti sve nedostižne ili mrtve neterminale.

Automat M

	0	1	Prihvata
A	A	B	0
B	B	C	1
C	A	C	1

Automat N

	1	2	Prihvata
D	E		1
E	D	E	0
F	F	E	1

Automat P

	0	a	Prihvata
1	1	2	1
2		1	0

Rešenje

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

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

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

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

Poziciono stablo u drugom zadatku.

Tabela sledećih pozicija

Pozicija	Sledeća pozicija
1	1,2,3,5
2	4
3	4
4	1,2,3,4,5
5	/

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

Konačni automat iz postavke zadatka.

Napisati fragment programskog koda koji implementira konačni automat sa slike:

1. eksplicitnom predstavom funkcije stanja
2. implicitnom predstavom funkcija stanja

Rešenje

a)

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");
  }
}

b)

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");
  }
}