\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}

\
\newpage

\begin{small}
\color{blue}{

\begin{center}
\textbf{Prevodioci i interpretatori - mart 2007. - teorijski
deo ispita}
\end{center}
\begin{enumerate}
\item[0.] Definisati:
\begin{enumerate}
    \item Pojam binarne relacije na skupu $A$. Pojam tranzitivnog zatvorenja relacije.
    Relaciju izvo\dj enja $\Rightarrow$ u gramatici $G$. Relaciju $\Rightarrow^*$.
    Jezik gramatike $G$.
    \item Potisni automat i mogu\' ce na\v cine prihvatanja.
\end{enumerate}

\item Zadata je gramatika $G$ slede\' cim pravilima: $S\rightarrow A1|B0$, $A\rightarrow SB$, $B\rightarrow
A0|BA|1$. Konstruisati $\varepsilon$-slobodnu gramatiku bez leve rekurzije takvu da je $L(G') = L(G)$.

\item
\begin{enumerate}
\item Transformisati slede\' ci automat u automat bez $\varepsilon$-pokreta (ne vr\v se\' ci determinizaciju):

$\Sigma = \{a,b\},\quad     Q = \{0,1,2,3,4\}\quad     I = \{1\}\quad     F= \{3, 1\}$

\noindent $\quad d = \{(0, b, 0), (1, a, 0), (1,b,2), (1,\varepsilon,4),  (2,b,0), (2,\varepsilon,4), (2,a,3), (3,a,3), (3,\varepsilon,1), (3,a,4)\}$
\item Determinizovati i minimizovati dobijeni automat.
\end{enumerate}


\item Za gramatiku
    \begin{eqnarray*}
      S &\rightarrow& AB\ |\ BA\\
      A &\rightarrow& aA\ | \ a \\
      B &\rightarrow& Bb\ | \ \varepsilon
    \end{eqnarray*}
    \begin{enumerate}
        \item Konstruisati SLR(1) parser za gramatiku $G$ i odrediti action i goto tablice.
        Da li je gramatika $G$ SLR(1) gramatika? Da li je gramatika $G$ LR(0) gramatika?
        \item Simulirati rad konstruisanog parsera na prihvatanju niski $bbaaa$ i $aabbbb$.
        \item Opisati ograni\v cenja
        koja nastaju prilikom implementacije ovog parsera ukoliko je maksimalna dubina steka $n$.
        Modifikovati gramatiku tako da se ova ograni\v cenja uklone. Kolika je minimalna vrednost broja
        $n$ za koju implementirani modifikovani parser mo\v ze da radi bez ograni\v cenja?
    \end{enumerate}

\item Data je shema prevo\dj enja:
    \begin{eqnarray*}
      E &\rightarrow& TR \\
      R &\rightarrow& op\ \ T\ \{print(op.leksema)\}\ R\ |\ \varepsilon \\
      T &\rightarrow& broj\ \{print(broj.vrednost)\}
    \end{eqnarray*}
Nacrtati drvo izvo\dj enja za izraz $5+3-2$ (uklju\v cuju\' ci
akcije). Kako glasi prevod niske ukoliko se vr\v si obilazak
drveta sa prvenstvom dubine (depth first). Re\v cima objasniti na
koji na\v cin ova shema transformi\v se aritmeti\v cke izraze.
\end{enumerate}

\vspace {0.2cm}
\begin{center}
\textbf{Prevodioci i interpretatori - mart 2007. - teorijski
deo ispita}
\end{center}
\begin{enumerate}
\item[0.] Definisati:
\begin{enumerate}
    \item Pojam binarne relacije na skupu $A$. Pojam tranzitivnog zatvorenja relacije.
    Relaciju izvo\dj enja $\Rightarrow$ u gramatici $G$. Relaciju $\Rightarrow^*$.
    Jezik gramatike $G$.
    \item Potisni automat i mogu\' ce na\v cine prihvatanja.
\end{enumerate}

\item Zadata je gramatika $G$ slede\' cim pravilima: $S\rightarrow A1|B0$, $A\rightarrow SB$, $B\rightarrow
A0|BA|1$. Konstruisati $\varepsilon$-slobodnu gramatiku bez leve rekurzije takvu da je $L(G') = L(G)$.

\item
\begin{enumerate}
\item Transformisati slede\' ci automat u automat bez $\varepsilon$-pokreta (ne vr\v se\' ci determinizaciju):

$\Sigma = \{a,b\},\quad     Q = \{0,1,2,3,4\}\quad     I = \{1\}\quad     F= \{3, 1\}$

\noindent $\quad d = \{(0, b, 0), (1, a, 0), (1,b,2), (1,\varepsilon,4),  (2,b,0), (2,\varepsilon,4), (2,a,3), (3,a,3), (3,\varepsilon,1), (3,a,4)\}$
\item Determinizovati i minimizovati dobijeni automat.
\end{enumerate}


\item Za gramatiku
    \begin{eqnarray*}
      S &\rightarrow& AB\ |\ BA\\
      A &\rightarrow& aA\ | \ a \\
      B &\rightarrow& Bb\ | \ \varepsilon
    \end{eqnarray*}
    \begin{enumerate}
        \item Konstruisati SLR(1) parser za gramatiku $G$ i odrediti action i goto tablice.
        Da li je gramatika $G$ SLR(1) gramatika? Da li je gramatika $G$ LR(0) gramatika?
        \item Simulirati rad konstruisanog parsera na prihvatanju niski $bbaaa$ i $aabbbb$.
        \item Opisati ograni\v cenja
        koja nastaju prilikom implementacije ovog parsera ukoliko je maksimalna dubina steka $n$.
        Modifikovati gramatiku tako da se ova ograni\v cenja uklone. Kolika je minimalna vrednost broja
        $n$ za koju implementirani modifikovani parser mo\v ze da radi bez ograni\v cenja?
    \end{enumerate}

\item Data je shema prevo\dj enja:
    \begin{eqnarray*}
      E &\rightarrow& TR \\
      R &\rightarrow& op\ \ T\ \{print(op.leksema)\}\ R\ |\ \varepsilon \\
      T &\rightarrow& broj\ \{print(broj.vrednost)\}
    \end{eqnarray*}
Nacrtati drvo izvo\dj enja za izraz $5+3-2$ (uklju\v cuju\' ci
akcije). Kako glasi prevod niske ukoliko se vr\v si obilazak
drveta sa prvenstvom dubine (depth first). Re\v cima objasniti na
koji na\v cin ova shema transformi\v se aritmeti\v cke izraze.
\end{enumerate}
}
\end{small}
\end{document}
