\documentclass[a4paper]{article}
\textwidth 18cm \textheight 26cm \topmargin -3cm
\parindent 0.46in
\headsep 0.2in \oddsidemargin -2cm \evensidemargin 0cm
\hoffset0.8cm \voffset 1.8cm \pagestyle{empty}
\begin{document}

\begin{center}
\textbf{Prevodioci i interpretatori - Februar 2004.}\\
teorijski deo ispita
\end{center}
\begin{enumerate}
\item
\begin{enumerate}
\item Konstruisati potisni automat koji metodom sintaksne analize
nani\v ze (top-down parsing) prihvata jezik $L=\{x^ny^mz^n, n\geq
1, m\geq 1\}$

\item Konstruisati potisni automat koji metodom sintaksne analize
navi\v se (bottom-up parsing) prihvata isti jezik.

\item Simulirati rad oba automata za datu nisku $xxyyzz$.
\end{enumerate}

\item
\begin{enumerate} \item Konsturisati LL(1) gramatiku koja
opisuje jezik uredjenih parova, pri \v cemu elementi uredjenih
parova mogu biti ili elementi  $\Sigma=\{a,b\}$ ili sami uredjeni
parovi. Npr. $(((a, a), (a, (b, b)) ), (a, b) )$

\item Konstruisati odgovaraju\' ci potisni automat i pokazati
njegov rad na datom primeru.

\item Napisati program u C-u koji simulira rad konstruisanog
automata.
\end{enumerate}

\item Napisati gramatiku koja opisuje \textit{if} iskaze u
\textit{Pascal}-u. Dozvoljeni uslovi u if-iskazima su isklju\v
civo relacije pored~jenja izmedju brojeva ili niski, a pridru\v
zene naredbe na naredbe dodele oblika \texttt{ime := broj} ili
\verb"ime := niska", pri \v cemu je dozvoljeno i grupisanje vi\v
se naredbi u blok kori\v s\' cenjem slu\v zbenih re\v ci
\verb"begin" i \verb"end". Takvu gramatiku transformisati u LL(1),
pa konstruisati odgovaraju\' ci potisni automat i simulirati
njegov rad na primeru:
\begin{verbatim}
                          if 5>3 then
                          begin
                              ime='Pera';
                              broj=3;
                          end
\end{verbatim}

\item Konstruisati minimalni deterministi\v cki automat kona\v can
automat koji prepoznaje re\v ci nad $\Sigma=\{a, b\}$ u kojima se
poslednje slovo javlja bar jo\v s dva puta prethodno u re\v ci.

\item Dokazati da je data gramatika vi\v sezna\v cna (ambiguous):
\begin{center}
\begin{tabular}{lll}
naredba &$\rightarrow$& \textit{if} uslov \textit{then} naredba \textit{else} naredba\\
&$|$&\textit{if} uslov \textit{then} naredba\\
&$|$&prom=broj\\
uslov &$\rightarrow$& broj rel broj\\
rel &$\rightarrow$& $<$ $|$ $>$ $|$ $\leq$ $|$ $\geq$ $|$ $=$\\
broj &$\rightarrow$& 0 $|$ \ldots $|$ 9
\end{tabular}
\end{center}
Konstruisati bar jednu nevi\v sezna\v cnu gramatiku ekvivalentnu
datoj.

\end{enumerate}


\end{document}
