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

Први колоквијум 2019. године одржан је 28. октобра и трајао је 90 минута. Поставка рока доступна је са странице предмета (архива).

1. задатак

Поставка

За дати коначни аутомат навести:

1. Класни дијаграм који илуструје пројектни шаблон (ГоФ десигн паттерн) Стање.
2. Написати програмску реализацију датог аутомата на основу шаблона из тачке а).

Дати коначни аутомат

	а	б	ц	Прихвата
→ С1	С2	С1	С2	0
С2		С2	С1	1

Решење

УМЛ дијаграм тражен у ставци под а првог задатка.

Решење дела под а се може наћи на слици, док је под б испод:

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. задатак

Поставка

Методом позиција одредити минимални детерминистички аутомат који је описан следећим регуларним изразром:^[сиц]

b(a | (bc)*)+

Решење

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

У синтаксном стаблу је чвор + означен као поништив јер је његов подизраз поништив, па самим тим може резултовати празном секвенцом (празна секвенца поновљена један или више пута је и даље празна секвенца).

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

1	2, 3, 5
2	2, 3, 5
3	4
4	2, 3, 5
5	-

Претварање недетерминистичког коначног аутомата у детерминистички

	а	б	ц	Прихвата
→ 1		2, 3, 5		0
2, 3, 5	2, 3, 5	4		1
4			2, 3, 5	0

Детерминистички коначни аутомат

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

3. задатак

Поставка

За све секвенце облика $(ab)^nc^ma^k, n \geq 0, m > k > 0$ потребно је:

1. конструисати граматику која описује овакве секвенце
2. конструисати потисни аутомат који описује овакве секвенце

Решење

Граматика која препознаје овакве секвенце може да изгледа овако:

• <С> → <А> <Б>
• <А> → аб <А>
• <А> → ε
• <Б> → цца
• <Б> → ц <Б>
• <Б> → ц <Б> а

Једно решење ставке под б, које укључује једно стање потисног аутомата, изгледа овако:

Потисни аутомат за препознавање секвенце задате у задатку

	а	б	ц	─┤
∇	ПУСХ(А) АДВАНЦЕ	РЕЈЕЦТ	ПУСХ(D) ПУСХ(Б) АДВАНЦЕ	РЕЈЕЦТ
А	РЕЈЕЦТ	ПОП АДВАНЦЕ	РЕЈЕЦТ	РЕЈЕЦТ
Б	ПОП АДВАНЦЕ	РЕЈЕЦТ	РЕПЛАЦЕ(C) ПУСХ(Б) АДВАНЦЕ	РЕЈЕЦТ
C	ПОП АДВАНЦЕ	РЕЈЕЦТ	РЕЈЕЦТ	АЦЦЕПТ
D	РЕЈЕЦТ	РЕЈЕЦТ	РЕЈЕЦТ	РЕЈЕЦТ

Алтернативно решење са више стања изгледа овако:

Прво стање потисног аутомата

	а	б	ц	─┤
∇	ПУСХ(А) АДВАНЦЕ	РЕЈЕЦТ	РЕТАИН СТАТЕ(С2)	РЕЈЕЦТ
А	РЕЈЕЦТ	ПОП АДВАНЦЕ	РЕЈЕЦТ	РЕЈЕЦТ

Друго стање потисног аутомата

	а	б	ц	─┤
∇	РЕЈЕЦТ	РЕЈЕЦТ	ПУСХ(А) АДВАНЦЕ	РЕЈЕЦТ
А	РЕТАИН СТАТЕ(С3)	РЕЈЕЦТ	ПУСХ(А) АДВАНЦЕ	РЕЈЕЦТ

Треће стање потисног аутомата

	а	б	ц	─┤
∇	РЕЈЕЦТ	РЕЈЕЦТ	РЕЈЕЦТ	РЕЈЕЦТ
А	ПОП АДВАНЦЕ	РЕЈЕЦТ	РЕЈЕЦТ	АЦЦЕПТ