\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}

\begin{document}
\begin{small}
\begin{comment}
\begin{center}
\textbf{Prevodioci i interpretatori - januar 2006. - test}
\end{center}

\begin{enumerate}
  \item Me\dj u slede\' cim jezicima zaokru\v ziti regularne i opisati ih regularnim izrazima.
  \begin{enumerate}
    \item $\{a^mb^n,\ m, n\in \mathbb{N}\}$
    \item $\{a^nb^n,\ n\in \mathbb{N}\}$
    \item $\{a^nb^mc^n,\ m,n\in \mathbb{N}\}$
    \item $\{a^nb^n,\ 0\leq n\leq 2006\}$
    \item $\{a^p, p\textrm{ je prost broj\}}$
    \item $\{a^nb^mc^p,\ m,n,p\in \mathbb{N}\}$
  \end{enumerate}

  \item Me\dj u slede\' cim jezicima zaokru\v ziti kontekstno slobodne i opisati ih KS gramatikama.
  \begin{enumerate}
    \item $\{a^mb^n,\ m, n\in \mathbb{N}\}$
    \item $\{a^nb^n,\ n\in \mathbb{N}\}$
    \item $\{a^nb^nc^n,\ n\in \mathbb{N}\}$
    \item $\{ww^{r},\ w\in \{a, b\}^*\}$
    \item $\{a^p, p\textrm{ je prost broj\}}$
    \item $\{ww,\ w\in \{a, b\}^*\}$
  \end{enumerate}

  \item Zaokru\v ziti ta\v cna tvr\dj enja
  \begin{enumerate}
    \item Svaki jezik prepoznat deterministi\v ckim kona\v cnim
    automatom je kontekstno slobodan.
    \item Svaki kontekstno slobodan jezik mo\v ze biti prepoznat
    deterministi\v ckim potisnim automatom.
    \item Svaka \textsc{ll} gramatika je i \textsc{lr} gramatika.
    \item Svaki regularni jezik mo\v ze biti prepoznat
    nedeterministi\v ckim kona\v cnim automatom.
    \item Svaka jezik opisan \textsc{ll} gramatikom mo\v ze biti
    opisan regularnim izrazom.
    \item Nijedno od navedenih tvr\dj enja nije ta\v cno.
  \end{enumerate}

  \item Zaokru\v ziti ta\v cna tvr\dj enja:
  \begin{enumerate}
    \item Klasa jezika prihva\' cenih deterministi\v ckim kona\v cnim automatima je
    zatvorena za operaciju skupovne razlike
    \item Klasa kontekstno slobodnih jezika je zatvorena za
    operaciju skupovne unije
    \item Klasa kontekstno slobodnih jezika je zatvorena za
    operaciju skupovnog preseka
    \item Klasa regularnih jezika je zatvorena za operaciju
    Klinijevog zatvorenja.
    \item Klasa kontekstno slobodnih jezika je zatvorena za
    operaciju proizvoda jezika
  \end{enumerate}

  \item Kontekstno slobodnom gramatikom opisati regularni jezik
  $a*bc*$ i dokazati da konstruisana gramatika generi\v se
  upravo dati jezik.

  \item Navesti Klinijevu teoremu.

  \item Ukoliko nedeterministi\v cki ima $n$ stanja broj stanja
  njemu ekvivalentnog minimalnog deterministi\v ckog automata je
  odozgo ograni\v cen brojem \_\_\_\_\_\_\_\_\_.

  \item Ukoliko regularni izraz sadr\v zi $n$ razli\v citih pojavljivanja
  slova azbuke $\Sigma$, Glu\v skovljev automat ima $\_\_\_\_$
  stanja.

  \item Neka je $n$ broj stanja minimalnog deterministi\v ckog
  kona\v cnog automata i $m$ du\v zina niske na ulazu. Vreme
  potrebno da bi se utvrdilo da li niska pripada jeziku automata
  je $O(\_\_\_)$.

  \item Opisati postupak upotpunjavanja deterministi\v ckog kona\v
  cnog automata i dokazati da se tim postupkom dobija automat
  ekvivalentan polaznom.

  \item Navesti lemu o razrastanju za regularne jezike.

  \item Navesti lemu o razrastanju za kontekstno slobodne jezike.

  \item Osloboditi se leve rekurzije iz gramatike
  $A\rightarrow Aa | b$ i to
  \begin{enumerate}
    \item bez uvo\dj enja $\varepsilon$ pravila
    \item sa uvo\dj enjem $\varepsilon$ pravila
  \end{enumerate}

  \item Izvr\v siti levu faktorizaciju gramatike
  $A\rightarrow a\alpha|a\beta|\gamma$

  \item Napisati najlevlje i najde\v snje izvo\dj enje
  niske $aaabbb$ u gramatici $S\rightarrow AB,\ A\rightarrow Aa|\varepsilon,\ B\rightarrow bB|\varepsilon$

  \item Ukloniti nedosti\v zne neterminale iz gramatike
  $S\rightarrow A|a,\ A\rightarrow bC,\ B\rightarrow CA,\ C\rightarrow AC|a$

  \item Ukloniti neproduktivne neterminale iz gramatike
  $S\rightarrow A|B|a,\ A\rightarrow BC,\ B\rightarrow DB|D,\ C\rightarrow
  AC|C,\ D\rightarrow Dd|D$

  \item Zaokru\v ziti ta\v cna tvr\dj enja:
  \begin{enumerate}
    \item Prilikom sintaksne analize navi\v se, na steku se vr\v
    si najlevlje izvo\dj enje niske koja se prihvata.
    \item Svaka \textsc{LR(0)} gramatika je i \textsc{SLR} gramatika.
    \item Svaka \textsc{LR(1)} gramatika je i \textsc{LALR}
    gramatika.
    \item Svaka \textsc{SLR} gramatika je i \textsc{LALR}
    gramtika.
    \item Svaka \textsc{LALR} gramatika je i \textsc{LR(0)}
    gramtika.
  \end{enumerate}

  \item Definisati i dati primer vi\v sezna\v cne gramatike.

  \item Definisati i dati primer gramatike u Greibach normalnoj
  formi.
