\documentclass[a4paper,dvipdfm]{article}

\setlength{\oddsidemargin}{-1cm} \setlength{\evensidemargin}{-1cm}
\setlength{\textwidth}{18cm}

\setlength{\topmargin}{-2cm} \setlength{\textheight}{25cm}

\pagestyle{empty}
\usepackage{graphics}

\begin{document}
{\small

\begin{center}
\textbf{Prevodioci i interpretatori - septembar 2004.\\teorijski
deo}
\end{center}
\begin{enumerate}
%---------------------------------------------------------------------
\item Pretpostavimo da je u transduktoru \begin{center}
\includegraphics{transduktor.jpg}
\end{center}
svako stanje zavr\v sno.

Pretpostavimo da se ulaz sastoji bar od \v cetiri slova. Koje(a)
od slede\' cih tvrdjenja su ta\v cna, a koja nisu? Odgovore
detaljno obrazlo\v ziti.
\begin{enumerate}
    \item Poslednji bit izlaza zavisi od po\v cetnog stanja
    \item Ako ulaz po\v cinje sa \verb"1100" izlaz se zavr\v sava
    sa \verb"1"
    \item Izlaz ne mo\v ze da se zavr\v si sa \verb"1" osim
    ukoliko se ulaz ne zavr\v sava sa \verb"1100" \hfill[8]
\end{enumerate}
%---------------------------------------------------------------------


%---------------------------------------------------------------------
\item Poznato je da je jezik $L\subseteq \{a,b\}^*$ koji se
sastoji od re\v ci koje imaju isti broj slova $a$ i $b$ kontekst
slobodan. Neka je $M$ regularan jezik $a*b*$. Koja od slede\' cih
tvrdjenja su ta\v cna, a koja nisu?
\begin{enumerate}
    \item $L \cap M$ je kontekst slobodan
    \item $L \cap M$ je regularan
    \item $L \cap M = \{a^nb^m|$ $n$ je prirodan broj manji od
    $m\}$
    \item Postoji kona\v can automat koji prepoznaje jezik $L \cap M$
    \item Postoji potisni automat koji prepoznaje jezik $L \cap M$\hfill[8]
\end{enumerate}
%---------------------------------------------------------------------


%---------------------------------------------------------------------
\item  Regularnim izrazom opisati binarne brojeve deljive sa 3.
\hfill[10]
%---------------------------------------------------------------------
\end{enumerate}



\vskip 1cm

\begin{center}
\textbf{Prevodioci i interpretatori - septembar 2004.\\teorijski
deo}
\end{center}
\begin{enumerate}
%---------------------------------------------------------------------
\item Pretpostavimo da je u transduktoru \begin{center}
\includegraphics{transduktor.jpg}
\end{center}
svako stanje zavr\v sno.

Pretpostavimo da se ulaz sastoji bar od \v cetiri slova. Koje(a)
od slede\' cih tvrdjenja su ta\v cna, a koja nisu? Odgovore
detaljno obrazlo\v ziti.
\begin{enumerate}
    \item Poslednji bit izlaza zavisi od po\v cetnog stanja
    \item Ako ulaz po\v cinje sa \verb"1100" izlaz se zavr\v sava
    sa \verb"1"
    \item Izlaz ne mo\v ze da se zavr\v si sa \verb"1" osim
    ukoliko se ulaz ne zavr\v sava sa \verb"1100" \hfill[8]
\end{enumerate}
%---------------------------------------------------------------------


%---------------------------------------------------------------------
\item Poznato je da je jezik $L\subseteq \{a,b\}^*$ koji se
sastoji od re\v ci koje imaju isti broj slova $a$ i $b$ kontekst
slobodan. Neka je $M$ regularan jezik $a*b*$. Koja od slede\' cih
tvrdjenja su ta\v cna, a koja nisu?
\begin{enumerate}
    \item $L \cap M$ je kontekst slobodan
    \item $L \cap M$ je regularan
    \item $L \cap M = \{a^nb^m|$ $n$ je prirodan broj manji od
    $m\}$
    \item Postoji kona\v can automat koji prepoznaje jezik $L \cap M$
    \item Postoji potisni automat koji prepoznaje jezik $L \cap M$\hfill[8]
\end{enumerate}
%---------------------------------------------------------------------


%---------------------------------------------------------------------
\item  Regularnim izrazom opisati binarne brojeve deljive sa 3.
\hfill[10]
%---------------------------------------------------------------------
\end{enumerate}




\newpage

\begin{enumerate}
%---------------------------------------------------------------------
\item[4] Koja od slede\' cih tvrdjenja su ta\v cna a koja nisu za
gramatiku opisanu Bekusovom notacijom:
\begin{verbatim}
       <S> ::= <A><B>
       <A> ::= a
       <A> ::= <B>a<B>
       <B> ::= bb<A>
\end{verbatim}

\begin{enumerate}
    \item Svaka re\v c jezika koji je opisan ovom gramatikom ima
    paran broj slova
    \item Nijedna re\v c jezika koji je opisan ovom gramatikom
    nema neparan broj uzastopnih \verb"b"-ova
    \item Nijedna re\v c jezika koji je opisan ovom gramatikom
    nema tri uzastopna slova \verb"a"
    \item Nijedna re\v c jezika koji je opisan ovom gramatikom
    nema \v cetiri uzastopna slova \verb"b"
    \item Svaka re\v c jezika koji je opisan ovom gramatikom ima
    bar onoliko \verb"b"-ova koliko i \verb"a"-ova \hfill[8]
\end{enumerate}

%---------------------------------------------------------------------

%---------------------------------------------------------------------
\item[5] Neka je $k\geq 2$. Neka je $L$ skup re\v ci u $\{0,1\}^*$
tako da je $x\in L$ akko je broj nula u $x$ deljiv brojem $k$ a
broj jedinica u $x$ neparan. Koji je najmanji broj stanja koje
mora da ima deterministi\v cki kona\v cni automat koji prepoznaje
$L$. Odgovor detaljno obrazlo\v ziti. \hfill[8]
%---------------------------------------------------------------------

%---------------------------------------------------------------------
\item[6] Ako NKA ozna\v cava nedeterministi\v cki, a DKA
deterministi\v cki kona\v cni automat, koja od slede\' cih
tvrdjenja su ta\v cna, a koja nisu?
\begin{enumerate}
    \item Za svaki jezik $L$, ukoliko neki DKA prepoznaje $L$,
    postoji DKA koji prepoznaje $\bar{L}$.
    \item Za svaki jezik $L$, ukoliko neki NKA prepoznaje $L$,
    postoji DKA koji prepoznaje $\bar{L}$.
    \item Za svaki jezik $L$, ukoliko neki DKA prepoznaje $L$,
    postoji NKA koji prepoznaje $\bar{L}$.
    \item Za svaki jezik $L$, ukoliko neki NKA prepoznaje $L$,
    postoji NKA koji prepoznaje $\bar{L}$.
    \item Za svaki jezik $L$, ukoliko je $L$ kontekst slobodan, onda
    je i $\bar{L}$ kontekst slobodan. \hfill[8]
\end{enumerate}
%---------------------------------------------------------------------

\end{enumerate}




\vskip 3cm

\begin{enumerate}
%---------------------------------------------------------------------
\item[4] Koja od slede\' cih tvrdjenja su ta\v cna a koja nisu za
gramatiku opisanu Bekusovom notacijom:
\begin{verbatim}
       <S> ::= <A><B>
       <A> ::= a
       <A> ::= <B>a<B>
       <B> ::= bb<A>
\end{verbatim}

\begin{enumerate}
    \item Svaka re\v c jezika koji je opisan ovom gramatikom ima
    paran broj slova
    \item Nijedna re\v c jezika koji je opisan ovom gramatikom
    nema neparan broj uzastopnih \verb"b"-ova
    \item Nijedna re\v c jezika koji je opisan ovom gramatikom
    nema tri uzastopna slova \verb"a"
    \item Nijedna re\v c jezika koji je opisan ovom gramatikom
    nema \v cetiri uzastopna slova \verb"b"
    \item Svaka re\v c jezika koji je opisan ovom gramatikom ima
    bar onoliko \verb"b"-ova koliko i \verb"a"-ova \hfill[8]
\end{enumerate}

%---------------------------------------------------------------------

%---------------------------------------------------------------------
\item[5] Neka je $k\geq 2$. Neka je $L$ skup re\v ci u $\{0,1\}^*$
tako da je $x\in L$ akko je broj nula u $x$ deljiv brojem $k$ a
broj jedinica u $x$ neparan. Koji je najmanji broj stanja koje
mora da ima deterministi\v cki kona\v cni automat koji prepoznaje
$L$. Odgovor detaljno obrazlo\v ziti. \hfill[8]
%---------------------------------------------------------------------

%---------------------------------------------------------------------
\item[6] Ako NKA ozna\v cava nedeterministi\v cki, a DKA
deterministi\v cki kona\v cni automat, koja od slede\' cih
tvrdjenja su ta\v cna, a koja nisu?
\begin{enumerate}
    \item Za svaki jezik $L$, ukoliko neki DKA prepoznaje $L$,
    postoji DKA koji prepoznaje $\bar{L}$.
    \item Za svaki jezik $L$, ukoliko neki NKA prepoznaje $L$,
    postoji DKA koji prepoznaje $\bar{L}$.
    \item Za svaki jezik $L$, ukoliko neki DKA prepoznaje $L$,
    postoji NKA koji prepoznaje $\bar{L}$.
    \item Za svaki jezik $L$, ukoliko neki NKA prepoznaje $L$,
    postoji NKA koji prepoznaje $\bar{L}$.
    \item Za svaki jezik $L$, ukoliko je $L$ kontekst slobodan, onda
    je i $\bar{L}$ kontekst slobodan. \hfill[8]
\end{enumerate}
%---------------------------------------------------------------------

\end{enumerate}


%*********************************************************************
}
\end{document}
