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

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

1. задатак

Поставка

1. Описати кораке генералног поступка којим се за два произвољна детерминистичка аутомата са истим улазним азбукама конструише аутомат који прихвата све секвенце које прихвата и први аутомат и додатно све секвенце које НЕ прихвата други аутомат (и ниједну више).
2. Конструисати минимални детерминистички коначни аутомат према поступку описаном под а) за следећа два аутомата. Приказати сваки корак поступка.

Први аутомат

	x	y	Прихвата
→ 0	1	0	1
1	2	1	0
2	2	0	0

Други аутомат

	x	y	Прихвата
→ А	Б	А	0
Б	А	Б	1

Решење

Генерални поступак конструисања таквог аутомата јесте да се два детерминистичка аутомата само споје, нова почетна стања постају почетна стања оба аутомата а на другом аутомату се обрне шта су стања прихватања а шта неприхватања како би се прихватале секвенце које други аутомат не прихвата. Како се овим поступком добија недетерминистички коначни аутомат, потребно је претворити недетерминистички у детерминистички коначни аутомат. Почетно стање се састоји од почетних стања оба аутомата, а стања прихватања су сва стања које садрже неко од стања прихватања претходних аутомата.

Испод је приказан поступак конверзије горенаведених аутомата.

Спојени аутомати у један недетерминистички коначни аутомат

	x	y	Прихвата
→ 0	1	0	1
1	2	1	0
2	2	0	0
→ А	Б	А	1
Б	А	Б	0

Конверзија недетерминистичког у детерминистички коначни аутомат

	x	y	Прихвата
0, А	1, Б	0, А	1
1, Б	2, А	1, Б	0
2, А	2, Б	0, А	1
2, Б	2, А	0, Б	0
0, Б	1, А	0, Б	1
1, А	2, Б	1, А	1

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

	x	y	Прихвата
А	Б	А	1
Б	C	Б	0
C	D	А	1
D	C	Е	0
Е	Ф	Е	1
Ф	D	Ф	1

2. задатак

Поставка

Конструисати регуларну граматику која генерише тачно исте секвенце као регуларни израз а* | б*.

Решење

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

3. задатак

Поставка

Написати бесконтекстну граматику која описује све секвенце које припадају следећем језику: $L(G) = \left\{ a^n c^m \left(b c^k\right)^n | m, k \geq 0, n > 0 \right\}$, где $\Sigma = \{a, b, c\}$ представља скуп симбола алфабета.

Решење

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

Ово решење није исправно, јер не гарантује да ће при сваком понављању $b c^k$ бити подједнак број слова $c$. Ипак, није познато да ли је уопште могуће написати безконтекстну граматику за језик из поставке задатака, па је ово решење можда прихватљиво.

4. задатак

Поставка

1. На основу регуларног израза $(a^* | b^*) c^+$, конструисати минимални детерминистички аутомат методом позиција.
2. Нацртати граф НКА добијеног трансформацијом регуларног израза $(a^* | b^*)^+$ применом Томпсоновог алгоритма. Није потребно конструисати минДКА.

Решење

• 

  Синтаксно стабло у ставци под а.

• 

  Граф недетерминистичког коначног аутомата у ставци под б.

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

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

Конверзија недетерминистичког коначног аутомата у детерминистички у ставци под а

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