Први колоквијум 2017. године одржан је 28. октобра и трајао је два сата. Радна верзија поставке рока је доступна са странице предмета (архива).
1. задатак
Поставка
Пројектовати потисни аутомат који препознаје следећи скуп секвенци: 
Из задатог скупа изабрати једну секвенцу дужине веће од три и приказати процес њеног препознавања.
Решење
Прво стање потисне машине за препознавање секвенце
|
|
а
|
б
|
ц
|
─┤
|
| ∇
|
|
РЕЈЕЦТ
|
РЕЈЕЦТ
|
РЕЈЕЦТ
|
| А
|
|
|
|
АЦЦЕПТ
|
| Б
|
|
|
|
РЕЈЕЦТ
|
Друго стање потисне машине за препознавање секвенце
|
|
а
|
б
|
ц
|
─┤
|
| А
|
РЕЈЕЦТ
|
АДВАНЦЕ
|
РЕЈЕЦТ
|
АЦЦЕПТ
|
| Б
|
РЕЈЕЦТ
|
АДВАНЦЕ
|
|
РЕЈЕЦТ
|
Треће стање потисне машине за препознавање секвенце
|
|
а
|
б
|
ц
|
─┤
|
| А
|
РЕЈЕЦТ
|
РЕЈЕЦТ
|
РЕЈЕЦТ
|
АЦЦЕПТ
|
| Б
|
РЕЈЕЦТ
|
РЕЈЕЦТ
|
|
РЕЈЕЦТ
|
Рад овог аутомата можемо приказати на секвенци аабббц.
| Стек
|
Секвенца
|
Стање
|
Операције
|
| ∇
|
аабббц─┤
|
1
|
ПУСХ(А), АДВАНЦЕ
|
| ∇А
|
абббц─┤
|
1
|
ПУСХ(Б), АДВАНЦЕ
|
| ∇АБ
|
бббц─┤
|
1
|
АДВАНЦЕ, СТАТЕ(С2)
|
| ∇АБ
|
ббц─┤
|
2
|
АДВАНЦЕ
|
| ∇АБ
|
бц─┤
|
2
|
АДВАНЦЕ
|
| ∇АБ
|
ц─┤
|
2
|
РЕТАИН, СТАТЕ(С3)
|
| ∇АБ
|
ц─┤
|
3
|
ПОП, АДВАНЦЕ
|
| ∇А
|
─┤
|
3
|
АЦЦЕПТ
|
2. задатак
Поставка
Стабло из поставке другог задатка.
- Директно на задатом синтаксном стаблу једног регуларног израза назначити поништивост, и функције прва и последња позиција.
- Нацртати табелу са вредностима функције следећа позиција.
- На основу задатог стабла и резултата под а) одредити коначни аутомат. Обавезно навести поступак. Није потребна минимизација.
Решење
Стабло из решења другог задатка.
Табела следећих позиција
| Позиција
|
Следећа позиција
|
| 1
|
3
|
| 2
|
3
|
| 3
|
4, 5, 8
|
| 4
|
4, 5, 8
|
| 5
|
6
|
| 6
|
7, 8
|
| 7
|
7, 8
|
| 8
|
-
|
Поступак претварања синтаксног стабла у детерминистички коначни аутомат
|
|
+
|
-
|
д
|
.
|
Прихвата
|
| 1, 2, 3
|
3
|
3
|
4, 5, 8
|
|
0
|
| 3
|
|
|
4, 5, 8
|
|
0
|
| 4, 5, 8
|
|
|
4, 5, 8
|
6
|
1
|
| 6
|
|
|
7, 8
|
|
0
|
| 7, 8
|
|
|
7, 8
|
|
1
|
Детерминистички коначни аутомат
|
|
+
|
-
|
д
|
.
|
Прихвата
|
| А
|
Б
|
Б
|
C
|
|
0
|
| Б
|
|
|
C
|
|
0
|
| C
|
|
|
C
|
D
|
1
|
| D
|
|
|
Е
|
|
0
|
| Е
|
|
|
Е
|
|
1
|
3. задатак
Поставка
Недетерминистички коначни аутомат из поставке трећег задатка под б.
- Да ли су дати аутомати еквивалентни? Обавезно приказати поступак.
- Конвертовати задати недетерминистички аутомат у детерминистички. Обавезно приказати поступак. Није потребна минимизација.
Први аутомат из поставке трећег задатка под а
|
|
0
|
1
|
2
|
Прихвата
|
| → Аx
|
Аx
|
Аx
|
Бx
|
0
|
| Бx
|
Бx
|
Аx
|
Бx
|
1
|
Други аутомат из поставке трећег задатка под а
|
|
0
|
1
|
2
|
Прихвата
|
| → Аз
|
Цз
|
Аз
|
Бз
|
0
|
| Бз
|
Бз
|
Аз
|
Аз
|
1
|
| Цз
|
Цз
|
Аз
|
Бз
|
0
|
Решење
Поступак провере еквиваленције аутомата из трећег задатка под а
|
|
0
|
1
|
2
|
| Аx, Аз
|
Аx, Цз
|
Аx, Аз
|
Бx, Бз
|
| Аx, Цз
|
Аx, Цз
|
Аx, Аз
|
Бx, Бз
|
| Бx, Бз
|
Бx, Бз
|
Аx, Аз
|
Бз, Аз
|
Због тога што стања Бз и Аз нису компатибилна, ова два аутомата нису еквивалентна.
Поступак претварања недетерминистичког коначног аутомата у детерминистички
|
|
+
|
-
|
д
|
.
|
Прихвата
|
| → 1, 2, 4, 7, 8, 9
|
3, 8, 9
|
5, 8, 9
|
9, 10, 11, 12, 17, 18, 19
|
|
0
|
| 3, 8, 9
|
|
|
9, 10, 11, 12, 17, 18, 19
|
|
0
|
| 5, 8, 9
|
|
|
9, 10, 11, 12, 17, 18, 19
|
|
0
|
| 9, 10, 11, 12, 17, 18, 19
|
|
|
9, 10, 11, 12, 17, 18, 19
|
13, 14
|
1
|
| 13, 14
|
|
|
14, 15, 16, 19
|
|
0
|
| 14, 15, 16, 19
|
|
|
14, 15, 16, 19
|
|
1
|
Детерминистички коначни аутомат
|
|
+
|
-
|
д
|
.
|
Прихвата
|
| → А
|
Б
|
C
|
D
|
|
0
|
| Б
|
|
|
D
|
|
0
|
| C
|
|
|
D
|
|
0
|
| D
|
|
|
D
|
Е
|
1
|
| Е
|
|
|
Ф
|
|
0
|
| Ф
|
|
|
Ф
|
|
1
|
4. задатак
Поставка
?????
Решење
?????
