Први колоквијум 2022. године одржан је 31. октобра и трајао је 90 минута. Поставка рока још увек није званично доступна са странице предмета.
1. задатак
- Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.
Поставка
Дата су три детерминистичка аутомата, M, Н и П.
- Направити детерминистички коначни аутомат К који прихвата секвенце типа , где су све секвенце које аутомат M одбија, а и секвенце које аутомати Н и П прихватају, респективно.
- Од аутомата из тачке под а направити десно-линеарну граматику, а затим из ње избацити све недостижне или мртве нетерминале.
Аутомат M
|
0
|
1
|
Прихвата
|
А
|
А
|
Б
|
0
|
Б
|
Б
|
C
|
1
|
C
|
А
|
C
|
1
|
Аутомат Н
|
1
|
2
|
Прихвата
|
D
|
Е
|
|
1
|
Е
|
D
|
Е
|
0
|
Ф
|
Ф
|
Е
|
1
|
Аутомат П
|
0
|
а
|
Прихвата
|
1
|
1
|
2
|
1
|
2
|
|
1
|
0
|
Решење
Недетерминстички аутомат који прихвата с2с3
|
1
|
2
|
0
|
а
|
Прихвата
|
D
|
Е
|
|
|
|
0
|
Е
|
D,1
|
Е
|
|
|
0
|
Ф
|
Ф,1
|
Е
|
|
|
0
|
1
|
|
|
1
|
2
|
1
|
2
|
|
|
|
1
|
0
|
Детерминстички аутомат који прихвата с2с3
|
1
|
2
|
0
|
а
|
Прихвата
|
D,1
|
Е
|
|
1
|
2
|
1
|
Е
|
D,1
|
Е
|
|
|
0
|
1
|
|
|
1
|
2
|
1
|
2
|
|
|
|
2
|
0
|
Недетерминистички аутомат који прихвата тражену секвенцу
|
0
|
1
|
2
|
а
|
Прихвата
|
А
|
А
|
Б
|
|
|
1
|
Б
|
Б
|
C
|
|
|
0
|
C
|
А
|
C
|
|
|
0
|
D,1
|
1
|
Е
|
|
2
|
1
|
Е
|
|
D,1
|
Е
|
|
0
|
1
|
1
|
|
|
2
|
1
|
2
|
|
|
|
1
|
0
|
Детерминистички аутомат који прихвата тражену секвенцу
|
0
|
1
|
2
|
а
|
1
|
{А,D,1}, С0
|
А,1
|
Б,Е
|
|
2
|
1
|
{А,1}, С1
|
А,1
|
Б
|
|
2
|
1
|
{Б,Е}, С2
|
Б
|
C,Д,1
|
Е
|
|
0
|
{2}, С3
|
|
|
|
1
|
0
|
{Б}, С4
|
Б
|
C
|
|
|
0
|
{C,Д,1}, С5
|
А,1
|
C,Е
|
|
2
|
1
|
{Е}, С6
|
|
D,1
|
Е
|
|
0
|
{1}, С7
|
1
|
|
|
2
|
1
|
{C}, С8
|
А
|
C
|
|
|
0
|
{C,Е}, С9
|
А
|
C,Д,1
|
Е
|
|
0
|
{D,1}, С10
|
1
|
Е
|
|
2
|
1
|
{А}, С11
|
А
|
Б
|
|
|
1
|
2. задатак
Поставка
Аритметички израз се састоји из нула или више бројева, где је број низ цифара, са аритметичким операцијама сабирања или одузимања између њих. Уколико су терминали у датој азбуци једна цифра ("ЦИФРА"), знак за сабирање ("+") и знак за одузимање ("-") написати регуларни израз који описује дате аритметичке изразе, а затим га претворити у детерминистички коначни аутомат коришћењем метода позиција.
Решење
Позиционо стабло у другом задатку.
Табела следећих позиција
Позиција
|
Следећа позиција
|
1
|
1,2,3,5
|
2
|
4
|
3
|
4
|
4
|
1,2,3,4,5
|
5
|
/
|
Детерминистички коначни аутомат за тражени регуларни израз
|
ЦИФРА
|
+
|
-
|
Прихвата
|
1,5
|
1,2,3,5
|
|
|
1
|
1,2,3,5
|
1,2,3,5
|
4
|
4
|
1
|
4
|
1,2,3,4,5
|
|
|
0
|
1,2,3,4,5
|
1,2,3,4,5
|
4
|
4
|
1
|
3. задатак
- Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.
Поставка
Коначни аутомат из поставке задатка.
Написати фрагмент програмског кода који имплементира коначни аутомат са слике:
- експлицитном представом функције стања
- имплицитном представом функција стања
Решење