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

\begin{document}

\
\newpage

\begin{small}

\begin{center}
\textbf{Prevodioci i interpretatori - februar 2007. - teorijski
deo ispita}
\end{center}
\begin{enumerate}
\item 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 Levi koli\v cnik $x^{-1}L$, $x\in \Sigma^*$, $L\subseteq \Sigma^*$
    \item Ru\v cku re\v ceni\v cne forme.
    \item Skupove $First(A)$ i $Follow(A)$ za neterminal $A$.
\end{enumerate}


\item Razmatrajmo problem sabiranja binarnih brojeva. Npr.
\begin{verbatim}
01010 +
01100
---------
10110
\end{verbatim}
Postupak ovog sabiranja je mogu\' ce opisati trojkama binarnih
cifara i to po\v cev\v si od cifre najmanje te\v zine. Za dati
primer su to trojke \verb"(0,0,0)(1,0,1)(0,1,1)(1,1,0)(0,0,1)".
Ukoliko se izostave zagrade i zapete dobija se niska iz
$\Sigma=\{0, 1\}^*$. Za dati primer se dobija niska
\verb"000101011110001". Konstruisati kona\v
cni automat koji prepoznaje sve ovakve niske koje predstavljaju
ispravna sabiranja. Da li je mogu\' ce napraviti ovakav kona\v cni
automat ukolio bi se trojke cifara navodile po\v cev\v si od cifre
najve\' ce te\v zine?

\item Neka je $\Sigma=\{0, 1\}$. Za proizvoljnu re\v c $w\in
\Sigma^*$ defini\v simo $d(w)$ kao nisku koja se dobija od niske
$w$ time \v sto se svako $0$ zameni sa $00$ i svako $1$ zameni sa
$11$. Dalje, neka je $d(L) = \{d(w)\ |\ w\in L\}$. Ako je $L$
regularan jezik, da li je i $d(L)$ regularan jezik? Dokazati.

\item Data je gramatika $G$:
    \begin{eqnarray*}
      A &\rightarrow& BC \\
      B &\rightarrow& bB\ |\ \varepsilon\\
      C &\rightarrow& Cc\ |\ c\\
    \end{eqnarray*}
    \begin{enumerate}
        \item Konstruisati SLR(1) parser za gramatiku $G$ i odrediti \textsc{action} i \textsc{goto} tablice.
        \item Simulirati rad konstruisanog parsera na prihvatanju niski $cc$ i $bbc$.
        \item Na osnovu konstruisanog parsera, napisati program
        koji proverava da li data niska pripada jeziku $L(G)$.
    \end{enumerate}


\item \textsc{ll(1)} gramatikom opisati iterativne \verb"while"
iskaze u \textsc{pascal}-u i odrediti skupove izbora. Npr.
\begin{verbatim}
while i < 10 do             while i < n do
    i := i + 1              begin
                                j := i + 1;
                                while j < n do
                                    j := j + 1
                            end
\end{verbatim}

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