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

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу

Prvi kolokvijum 2019. godine održan je 28. oktobra i trajao je 90 minuta. Postavka roka dostupna je sa stranice predmeta (arhiva).

1. zadatak

Postavka

Za dati konačni automat navesti:

  1. Klasni dijagram koji ilustruje projektni šablon (GoF design pattern) Stanje.
  2. Napisati programsku realizaciju datog automata na osnovu šablona iz tačke a).
Dati konačni automat
a b c Prihvata
→ S1 S2 S1 S2 0
S2 S2 S1 1

Rešenje

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:

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

    // ...
}

2. zadatak

Postavka

Metodom pozicija odrediti minimalni deterministički automat koji je opisan sledećim regularnim izrazrom:[sic]

b(a | (bc)*)+

Rešenje

Poziciono stablo u drugom zadatku.
Tabela sledećih pozicija
1 2, 3, 5
2 2, 3, 5
3 4
4 2, 3, 5
5 -
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
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 potrebno je:

  1. konstruisati gramatiku koja opisuje ovakve sekvence
  2. konstruisati potisni automat koji opisuje ovakve sekvence

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

Jedno rešenje stavke pod b, koje uključuje jedno stanje potisnog automata, izgleda ovako:

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

Alternativno rešenje sa više stanja izgleda ovako:

Prvo stanje potisnog automata
a b c ─┤
  • PUSH(A)
  • ADVANCE
REJECT
  • RETAIN
  • STATE(S2)
REJECT
A REJECT
  • POP
  • ADVANCE
REJECT REJECT
Drugo stanje potisnog automata
a b c ─┤
REJECT REJECT
  • PUSH(A)
  • ADVANCE
REJECT
A
  • RETAIN
  • STATE(S3)
REJECT
  • PUSH(A)
  • ADVANCE
REJECT
Treće stanje potisnog automata
a b c ─┤
REJECT REJECT REJECT REJECT
A
  • POP
  • ADVANCE
REJECT REJECT ACCEPT