\documentclass[a4paper]{article}

\setlength{\textwidth}{18cm} \setlength{\oddsidemargin}{-1cm}
\setlength{\topmargin}{-2cm} \setlength{\textheight}{26cm}
\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}
\pagestyle{empty}

\begin{document}
\begin{small}
\begin{center}
\textbf{Prevodioci i interpretatori - Oktobar 2005.}
\end{center}

\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Neka su $x, y, z\in \Sigma^*$. Dokazati da je $x^2=y^2z^2$ ako i samo ako postoji $t\in \Sigma^*$, takvo
da $x, y, z\in t^*$ i $x=yz$. (Napomena: Poznata tvr\dj enja iz literature je dozvoljeno koristiti bez dokaza.)
\hfill[10]
\item
%\begin{enumerate}
%\item Regularnim izrazom i minimalnim deterministi\v ckim kona\v
%cnim automatom, opisati skup nepraznih re\v ci nad $\Sigma=\{0,
%1\}$ koje se sastoje od podjednakog broja nula i jedinica,
%pri \v cemu se u svakom njihovom prefiksu broj nula i jedinica razlikuje najvi\v se za 1.
%\item
Konstruisati minimalni deterministi\v cki kona\v cni automat za regularni izraz \verb"(a|b)+aba?".
\hfill[8]
%\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Izrazi se grade nad celobrojnim konstantama (dekadnim i
heksadekadnim) kori\v s\' cenjem bitskih operatora \verb"|",
\verb"&" i \verb"~", npr. \verb"(0x10 | 0x13) & ~0", pri \v cemu \verb"~" ima ve\' ci
prioritet nego \verb"&" koji ima ve\' ci prioritet nego
\verb"|". LL(1)
gramatikom opisati jezik opisanih izraza i kori\v s\' cenjem \textsc{c}-a i eventualno
\textsc{lex}-a napisati program koji
tehnikom rekurzivnog spusta ispisuje dekadnu vrednost izraza koji se
u\v citava sa standardnog ulaza.\hfill[20]
\end{enumerate}

\vspace{3cm}

\begin{center}
\textbf{Prevodioci i interpretatori - Oktobar 2005.}
\end{center}