\end{enumerate}
\end{comment}



\newpage

\begin{center}
\textbf{Prevodioci i interpretatori - januar 2006. - teorijski deo
ispita}
\end{center}
\begin{enumerate}
    \item Ispitati da li su jezici $L_1=(a^2+b^*a^+)^*$ i $L_2=((a^2)^*+b^*a)^*$ jednaki.
Odgovor dokazati.

    \item LL(1) gramatikom opisati niz definicija listi i he\v s tabela u jeziku {\sc perl}.
    Npr.
\begin{verbatim}
        @l = ("Pii", 45, 38.3);
        %a = {"Pera" => 25, "Mika" => 30, "Ana" => 40};
\end{verbatim}
Za konstruisanu gramatiku odrediti skupove izbora i konstruisati
potisni automat
koji tehnikom analize nani\v ze prihvata dati jezik. Za nisku  \verb|%a = {"Pera" => 25, "Ana" => 40};|
odrediti najlevlje izvo\dj enje, nacrtati drvo izvo\dj enja i
prikazati rad automata prilikom njenog prihvatanja.

\item KS gramatikom opisati aritmeti\v cke izraze sa operacijama
\verb"+" i \verb"*" u kojima se ne koriste zagrade. Kreirati SLR
parser za datu gramatiku, opisati ga \textit{action} i
\textit{goto} tablicama i prikazati njegov rad na prihvatanju
niske \verb"2+3*5".
\end{enumerate}

\vspace{1cm}


