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

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.

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

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 $(ab)^nc^ma^k, n \geq 0, m > k > 0$ 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