\documentclass[a4paper]{article}
\setlength{\oddsidemargin}{-1cm} \setlength{\topmargin}{-3cm}
\setlength{\textwidth}{18cm} \setlength{\textheight}{26cm}
\pagestyle{empty}

\def\DJ{\leavevmode\setbox0=\hbox{D}\kern0pt
 \rlap{\kern.04em\raise.188\ht0\hbox{-}}D}
\def\dj{\leavevmode\setbox0=\hbox{d}\kern0pt
 \rlap{\kern.215em\raise.46\ht0\hbox{-}}d}

\usepackage{amssymb}
\usepackage{comment}
\usepackage{color}

\begin{document}

\begin{small}

\begin{center}
\textbf{Prevodioci i interpretatori - mart 2007. - prakti\v cni
deo ispita}
\end{center}
\begin{enumerate}
\item Posmatrajmo fragment programskog jezika \textsc{pascal} u
kome je dopu\v steno kori\v s\' cenje naredbi \verb"while",
\verb"if", dodele brojevne konstante promenljivoj i pore\dj enje
dve promenljive/konstante. Npr.
\begin{verbatim}
while a > 3 do
begin
    if a > 5 then
       a = 2;
    if a > b then
    begin
        tmp = a;
        a = b;
        b = tmp
    end
end
\end{verbatim}
\begin{enumerate}
\item LL(1) gramatikom opisati opisani fragment jezika i odrediti skupove izbora.
\item Napisati \textsc{perl}     skript koji vr\v se\' ci simulaciju potisnog automata nani\v ze
proverava da li program u datoteci \v cije se ime navodi kao prvi argument komandne linije
pripada datom fragmentu jezika.
\end{enumerate}

\item Implementirati sistem koji korisniku daje mogu\' cnost davanja odgovora
o svojstvima relacija definisanih na kona\v cnim domenima.
Kona\v cni skupovi elemenata se defini\v su klju\v cnom re\v cju \verb"type"
kao intervali \verb"a..b", ili navo\dj enjem njihovih elemenata u viti\v castim zagradama.
Relacije se navode klju\v cnom re\v cju \verb"relation", zatim navo\dj enjem jednog ili
vi\v se domena relacije i nakon toga definisanjem relacije u obliku skupa n-torki.
Relacija \verb"=" je automatski na raspolaganju.
Pitanja o svojstvima relacije se postavljaju klju\v cnom re\v cju \verb"question", a
odgovori na njih se dobijaju klju\v cnom re\v cju \verb"answer". Pitaja su re\v cenice
logike prvog reda na datom relacijskom jeziku.
Konjunkcija se ozna\v cava operatorom \verb"&", disjunkcija operatorom
\verb"|", implikacija operatorom \verb"-->", negacija operatorom \verb"~". Uz kvantifikatore se navodi kvantifikatorska
promenljiva i njen domen. Univerzalni kvantifikator se ozna\v cava sa
\verb"!(x::domain). formula", a egzistencijalni sa \verb"?(x::domain). formula"
\begin{verbatim}
> type int4 = 1..4;
        Type int4 defined as {1, 2, 3, 4}
> type odd4 = {1, 3};
        Type odd4 defined as {1, 3}
> relation R(int4, odd4) = {(1, 3), (2, 1), (3, 3), (4, 1)};
        Relation R defined
> relation S(int4, int4, int4) = {(1, 1, 1), (1, 2, 3), (3, 2, 1)};
        Relation S defined
> relation T(int4, odd4) = {(1, 2)};
        Error: T definition incorrect. Skipping.
> question 1R3 = R(1, 3);
        Question 1R3 defined
> answer 1R3;
        Answer: TRUE
> question questionAboutS = ~(S(1, 1, 1) | S(2, 1, 3));
        Question questionAboutS defined
> question isFunctionR = !(x::int4). !(y1::odd4). !(y2::odd4).
                                (R(x, y1) & R(x, y2) --> y1 = y2);
        Question isFunctionR defined
> answer questionAboutS;
        Answer: FALSE
> answer isFunctionR;
        Answer: TRUE
> relation R(int4, odd4) = {(1, 1), (1, 3), (2, 1), (2, 3)};
        Relation R defined
> answer isFunctionR;
        Answer: FALSE
\end{verbatim}


Predlog redosleda re\v savanja zadatka:
\begin{enumerate}
    \item Odabrati strukturu podataka za reprezentovanje kona\v cnih skupova i
          omogu\' citi njihovo definisanje (\verb"type" direktivu).
    \item Definisati strukturu podataka za reprezentovanje relacije i
    omogu\' citi njihovo definisanje (\verb"relation" direktivu). U po\v cetku
    presko\v citi proveru korektnosti.
    \item Definisati strukturu podataka za reprezentovanje formula (pitanja)
    i omogu\' citi definisanje i odgovaranje (\verb"question", \verb"answer") isklju\v civo na atomi\v cna pitanja
    ($R(x_1, \ldots, x_n)$).
    \item Omogu\' citi pojavu operatora \verb"&", \verb"|", \verb"-->" i \verb"~" u pitanjima.
    \item Omogu\' citi pojavu kvantifikatora u pitanjima.
\end{enumerate}

\end{enumerate}
\end{small}
\end{document}
