\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}
\usepackage{color}

\begin{document}
\begin{small}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%-------------------------------------------------------------------------
\begin{center}
\textbf{Prevodioci i interpretatori - 1. kolokvijum 2007/08.}
\end{center}
\begin{enumerate}
\item Izvorni jezik $S$ evoluira ka verziji $S_1$, npr. originalni
C prema standardizovanom. Opisati pomo\' cu T-dijagrama
konstrukciju kompilatora za $S_1$ ako raspola\v zemo kompilatorom
za $S$.

\item Neka su $x, y\in \Sigma^*$. Pokazati da ako postoje dva cela
broja $n$ i $m$, od kojih je bar jedan razli\v cit od 0 i takvi da
je $x^n = y^m$, onda postoji $z\in \Sigma^*$ takvo da je $x\in
z^*$ i $y\in z^*$.

\item
\begin{enumerate}
\item Definisati pojmove kona\v cnog automata i jezika koji
automat prepoznaje.

\item Odrediti jezik kona\v cnog automata nad $\Sigma = \{a,b\}$
zadatog slede\' com tablicom (po\v cetno i zavr\v sno stanje je
stanje 0)

\begin{tabular}{l|lllll}
  &   0  & 1 &  2 &  3 &  4\\
\hline
a &  1 &  2 &  3 &  4 &  0\\
b &  4 &  0 &  1 &  2 &  3\\
\end{tabular}
\end{enumerate}

\item
\begin{enumerate}
\item Dokazati da je presek deterministi\v ckih automata
deterministi\v cki automat.

\item Koriste\' ci svojstva zatvorenja, konstruisati {\em direktno
determinsti\v cki} kona\v cni automat koji prepoznaje jezik $L$
nad $\Sigma = \{a, b\}$ gde je $L = L_1 \cap L_2$,  $L_1 =
ab\Sigma^*$ i $L_2 = (\Sigma^4)^*$.
\end{enumerate}

\item Ispitati da li su jezici $L_1 = (a^*b)^*a^*$ i $L_2 =
(b^*a)^*b^*$ jednaki.
\end{enumerate}
%-------------------------------------------------------------------------
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%**************************************************************************
\begin{center}
\textbf{Prevodioci i Interpretatori - 1. kolokvijum 2007/08.}
\end{center}
\begin{enumerate}
\item Objektni jezik $O$ evoluira ka verziji $O_1$. Opisati pomo\'
cu T-dijagrama konstrukciju kompilatora za izvorni jezik $L$ ako
raspola\v zemo kompilatorom za koji $L$ prevodi na $O$.



\item Neka su $x, y\in \Sigma^*$. Pokazati da ako postoji $z\in
\Sigma^*$ takvo da je $x\in z^*$ i $y\in z^*$ tada postoje dva
cela broja $n$ i $m$, od kojih je bar jedan razli\v cit od 0 i
takvi da je $x^n = y^m$.


\item
\begin{enumerate}
\item Definisati pojmove regularnog skupa, regulranog izraza i
regulranog jezika.

\item Odrediti jezik kona\v cnog automata nad $\Sigma = \{a,b\}$
zadatog slede\' com tablicom (po\v cetno stanje je 1, a zavr\v sno
stanje je stanje 4)

\begin{tabular}{l|lllll}
  &   1 &  2 &  3 &  4\\
\hline
a &  2 &  1 &  4 &  2\\
b &  1 &  3 &  1 &  3\\
\end{tabular}
\end{enumerate}

\item
\begin{enumerate}
\item Dokazati da je unija deterministi\v ckih automata
deterministi\v cki automat.

\item Koriste\' ci svojstva zatvorenja, konstruisati {\em direktno
determinsti\v cki} kona\v cni automat koji prepoznaje jezik $L$
nad $\Sigma = \{a, b\}$ gde je $L = \{w\in \Sigma^*\ |\ w\
\mathrm{ima\ prefiks}\ a^3,\ \mathrm{a\  sufiks\ joj\ je\ ili\ }
a\mathrm{\ ili\ }b\}$.
\end{enumerate}

