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

Први колоквијум 2022. године одржан је 31. октобра и трајао је 90 минута. Поставка рока још увек није званично доступна са странице предмета.

1. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

Дата су три детерминистичка аутомата, M, Н и П.

1. Направити детерминистички коначни аутомат К који прихвата секвенце типа $s_1|(s_2s_3)$, где су $s_1$ све секвенце које аутомат M одбија, а $s_2$ и $s_3$ секвенце које аутомати Н и П прихватају, респективно.
2. Од аутомата из тачке под а направити десно-линеарну граматику, а затим из ње избацити све недостижне или мртве нетерминале.

Аутомат M

	0	1	Прихвата
А	А	Б	0
Б	Б	C	1
C	А	C	1

Аутомат Н

	1	2	Прихвата
D	Е		1
Е	D	Е	0
Ф	Ф	Е	1

Аутомат П

	0	а	Прихвата
1	1	2	1
2		1	0

Решење

Недетерминстички аутомат који прихвата с2с3

	1	2	0	а	Прихвата
D	Е				0
Е	D,1	Е			0
Ф	Ф,1	Е			0
1			1	2	1
2				1	0

Детерминстички аутомат који прихвата с2с3

	1	2	0	а	Прихвата
D,1	Е		1	2	1
Е	D,1	Е			0
1			1	2	1
2				2	0

Недетерминистички аутомат који прихвата тражену секвенцу

	0	1	2	а	Прихвата
А	А	Б			1
Б	Б	C			0
C	А	C			0
D,1	1	Е		2	1
Е		D,1	Е		0
1	1			2	1
2				1	0

Детерминистички аутомат који прихвата тражену секвенцу

	0	1	2	а	1
{А,D,1}, С0	А,1	Б,Е		2	1
{А,1}, С1	А,1	Б		2	1
{Б,Е}, С2	Б	C,Д,1	Е		0
{2}, С3				1	0
{Б}, С4	Б	C			0
{C,Д,1}, С5	А,1	C,Е		2	1
{Е}, С6		D,1	Е		0
{1}, С7	1			2	1
{C}, С8	А	C			0
{C,Е}, С9	А	C,Д,1	Е		0
{D,1}, С10	1	Е		2	1
{А}, С11	А	Б			1

2. задатак

Поставка

Аритметички израз се састоји из нула или више бројева, где је број низ цифара, са аритметичким операцијама сабирања или одузимања између њих. Уколико су терминали у датој азбуци једна цифра ("ЦИФРА"), знак за сабирање ("+") и знак за одузимање ("-") написати регуларни израз који описује дате аритметичке изразе, а затим га претворити у детерминистички коначни аутомат коришћењем метода позиција.

Решење

Позиционо стабло у другом задатку.

Табела следећих позиција

Позиција	Следећа позиција
1	1,2,3,5
2	4
3	4
4	1,2,3,4,5
5	/

Детерминистички коначни аутомат за тражени регуларни израз

	ЦИФРА	+	-	Прихвата
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. задатак

Поставка

Коначни аутомат из поставке задатка.

Написати фрагмент програмског кода који имплементира коначни аутомат са слике:

1. експлицитном представом функције стања
2. имплицитном представом функција стања

Решење

а)

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

б)

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