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

Овај рок није решен. Помозите СИ Wики тако што ћете га решити.

Први колоквијум 2022. године одржан је 31. октобра и трајао је 90 минута. Поставка рока још увек није званично доступна са странице предмета.

1. задатак

Поставка

Дата су три детерминистичка аутомата, M, Н и П.

1. Направити детерминистички коначни аутомат К који прихвата секвенце типа $s_1|(s_2s_3)$, где су $s_1$ све секвенце које аутомат M одбија, а $s_2$ и $s_3$ секвенце које аутомати Н и П прихватају, респективно.
2. Од аутомата из тачке под а направити десно-линеарну граматику, а затим из ње избацити све недостижне или мртве нетерминале.

Аутомат 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. имплицитном представом функција стања