\begin{center}
\textbf{Prevodioci i interpretatori - januar 2006. - teorijski deo
ispita}
\end{center}
\begin{enumerate}
    \item Ispitati da li su jezici $L_1=(a^2+b^*a^+)^*$ i $L_2=((a^2)^*+b^*a)^*$ jednaki.
Odgovor dokazati.

    \item LL(1) gramatikom opisati niz definicija listi i he\v s tabela u jeziku {\sc perl}.
    Npr.
\begin{verbatim}
        @l = ("Pii", 45, 38.3);
        %a = {"Pera" => 25, "Mika" => 30, "Ana" => 40};
\end{verbatim}
Za konstruisanu gramatiku odrediti skupove izbora i konstruisati
potisni automat
koji tehnikom analize nani\v ze prihvata dati jezik. Za nisku  \verb|%a = {"Pera" => 25, "Ana" => 40};|
odrediti najlevlje izvo\dj enje, nacrtati drvo izvo\dj enja i
prikazati rad automata prilikom njenog prihvatanja.

\item KS gramatikom opisati aritmeti\v cke izraze sa operacijama
\verb"+" i \verb"*" u kojima se ne koriste zagrade. Kreirati SLR
parser za datu gramatiku, opisati ga \textit{action} i
\textit{goto} tablicama i prikazati njegov rad na prihvatanju
niske \verb"2+3*5".
\end{enumerate}

\vspace{1cm}

\begin{center}
\textbf{Prevodioci i interpretatori - januar 2006. - teorijski deo
ispita}
\end{center}
\begin{enumerate}
    \item Ispitati da li su jezici $L_1=(a^2+b^*a^+)^*$ i $L_2=((a^2)^*+b^*a)^*$ jednaki.
Odgovor dokazati.

    \item LL(1) gramatikom opisati niz definicija listi i he\v s tabela u jeziku {\sc perl}.
    Npr.
\begin{verbatim}
        @l = ("Pii", 45, 38.3);
        %a = {"Pera" => 25, "Mika" => 30, "Ana" => 40};
\end{verbatim}
Za konstruisanu gramatiku odrediti skupove izbora i konstruisati
potisni automat
koji tehnikom analize nani\v ze prihvata dati jezik. Za nisku  \verb|%a = {"Pera" => 25, "Ana" => 40};|
odrediti najlevlje izvo\dj enje, nacrtati drvo izvo\dj enja i
prikazati rad automata prilikom njenog prihvatanja.

\item KS gramatikom opisati aritmeti\v cke izraze sa operacijama
\verb"+" i \verb"*" u kojima se ne koriste zagrade. Kreirati SLR
parser za datu gramatiku, opisati ga \textit{action} i
\textit{goto} tablicama i prikazati njegov rad na prihvatanju
niske \verb"2+3*5".
\end{enumerate}

\vspace{1cm}

\begin{center}
\textbf{Prevodioci i interpretatori - januar 2006. - teorijski deo
ispita}
\end{center}
\begin{enumerate}
    \item Ispitati da li su jezici $L_1=(a^2+b^*a^+)^*$ i $L_2=((a^2)^*+b^*a)^*$ jednaki.
Odgovor dokazati.

    \item LL(1) gramatikom opisati niz definicija listi i he\v s tabela u jeziku {\sc perl}.
    Npr.
\begin{verbatim}
        @l = ("Pii", 45, 38.3);
        %a = {"Pera" => 25, "Mika" => 30, "Ana" => 40};
\end{verbatim}
Za konstruisanu gramatiku odrediti skupove izbora i konstruisati
potisni automat
koji tehnikom analize nani\v ze prihvata dati jezik. Za nisku  \verb|%a = {"Pera" => 25, "Ana" => 40};|
odrediti najlevlje izvo\dj enje, nacrtati drvo izvo\dj enja i
prikazati rad automata prilikom njenog prihvatanja.