\item Ispitati da li su jezici $L_1 = (a^*b)^*$ i $L_2 =
\Sigma^*b$ jednaki.
\end{enumerate}
%**************************************************************************
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%-------------------------------------------------------------------------
\begin{center}
\textbf{Prevodioci i interpretatori - 1. kolokvijum 2007/08.}
\end{center}
\begin{enumerate}
\item Izvorni jezik $S$ evoluira ka verziji $S_1$, npr. originalni
C prema standardizovanom. Opisati pomo\' cu T-dijagrama
konstrukciju kompilatora za $S_1$ ako raspola\v zemo kompilatorom
za $S$.

\item Neka su $x, y\in \Sigma^*$. Pokazati da ako postoje dva cela
broja $n$ i $m$, od kojih je bar jedan razli\v cit od 0 i takvi da
je $x^n = y^m$, onda postoji $z\in \Sigma^*$ takvo da je $x\in
z^*$ i $y\in z^*$.

\item
\begin{enumerate}
\item Definisati pojmove kona\v cnog automata i jezika koji
automat prepoznaje.

\item Odrediti jezik kona\v cnog automata nad $\Sigma = \{a,b\}$
zadatog slede\' com tablicom (po\v cetno i zavr\v sno stanje je
stanje 0)

\begin{tabular}{l|lllll}
  &   0  & 1 &  2 &  3 &  4\\
\hline
a &  1 &  2 &  3 &  4 &  0\\
b &  4 &  0 &  1 &  2 &  3\\
\end{tabular}
\end{enumerate}

\item
\begin{enumerate}
\item Dokazati da je presek deterministi\v ckih automata
deterministi\v cki automat.

\item Koriste\' ci svojstva zatvorenja, konstruisati {\em direktno
determinsti\v cki} kona\v cni automat koji prepoznaje jezik $L$
nad $\Sigma = \{a, b\}$ gde je $L = L_1 \cap L_2$,  $L_1 =
ab\Sigma^*$ i $L_2 = (\Sigma^4)^*$.
\end{enumerate}

\item Ispitati da li su jezici $L_1 = (a^*b)^*a^*$ i $L_2 =
(b^*a)^*b^*$ jednaki.
\end{enumerate}
%-------------------------------------------------------------------------
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%**************************************************************************
\begin{center}
\textbf{Prevodioci i Interpretatori - 1. kolokvijum 2007/08.}
\end{center}
\begin{enumerate}
\item Objektni jezik $O$ evoluira ka verziji $O_1$. Opisati pomo\'
cu T-dijagrama konstrukciju kompilatora za izvorni jezik $L$ ako
raspola\v zemo kompilatorom za koji $L$ prevodi na $O$.



\item Neka su $x, y\in \Sigma^*$. Pokazati da ako postoji $z\in
\Sigma^*$ takvo da je $x\in z^*$ i $y\in z^*$ tada postoje dva
cela broja $n$ i $m$, od kojih je bar jedan razli\v cit od 0 i
takvi da je $x^n = y^m$.


\item
\begin{enumerate}
\item Definisati pojmove regularnog skupa, regulranog izraza i
regulranog jezika.

\item Odrediti jezik kona\v cnog automata nad $\Sigma = \{a,b\}$
zadatog slede\' com tablicom (po\v cetno stanje je 1, a zavr\v sno
stanje je stanje 4)

\begin{tabular}{l|lllll}
  &   1 &  2 &  3 &  4\\
\hline
a &  2 &  1 &  4 &  2\\
b &  1 &  3 &  1 &  3\\
\end{tabular}
\end{enumerate}

\item
\begin{enumerate}
\item Dokazati da je unija deterministi\v ckih automata
deterministi\v cki automat.

\item Koriste\' ci svojstva zatvorenja, konstruisati {\em direktno
determinsti\v cki} kona\v cni automat koji prepoznaje jezik $L$
nad $\Sigma = \{a, b\}$ gde je $L = \{w\in \Sigma^*\ |\ w\
\mathrm{ima\ prefiks}\ a^3,\ \mathrm{a\  sufiks\ joj\ je\ ili\ }
a\mathrm{\ ili\ }b\}$.
\end{enumerate}

\item Ispitati da li su jezici $L_1 = (a^*b)^*$ i $L_2 =
\Sigma^*b$ jednaki.
\end{enumerate}
%**************************************************************************
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{small}
\end{document}
