\documentclass[a4paper]{article}

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

\begin{document}
\
\newpage
\begin{small}

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

\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Pokazati da je skup regularnih jezika nad azbukom $\Sigma$ zatvoren u odnosu na operaciju
$$
\min(L) = \{w\ |\ w\in L,\textrm{ nijedan pravi prefiks re\v ci}\ w\ \textrm{nije u }L \}
$$
\hfill[15]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item LL(1) gramatikom opisati osnovne regularne izraze nad azbukom $\Sigma=\{a, b\}$. Napisati
izvo\dj enje, drvo izvo\dj enja i drvo apstraktne sintakse za izraz $(a^*b|ba^*)^*$.
\hfill[12]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Osloboditi se leve rekurzije u gramatici
\begin{eqnarray*}
A &\rightarrow& BC\quad |\quad a\\
B & \rightarrow & CA\quad |\quad Ab\\
C & \rightarrow & AB\quad |\quad CC\quad|\quad a
\end{eqnarray*}
bez uvodjenja $\varepsilon$ pravila.
\hfill[8]
\end{enumerate}


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

\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Pokazati da je skup regularnih jezika nad azbukom $\Sigma$ zatvoren u odnosu na operaciju
$$
\min(L) = \{w\ |\ w\in L,\textrm{ nijedan pravi prefiks re\v ci}\ w\ \textrm{nije u }L \}
$$
\hfill[15]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item LL(1) gramatikom opisati osnovne regularne izraze nad azbukom $\Sigma=\{a, b\}$. Napisati
izvo\dj enje, drvo izvo\dj enja i drvo apstraktne sintakse za izraz $(a^*b|ba^*)^*$.
\hfill[12]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Osloboditi se leve rekurzije u gramatici
\begin{eqnarray*}
A &\rightarrow& BC\quad |\quad a\\
B & \rightarrow & CA\quad |\quad Ab\\
C & \rightarrow & AB\quad |\quad CC\quad|\quad a
\end{eqnarray*}
bez uvodjenja $\varepsilon$ pravila.
\hfill[8]
\end{enumerate}

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

\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Pokazati da je skup regularnih jezika nad azbukom $\Sigma$ zatvoren u odnosu na operaciju
$$
\min(L) = \{w\ |\ w\in L,\textrm{ nijedan pravi prefiks re\v ci}\ w\ \textrm{nije u }L \}
$$
\hfill[15]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item LL(1) gramatikom opisati osnovne regularne izraze nad azbukom $\Sigma=\{a, b\}$. Napisati
izvo\dj enje, drvo izvo\dj enja i drvo apstraktne sintakse za izraz $(a^*b|ba^*)^*$.
\hfill[12]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Osloboditi se leve rekurzije u gramatici
\begin{eqnarray*}
A &\rightarrow& BC\quad |\quad a\\
B & \rightarrow & CA\quad |\quad Ab\\
C & \rightarrow & AB\quad |\quad CC\quad|\quad a
\end{eqnarray*}
bez uvodjenja $\varepsilon$ pravila.
\hfill[8]
\end{enumerate}

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

\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Pokazati da je skup regularnih jezika nad azbukom $\Sigma$ zatvoren u odnosu na operaciju
$$
\min(L) = \{w\ |\ w\in L,\textrm{ nijedan pravi prefiks re\v ci}\ w\ \textrm{nije u }L \}
$$
\hfill[15]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item LL(1) gramatikom opisati osnovne regularne izraze nad azbukom $\Sigma=\{a, b\}$. Napisati
izvo\dj enje, drvo izvo\dj enja i drvo apstraktne sintakse za izraz $(a^*b|ba^*)^*$.
\hfill[12]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Osloboditi se leve rekurzije u gramatici
\begin{eqnarray*}
A &\rightarrow& BC\quad |\quad a\\
B & \rightarrow & CA\quad |\quad Ab\\
C & \rightarrow & AB\quad |\quad CC\quad|\quad a
\end{eqnarray*}
bez uvodjenja $\varepsilon$ pravila.
\hfill[8]
\end{enumerate}


\newpage
\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item[4.] Gramatika $G$ je opisana slede\' cim skupom pravila
    \begin{eqnarray*}
      S &\rightarrow& A\ |\ B \\
      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?
        \item Simulirati rad konstruisanog parsera na prihvatanju niski $aaaa$ i $bbbb$.
        \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?
%        \item Ispitati da li je gramatika $G$ LR(0) gramatika.
%        \item Da li je gramatika $G$ vi\v sezna\v cna? Opisati op\v sti postupak koji za proizvoljnu gramatiku
%        utvr\dj uje da li je vi\v sezna\v cna.
    \end{enumerate}
    \hfill[15]
\end{enumerate}

\vspace{1cm}
\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item[4.] Gramatika $G$ je opisana slede\' cim skupom pravila
    \begin{eqnarray*}
      S &\rightarrow& A\ |\ B \\
      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?
        \item Simulirati rad konstruisanog parsera na prihvatanju niski $aaaa$ i $bbbb$.
        \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?
%        \item Ispitati da li je gramatika $G$ LR(0) gramatika.
%        \item Da li je gramatika $G$ vi\v sezna\v cna? Opisati op\v sti postupak koji za proizvoljnu gramatiku
%        utvr\dj uje da li je vi\v sezna\v cna.
    \end{enumerate}
    \hfill[15]
\end{enumerate}

\vspace{1cm}
\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item[4.] Gramatika $G$ je opisana slede\' cim skupom pravila
    \begin{eqnarray*}
      S &\rightarrow& A\ |\ B \\
      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?
        \item Simulirati rad konstruisanog parsera na prihvatanju niski $aaaa$ i $bbbb$.
        \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?
%        \item Ispitati da li je gramatika $G$ LR(0) gramatika.
%        \item Da li je gramatika $G$ vi\v sezna\v cna? Opisati op\v sti postupak koji za proizvoljnu gramatiku
%        utvr\dj uje da li je vi\v sezna\v cna.
    \end{enumerate}
    \hfill[15]
\end{enumerate}

\vspace{1cm}
\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item[4.] Gramatika $G$ je opisana slede\' cim skupom pravila
    \begin{eqnarray*}
      S &\rightarrow& A\ |\ B \\
      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?
        \item Simulirati rad konstruisanog parsera na prihvatanju niski $aaaa$ i $bbbb$.
        \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?
%        \item Ispitati da li je gramatika $G$ LR(0) gramatika.
%        \item Da li je gramatika $G$ vi\v sezna\v cna? Opisati op\v sti postupak koji za proizvoljnu gramatiku
%        utvr\dj uje da li je vi\v sezna\v cna.
    \end{enumerate}
    \hfill[15]
\end{enumerate}

\end{small}
\end{document}