\item KS gramatikom opisati aritmeti\v cke izraze sa operacijama
\verb"+" i \verb"*" u kojima se ne koriste zagrade. Kreirati SLR
parser za datu gramatiku, opisati ga \textit{action} i
\textit{goto} tablicama i prikazati njegov rad na prihvatanju
niske \verb"2+3*5".
\end{enumerate}

\newpage
\begin{enumerate}

\item[4.] Data je KS gramatika
\begin{eqnarray*}
S &\rightarrow& \verb"if " c \verb" then " S \verb" else " S \\
&|& \verb"while " c \verb" do " S\\
&|& s
\end{eqnarray*}
\begin{enumerate}
    \item Ispitati da li je data gramatika vi\v sezna\v cna.
    Dokazati odgovor.
    \item Ukoliko je gramatika vi\v sezna\v cna navesti
    bar jednu njoj ekvivalentnu nevi\v sezna\v cnu gramatiku.
    \item \v Sta mo\v zete re\' ci o op\v stem algoritmu za ispitivanje da li je
    proizvoljna gramatika vi\v sezna\v cna.
    \item Dokazati da nijedna \textsc{ll(1)} gramatika ne mo\v ze
    biti vi\v sezna\v cna.
\end{enumerate}
\end{enumerate}

\vspace{1.7cm}
\begin{enumerate}

\item[4.] Data je KS gramatika
\begin{eqnarray*}
S &\rightarrow& \verb"if " c \verb" then " S \verb" else " S \\
&|& \verb"while " c \verb" do " S\\
&|& s
\end{eqnarray*}
\begin{enumerate}
    \item Ispitati da li je data gramatika vi\v sezna\v cna.
    Dokazati odgovor.
    \item Ukoliko je gramatika vi\v sezna\v cna navesti
    bar jednu njoj ekvivalentnu nevi\v sezna\v cnu gramatiku.
    \item \v Sta mo\v zete re\' ci o op\v stem algoritmu za ispitivanje da li je
    proizvoljna gramatika vi\v sezna\v cna.
    \item Dokazati da nijedna \textsc{ll(1)} gramatika ne mo\v ze
    biti vi\v sezna\v cna.
\end{enumerate}
\end{enumerate}


\vspace{1.7cm}
\begin{enumerate}

\item[4.] Data je KS gramatika
\begin{eqnarray*}
S &\rightarrow& \verb"if " c \verb" then " S \verb" else " S \\
&|& \verb"while " c \verb" do " S\\
&|& s
\end{eqnarray*}
\begin{enumerate}
    \item Ispitati da li je data gramatika vi\v sezna\v cna.
    Dokazati odgovor.
    \item Ukoliko je gramatika vi\v sezna\v cna navesti
    bar jednu njoj ekvivalentnu nevi\v sezna\v cnu gramatiku.
    \item \v Sta mo\v zete re\' ci o op\v stem algoritmu za ispitivanje da li je
    proizvoljna gramatika vi\v sezna\v cna.
    \item Dokazati da nijedna \textsc{ll(1)} gramatika ne mo\v ze
    biti vi\v sezna\v cna.
\end{enumerate}
\end{enumerate}

\vspace{1.7cm}
\begin{enumerate}

\item[4.] Data je KS gramatika
\begin{eqnarray*}
S &\rightarrow& \verb"if " c \verb" then " S \verb" else " S \\
&|& \verb"while " c \verb" do " S\\
&|& s
\end{eqnarray*}
\begin{enumerate}
    \item Ispitati da li je data gramatika vi\v sezna\v cna.
    Dokazati odgovor.
    \item Ukoliko je gramatika vi\v sezna\v cna navesti
    bar jednu njoj ekvivalentnu nevi\v sezna\v cnu gramatiku.
    \item \v Sta mo\v zete re\' ci o op\v stem algoritmu za ispitivanje da li je
    proizvoljna gramatika vi\v sezna\v cna.
    \item Dokazati da nijedna \textsc{ll(1)} gramatika ne mo\v ze
    biti vi\v sezna\v cna.
\end{enumerate}
\end{enumerate}