\begin{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Neka su $x, y, z\in \Sigma^*$. Dokazati da je $x^2=y^2z^2$
ako i samo ako postoji $t\in \Sigma^*$, takvo da $x, y, z\in t^*$
i $x=yz$. (Napomena: Poznata tvr\dj enja iz literature je
dozvoljeno koristiti bez dokaza.) \hfill[10] \item
%\begin{enumerate}
%\item Regularnim izrazom i minimalnim deterministi\v ckim kona\v
%cnim automatom, opisati skup nepraznih re\v ci nad $\Sigma=\{0,
%1\}$ koje se sastoje od podjednakog broja nula i jedinica,
%pri \v cemu se u svakom njihovom prefiksu broj nula i jedinica razlikuje najvi\v se za 1.
%\item
Konstruisati minimalni deterministi\v cki kona\v cni automat za
regularni izraz \verb"(a|b)+aba?". \hfill[8]
%\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Izrazi se grade nad celobrojnim konstantama (dekadnim i
heksadekadnim) kori\v s\' cenjem bitskih operatora \verb"|",
\verb"&" i \verb"~", npr. \verb"(0x10 | 0x13) & ~0", pri \v cemu
\verb"~" ima ve\' ci prioritet nego \verb"&" koji ima ve\' ci
prioritet nego \verb"|". LL(1) gramatikom opisati jezik opisanih
izraza i kori\v s\' cenjem \textsc{c}-a i eventualno
\textsc{lex}-a napisati program koji tehnikom rekurzivnog spusta
ispisuje dekadnu vrednost izraza koji se u\v citava sa standardnog
ulaza.\hfill[20]



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\item
%\begin{enumerate}
%\item
%LL(1) gramatikom opisati sintaksu DTD dokumenata. Ograni\v
%citi se isklju\v civo na konstrukte koji se javljaju u slede\' cem primeru:

%\begin{footnotesize}
%\begin{verbatim}
%        <!ELEMENT catalog   (book | article)*>
%        <!ELEMENT book      (title, authors, publisher)>
%        <!ELEMENT article   (title, authors)>
%        <!ELEMENT authors   (author+)>

%        <!ELEMENT title     (#PCDATA)>
%        <!ELEMENT author    (#PCDATA)>
%        <!ELEMENT publisher EMPTY>
%        <!ATTLIST publisher
%            name    CDATA      #REQUIRED
%            year    CDATA      #IMPLIED
%            country (USA | YU) #IMPLIED>
%\end{verbatim}
%\end{footnotesize}

%\item Napisati primer {\sc xml} dokumenta koji je u skladu sa navedenim {\sc dtd} a koji
%opisuje bar tri knjige i jedan \v clanak iz oblasti prevo\dj enja.
%\end{enumerate}
\end{enumerate}



\vspace{2.5cm}
\begin{center}
\textbf{Prevodioci i interpretatori - Septembar 2005.}
\end{center}

\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Neka su $x, y, z\in \Sigma^*$. Dokazati da je $x^2=y^2z^2$
ako i samo ako postoji $t\in \Sigma^*$, takvo da $x, y, z\in t^*$
i $x=yz$. (Napomena: Poznata tvr\dj enja iz literature je
dozvoljeno koristiti bez dokaza.) \hfill[10] \item
%\begin{enumerate}
%\item Regularnim izrazom i minimalnim deterministi\v ckim kona\v
%cnim automatom, opisati skup nepraznih re\v ci nad $\Sigma=\{0,
%1\}$ koje se sastoje od podjednakog broja nula i jedinica,
%pri \v cemu se u svakom njihovom prefiksu broj nula i jedinica razlikuje najvi\v se za 1.
%\item
Konstruisati minimalni deterministi\v cki kona\v cni automat za
regularni izraz \verb"(a|b)+aba?". \hfill[8]
%\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Izrazi se grade nad celobrojnim konstantama (dekadnim i
heksadekadnim) kori\v s\' cenjem bitskih operatora \verb"|",
\verb"&" i \verb"~", npr. \verb"(0x10 | 0x13) & ~0", pri \v cemu
\verb"~" ima ve\' ci prioritet nego \verb"&" koji ima ve\' ci
prioritet nego \verb"|". LL(1) gramatikom opisati jezik opisanih
izraza i kori\v s\' cenjem \textsc{c}-a i eventualno
\textsc{lex}-a napisati program koji tehnikom rekurzivnog spusta
ispisuje dekadnu vrednost izraza koji se u\v citava sa standardnog
ulaza.\hfill[20]
\end{enumerate}

\vspace{2cm}
\begin{center}
\textbf{Prevodioci i interpretatori - Septembar 2005.}
\end{center}

\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Neka su $x, y, z\in \Sigma^*$. Dokazati da je $x^2=y^2z^2$
ako i samo ako postoji $t\in \Sigma^*$, takvo da $x, y, z\in t^*$
i $x=yz$. (Napomena: Poznata tvr\dj enja iz literature je
dozvoljeno koristiti bez dokaza.) \hfill[10] \item
%\begin{enumerate}
%\item Regularnim izrazom i minimalnim deterministi\v ckim kona\v
%cnim automatom, opisati skup nepraznih re\v ci nad $\Sigma=\{0,
%1\}$ koje se sastoje od podjednakog broja nula i jedinica,
%pri \v cemu se u svakom njihovom prefiksu broj nula i jedinica razlikuje najvi\v se za 1.
%\item
Konstruisati minimalni deterministi\v cki kona\v cni automat za
regularni izraz \verb"(a|b)+aba?". \hfill[8]
%\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Izrazi se grade nad celobrojnim konstantama (dekadnim i
heksadekadnim) kori\v s\' cenjem bitskih operatora \verb"|",
\verb"&" i \verb"~", npr. \verb"(0x10 | 0x13) & ~0", pri \v cemu
\verb"~" ima ve\' ci prioritet nego \verb"&" koji ima ve\' ci
prioritet nego \verb"|". LL(1) gramatikom opisati jezik opisanih
izraza i kori\v s\' cenjem \textsc{c}-a i eventualno
\textsc{lex}-a napisati program koji tehnikom rekurzivnog spusta
ispisuje dekadnu vrednost izraza koji se u\v citava sa standardnog
ulaza.\hfill[20]
\end{enumerate}

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}
\item[4.] Gramatika $G$ je opisana slede\' cim skupom pravila
    \begin{eqnarray*}
      S' &\rightarrow& SX \\
      S &\rightarrow& Aa\ | \ Bb\ |\ ac \\
      A &\rightarrow& a\\
      B &\rightarrow& b\\
      X &\rightarrow& xX\ |\ \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?
        \item Simulirati rad konstruisanog parsera na prihvatanju niski $acxx$ i $aax$ i $bb$.
        \item Da li je gramatika $G$ LR(0) gramatika? Obrazlo\v ziti.     \hfill[12]
 %       \item Da li je gramatika $G$ vi\v sezna\v cna? Re\v cima opisati op\v sti postupak
 %       koji za proizvoljnu gramatiku utvr\dj uje da li je vi\v sezna\v cna.
   \end{enumerate}
\end{enumerate}
\vspace{1cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}
\item[4.] Gramatika $G$ je opisana slede\' cim skupom pravila
    \begin{eqnarray*}
      S' &\rightarrow& SX \\
      S &\rightarrow& Aa\ | \ Bb\ |\ ac \\
      A &\rightarrow& a\\
      B &\rightarrow& b\\
      X &\rightarrow& xX\ |\ \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?
        \item Simulirati rad konstruisanog parsera na prihvatanju niski $acxx$ i $aax$ i $bb$.
        \item Da li je gramatika $G$ LR(0) gramatika? Obrazlo\v ziti.     \hfill[12]
 %       \item Da li je gramatika $G$ vi\v sezna\v cna? Re\v cima opisati op\v sti postupak
 %       koji za proizvoljnu gramatiku utvr\dj uje da li je vi\v sezna\v cna.
   \end{enumerate}
\end{enumerate}
\vspace{1cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}
\item[4.] Gramatika $G$ je opisana slede\' cim skupom pravila
    \begin{eqnarray*}
      S' &\rightarrow& SX \\
      S &\rightarrow& Aa\ | \ Bb\ |\ ac \\
      A &\rightarrow& a\\
      B &\rightarrow& b\\
      X &\rightarrow& xX\ |\ \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?
        \item Simulirati rad konstruisanog parsera na prihvatanju niski $acxx$ i $aax$ i $bb$.
        \item Da li je gramatika $G$ LR(0) gramatika? Obrazlo\v ziti.     \hfill[12]
 %       \item Da li je gramatika $G$ vi\v sezna\v cna? Re\v cima opisati op\v sti postupak
 %       koji za proizvoljnu gramatiku utvr\dj uje da li je vi\v sezna\v cna.
   \end{enumerate}
\end{enumerate}
\vspace{1cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}
\item[4.] Gramatika $G$ je opisana slede\' cim skupom pravila
    \begin{eqnarray*}
      S' &\rightarrow& SX \\
      S &\rightarrow& Aa\ | \ Bb\ |\ ac \\
      A &\rightarrow& a\\
      B &\rightarrow& b\\
      X &\rightarrow& xX\ |\ \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?
        \item Simulirati rad konstruisanog parsera na prihvatanju niski $acxx$ i $aax$ i $bb$.
        \item Da li je gramatika $G$ LR(0) gramatika? Obrazlo\v ziti.     \hfill[12]
 %       \item Da li je gramatika $G$ vi\v sezna\v cna? Re\v cima opisati op\v sti postupak
 %       koji za proizvoljnu gramatiku utvr\dj uje da li je vi\v sezna\v cna.
   \end{enumerate}
\end{enumerate}


\end{small}
\end{document}
