\documentclass[a4paper]{article}
\textwidth 19cm \textheight 26cm \topmargin -3cm
\parindent 0.46in
\headsep 0.2in \oddsidemargin -2.5cm \evensidemargin 0cm
\hoffset0.8cm \voffset 1.8cm \pagestyle{empty}



\begin{document}

\begin{center}
\textbf{Prevodioci i interpretatori - septembar 2003. - predlog
zadataka}
\end{center}

\begin{enumerate}
\item Data je azbuka $\Sigma=\{0,1\}$. Odrediti sve re\v ci $x\in
\Sigma^*$ za koje va\v zi
$$
0x=x0
$$

\item Kona\v cnim automatom i regularnim izrazom opisati skup re\v ci iz $\{0,1\}^*$
takve da im $101$ nije podre\v c. Ukoliko konstruisani automat
nije minimalni deterministi\v cki, minimizovati ga i
determinizovati.
\item
Dokazati ili opovrgunti:
\begin{itemize}
\item Klasa regularnih jezika je zatvorena u odnosu na operaciju
simetri\v cne razlike.
\item Klasa kontekst slobodnih jezika je zatvorena u odnosu na
operaciju preseka.
\end{itemize}
\item Napisati program koriste\' ci Lex koji za uneti rimski broj
proverava da li je ispravan i ako jeste ispisuje njegovu vrednost.

\item Sastaviti LL(1) gramatiku za jezik aritmeti\v ckih izraza
nad azbukom $\{(,),[,],+,-,*,/,^,a,b\}$ pri \v cemu se obi\v ce
koriste za zagradjivanje izraza bez zagrada, dok se uglaste
zagrada koriste za zagradjivanje izraza koji ve\' c u sebi sadr\v
ze neke zagrade. Za ovako napravljenu gramatiku odrediti skupove
izbora i na osnovu njih u programskom jeziku C skicirati
implementaciju potisnog automata koji za uneti izraz ispituje da
li pripada jeziku ove gramatike.

\item Gramatiku
\begin{eqnarray*}
S\rightarrow Ba | Ab\\
A\rightarrow Sa|AAb|a\\
B\rightarrow Sb|BBa|b
\end{eqnarray*}

prevesti u Greibach normalnu formu

\item Napisati program koji aritmeti\v cki izraz koji se unosi sa ulaza prevodi u tzv. MathML
notaciju, na slede\' ci na\v cin. Oznake svih promenjivih  (u
obzir uzeti samo jednoslovne promenjive) koje se javljaju u izrazu
se pi\v su unutar \verb"<mi>" etiketa. Oznake svih brojeva se pi\v
su unutar \verb"<mn>" etiketa. Oznake aritmeti\v ckih operacija +,
- i * se pi\v su unutar \verb"<mo>" etiketa. Svaki izraz koji se
pojavi u zagradama se stavlja unutar \verb"<mfenced>" etiketa.
Ukoliko se naidje na operaciju deljenja ona se obradjuje tako \v
sto se unutar etiketa \verb"<mfrac>"  navedu deljenik i delilac.
Svi izrazi koji se prilikom uobi\v cajenog na\v cina ispisa pisali
u jedom redu se stavljaju unutar \verb"<mrow>" etiketa (to su
izrazi koji sadr\v ze niz operacija sabiranja, oduzimanja i mno\v
zenja). Npr. izraz \verb"(x+y/5-4)/20+2" je potrebno prevesti u
\begin{verbatim}
<mrow>
   <mfrac>
      <mfenced>
          <mrow>
            <mi>x</mi>
            <mo>+</mo>
            <mfrac>
               <mi>y</mi>
               <mn>5</mn>
            </mfrac>
            <mo>-</mo>
            <mn>4</mn>
          </mrow>
      </mfenced>
      <mn>20</mn>
   </mfrac>
   <mo>+</mo>
   <mn>2</mn>
</mrow>
\end{verbatim}
Poku\v sajte da ispo\v stujete na\v cin nazubljivanja ispisa koji
je dat u primeru.

\item Pretpostavimo da \verb"main()" funkcija programa napisana na jeziku
C++ koristi klasu \verb"String". Funkcija po\v cinje nizom deklaracija
promenjivih za kojim sledi niz izraza nad tim promenjivim. Klasa \verb"String"
ima konstruktor na osnovu jednog argumenta tipa \verb"char*", destruktor, zatim operatore
\verb"+", i \verb"+=" za konkatenaciju i funkciju size() koja vra\' ca veli\v cinu
stringa.
Napraviti program koji \' ce da prepi\v se taj main tako da se umesto klase
 \verb"String" radi samo sa niskama karaktera i pokaziva\v cima na njih. Npr.

\begin{verbatim}
main()                           main()
{   int a;                       {    int a;
    float b;                          float b;
    String c("Niska"),d;              char *c="Niska", *d=NULL;
    String e;                         char *e=NULL;

    c+="Cao";                         char *tmp;
                                      tmp=new char[strlen(c)+3+1];
                                      strcpy(tmp,c);
                                      strcpy(tmp+strlen(c),"Cao");
                                      if (c) delete [] c;
                                      c=tmp;

    a++;                              a++;

    d=c;                              tmp=new char[strlen(c)+1];
                                      strcpy(tmp,c);
                                      if (d) delete[] d;
                                      d=tmp;

    e=d+"Ahoj";                       tmp=new char[strlen(d)+4+1];
                                      strcpy(tmp,d);
                                      strcpy(tmp+strlen(d),"Ahoj");
                                      if (e) delete[] e;
                                      e=tmp;

                                      if (c) delete []c;
                                      if (d) delete []d;
                                      if (e) delete []e;
}

\end{verbatim}

Na\v cin prevodjenja odredite sami i poku\v sajte da pri tome vodite ra\v cuna o optimalnosti.

\end{enumerate}

\end{document}