\newpage
\begin{center}
\textbf{Prevodioci i interpretatori - januar 2006. - prakti\v cni deo
ispita}
\end{center}

\begin{enumerate}
\item Kori\v s\' cenjem jezika \textsc{perl} napisati konverter
ispravno zapisanih \textsc{html} datoteka u pregledan, tekstualni
format. Konverter treba da obradi slede\' ce etikete:
\begin{enumerate}

\item \verb"<img>" se zamenjuje imenom slike izme\dj u viti\v castih zagrada. Npr.
\verb|<img src="slika.jpg" width="300">| se zamenjuje sa \verb"{slika.jpg}"

\item \verb"<a>" linkovi se zamenjuju sa adresom na koju ukazuju izme\dj u uglastih zagrada
Npr. \verb|<a href="http://www.google.com">| se zamenjuje sa \verb|[http://www.google.com]|

\item \verb"<h1>" naslovi se ispisuju se sa po jednim
razmakom izme\dj u svakog slova i po jednim praznim redom ispred i iza
(npr. naslov \verb"<h1>OVO JE NASLOV</h2>"
se prevodi u \verb"O V O   J E   N A S L O V")

\item \verb"<h2>" do \verb"<h6>" naslovi se ispisuju sa po jednim praznim redom ispred i iza.

\item \verb"<p>" se zamenjuje jednim praznim redom
\item \verb"<br>" se zamenjuje prelaskom u novi red

\item \verb"<ol>" nabrajanja se zamenjuju brojevima. Npr.
\begin{verbatim}
  <ol><li>Prva stavka<li>Druga<li>Treca</ol>
\end{verbatim}
se prikazuje kao
\begin{verbatim}
1. Prva stavka
2. Druga
3. Treca
\end{verbatim}
Liste mogu biti ugnje\v z\dj ene.
\end{enumerate}

Sve vi\v sestruke beline se zamenjuju jednostrukim, prelasci u novi red se ignori\v su, a tekst
se formatira tako da svaki red zauzima najvi\v se 80 karaktera. \hfill[20]
\end{enumerate}

\vspace{1.5cm}
\begin{center}
\textbf{Prevodioci i interpretatori - januar 2006. - prakti\v cni deo
ispita}
\end{center}

\begin{enumerate}
\item Kori\v s\' cenjem jezika \textsc{perl} napisati konverter
ispravno zapisanih \textsc{html} datoteka u pregledan, tekstualni
format. Konverter treba da obradi slede\' ce etikete:
\begin{enumerate}

\item \verb"<img>" se zamenjuje imenom slike izme\dj u viti\v castih zagrada. Npr.
\verb|<img src="slika.jpg" width="300">| se zamenjuje sa \verb"{slika.jpg}"

\item \verb"<a>" linkovi se zamenjuju sa adresom na koju ukazuju izme\dj u uglastih zagrada
Npr. \verb|<a href="http://www.google.com">| se zamenjuje sa \verb|[http://www.google.com]|

\item \verb"<h1>" naslovi se ispisuju se sa po jednim
razmakom izme\dj u svakog slova i po jednim praznim redom ispred i iza
(npr. naslov \verb"<h1>OVO JE NASLOV</h2>"
se prevodi u \verb"O V O   J E   N A S L O V")

\item \verb"<h2>" do \verb"<h6>" naslovi se ispisuju sa po jednim praznim redom ispred i iza.

\item \verb"<p>" se zamenjuje jednim praznim redom
\item \verb"<br>" se zamenjuje prelaskom u novi red

\item \verb"<ol>" nabrajanja se zamenjuju brojevima. Npr.
\begin{verbatim}
  <ol><li>Prva stavka<li>Druga<li>Treca</ol>
\end{verbatim}
se prikazuje kao
\begin{verbatim}
1. Prva stavka
2. Druga
3. Treca
\end{verbatim}
Liste mogu biti ugnje\v z\dj ene.
\end{enumerate}

Sve vi\v sestruke beline se zamenjuju jednostrukim, prelasci u novi red se ignori\v su, a tekst
se formatira tako da svaki red zauzima najvi\v se 80 karaktera. \hfill[20]
\end{enumerate}


\newpage
\begin{enumerate}
\item[2.] Datoteka sadr\v zi niz regularnih definicija. Svaka regularna definicija je oblika
\verb"id = regex", gde u izgradnji regularnog izraza mogu u\v cestvovati karakteri, klase karaktera,
prethodno definisani regularni izrazi i operacije \verb"|", \verb"*", \verb"+", \verb"?". Prilikom
izgradnje regularnog izraza mogu\' ce je koristiti operator \verb"basic_regex" kojom se dati regularni
izraz prevodi u osnovni, odnosno osloba\dj a karakterskih klasa i operatora \verb"+" i \verb"?". Funkcijom
\verb"print" vr\v si se ispisivanje datog regularnog izraza. Npr.
\begin{verbatim}
DIGIT = [0-9];
NUM = {DIGIT}?.{DIGIT};
print({NUM});                          [0-9]?.[0-9]
HEX = 0x({DIGIT}|[A-F])+;
DIGIT = [0-1];
print({HEX});                          0x([0-9]|[A-F])+
BIN = basic_regex({DIGIT}+);
print({BIN});                          (0|1)(0|1)*
\end{verbatim}
\begin{enumerate}
  \item Kreirati leksi\v cki analizator i gramatikom opisati opisani oblik datoteka.\hfill[5]
  \item Napisati hijerarhiju klasa (C++) ili strukturu (C) za predstavljanje regularnih izraza u obliku stabla.\hfill[12]
  \item Definisati i implementirati funkcije za ispis regularnog izraza.\hfill[3]
  \item Definisati tablicu simbola u kojoj se \v cuvaju regularne definicije.\hfill[3]
  \item Definisati funkcije za prevo\dj enje regularnih izraza u osnovne.\hfill[7]
\end{enumerate}

\end{enumerate}

\vspace{6cm}
\begin{enumerate}
\item[2.] Datoteka sadr\v zi niz regularnih definicija. Svaka regularna definicija je oblika
\verb"id = regex", gde u izgradnji regularnog izraza mogu u\v cestvovati karakteri, klase karaktera,
prethodno definisani regularni izrazi i operacije \verb"|", \verb"*", \verb"+", \verb"?". Prilikom
izgradnje regularnog izraza mogu\' ce je koristiti operator \verb"basic_regex" kojom se dati regularni
izraz prevodi u osnovni, odnosno osloba\dj a karakterskih klasa i operatora \verb"+" i \verb"?". Funkcijom
\verb"print" vr\v si se ispisivanje datog regularnog izraza. Npr.
\begin{verbatim}
DIGIT = [0-9];
NUM = {DIGIT}?.{DIGIT};
print({NUM});                          [0-9]?.[0-9]
HEX = 0x({DIGIT}|[A-F])+;
DIGIT = [0-1];
print({HEX});                          0x([0-9]|[A-F])+
BIN = basic_regex({DIGIT}+);
print({BIN});                          (0|1)(0|1)*
\end{verbatim}
\begin{enumerate}
  \item Kreirati leksi\v cki analizator i gramatikom opisati opisani oblik datoteka.\hfill[5]
  \item Napisati hijerarhiju klasa (C++) ili strukturu (C) za predstavljanje regularnih izraza u obliku stabla.\hfill[12]
  \item Definisati i implementirati funkcije za ispis regularnog izraza.\hfill[3]
  \item Definisati tablicu simbola u kojoj se \v cuvaju regularne definicije.\hfill[3]
  \item Definisati funkcije za prevo\dj enje regularnih izraza u osnovne.\hfill[7]
\end{enumerate}

\end{enumerate}

\end{small}
\end{document}
