\documentclass[a4paper,twoside]{article}
\usepackage{pst-all}
\usepackage{amsfonts}
\begin{document}
\begin{center}
\Large\bf Decembar 2002.
\end{center}

1. a) Konstrui\v simo automat u kome \' ce svako od stanja da ima
slede\' cu interpretaciju :

Neka je $n$ broj nula u dosada prepoznatom delu niske.

\indent $A$ - n je deljiv sa 3

\indent $B$ - ostatak pri deljenju n sa 3 je 1

\indent $C$ - ostatak pri deljenju n sa 3 je 2

Po\v cetno stanje automata je $A$ zato \v sto prazna niska ne
sadr\v zi nijednu nulu. Ako je slede\' ci simbol $1$, stanje se ne
menja. Ako je, pak, slede\' ci simbol $0$ prelazi se u stanje koje
je slede\' ce po modulu 3. Zavr\v sno stanje je $A$. Dakle tra\v
zeni automat je : \vspace{1cm}
$$
\psmatrix[mnode=circle,colsep=1] [mnode=p]&[doubleline=true]A&B&C
\endpsmatrix
\psset{shortput=nab,arrows=->,labelsep=3pt} \small
\nccircle[nodesep=3pt]{->}{1,2}{.4cm}_{1}
\nccircle[nodesep=3pt]{->}{1,3}{.4cm}_{1}
\nccircle[nodesep=3pt]{->}{1,4}{.4cm}_{1}
\ncline{1,1}{1,2}
\ncline{1,2}{1,3}^{0} \ncline{1,3}{1,4}^{0}
\ncarc[arcangle=35]{1,4}{1,2}^{0}
$$
\vspace{1cm}

b)Ve\' cina automata u kojima se zahteva ispitivanje deljivosti
nekim brojem se kontrui\v se na prili\v cno sli\v can na\v cin.
Neka dakle konstrui\v semo automat koji odredjuje deljivost brojem
$n$, broja zapisanog u osnovi $m$.  Ideja je da nekako simuliramo
algoritam deljenja. Svako stanje automata \' ce da predstavlja
jedan od mogu\' cih ostataka pri deljenju sa brojem $n$. Stanja
automata su, dakle, $0$,$1$,\ldots,$n-1$. Konstrukcija se zasniva
na \v cinjenici da se samo na osnovu ostatka pri deljenju broja
zapisanog sa prvih $k$ cifara na\v seg broja sa $n$ i na osnovu
$k+1$-ve cifre mo\v zeo odrediti ostatak pri deljenju broja
zapisanog sa prvih $k+1$ cifara na\v seg broja brojem $n$. Zaista,
"spu\v stanje" $k+1$-ve cifre predstavlja mno\v zenje dosada\v
snjeg ostatka brojem $m$ i zatim dodavanjem $k+1$ cifre. Novi
ostatak je ostatak pri deljenju tako dobijenog broja brojem $n$.
Po\v cetno stanje je nula, jer na po\v cetku pretpostavljamo da
nema nikakvog ostatka. Na osnovu re\v cenog mo\v zemo konstruisati
automat:
\vspace{1cm}
$$
\psmatrix[mnode=circle,colsep=1]
[mnode=p]&[doubleline=true]0&1&2
\endpsmatrix
\psset{shortput=nab,arrows=->,labelsep=3pt} \small
\nccircle[nodesep=3pt]{->}{1,2}{.4cm}_{0}
\nccircle[nodesep=3pt]{->}{1,4}{.4cm}_{1}
\ncline{1,1}{1,2}
\ncarc[arcangle=35]{1,2}{1,3}^{1}
\ncarc[arcangle=35]{1,3}{1,4}^{0}
\ncarc[arcangle=35]{1,3}{1,2}^{1}
\ncarc[arcangle=35]{1,4}{1,3}^{0}
$$

\vspace{1cm} c)Po\v sto ova dva automata predstavljaju presek i
razliku prethodna dva automata koji su imali svojstvo da su
deterministi\v cki, potpuni automati, mo\v zemo ih konstruisati
standardnim postupkom za konstrukciju preseka i razlike. Ideja se
zasniva na simuliranju istovremenog rada dva automata. Dakle
konstrui\v semo automat \v ciji skup stanja se sastoji od
proizvoda skupova stanja prethodna dva automata. Stanje
$(q_1,q_2)$ ima interpretaciju da bi prilikom prepoznavanja niske
prvi automat bio u stanju $q1$, a drugi u stanju $q2$. Konstrui\v
simo taj automat:

\vspace{1cm}
$$
\psmatrix[mnode=circle,colsep=1]
[mnode=p]&(A,0)&(A,1)&(A,2)\\
&(B,0)&(B,1)&(B,2)\\
&(C,0)&(C,1)&(C,2)\\
\endpsmatrix
\psset{shortput=nab,arrows=->,labelsep=3pt} \small
\nccircle[nodesep=3pt]{->}{1,4}{.6cm}_{1}
\nccircle[nodesep=3pt]{->}{2,4}{.6cm}_{1}
\nccircle[nodesep=3pt]{->}{3,4}{.6cm}_{1}
\ncline{1,1}{1,2}
\ncline{1,2}{2,2}^{0}
\ncline{2,2}{3,2}^{0}
\ncline{1,3}{2,4}^[npos=0.2]{0}
\ncline{2,3}{3,4}_[npos=0.2]{0}
\ncline{1,4}{2,3}_[npos=0.2]{0}
\ncline{2,4}{3,3}^[npos=0.2]{0}
\ncarc[arcangle=20]{1,2}{1,3}^{1}
\ncarc[arcangle=20]{1,3}{1,2}^{1}
\ncarc[arcangle=20]{2,2}{2,3}^{1}
\ncarc[arcangle=20]{2,3}{2,2}^{1}
\ncarc[arcangle=20]{3,2}{3,3}^{1}
\ncarc[arcangle=20]{3,3}{3,2}^{1}
\ncarc[arcangle=30]{3,2}{1,2}^{0}
\ncangles[angleA=180,angleB=-90,armA=0.2cm,armB=0.2cm]{3,3}{1,4}^[npos=1.3]{0}
\ncangles[angleA=0,angleB=-90,armA=0.2cm,armB=0.3cm]{3,4}{1,3}_[npos=1.3]{0}
$$
\vspace{1cm}

Sada odredimo zavr\v sna stanja na osnovu uslova zadatka. U delu
pod i) je potrebno da prvi automat ne prepoznaje nisku, dok je
drugi prepoznaje. Dakle zavr\v sna stanja su $(B,0)$ i $(C,0)$. U
delu pod ii) je potrebno da oba automata prepoznaju nisku tako da
je jedino zavr\v sno stanje $(A,0)$. \hfill $\Box$

\vspace{1cm}

3. Imaju\' ci u vidu slede\' ce jednakosti, do re\v senja se veoma
lako dolazi :
$$
a^+=aa^*
$$
$$
a?=a|\varepsilon
$$
gde je a proizvoljni regularni izraz.

Karakterske klase se zamenjuju disjunkcijom karaktera \v clanova.
Npr.
$$
 [a-c]=a|b|c
$$

Gramatika regularnih izraza je prili\v cno uobi\v cajena:

\begin{verbatim}
        ri      :   ri BAR riili
                |   riili
                ;

        riili   :   riili riputa
                |   riputa
                ;

        riputa  :   ( ri )
                |   riputa ?
                |   riputa +
                |   riputa *
                |   [slovo-slovo]
                |   slovo
                ;
\end{verbatim}

Faza leksi\v cke analize je jako jednostavna, imaju\' ci u vidu
azbuku nad kojom su definisani regularni izrazi. Leksi\v cki
analizator je dat u datoteci \textbf{decembar2002.lex}.

\begin{verbatim}
%option noyywrap

%{
#include "y.tab.h"
%}

%%
[a-z0-9_]   return SLOVO;
"("     return LOZ;
")"     return DOZ;
"["     return LUZ;
"]"     return DUZ;
"?"     return UPITNIK;
"*"     return ZVEZDA;
"-"     return CRTICA;
"+"     return PLUS;
"|"     return BAR;

.       printf("Nedozvoljen karakter : %s\n",yytext);
%%
\end{verbatim}

Prevodjenje vr\v simo koriste\' ci YACC-ov interni stek. Va\v zno
je da naglasimo da \' ce se na steku \v cuvati niske karaktera
(tj. pokaziva\v ci na njih). Kada se, prilikom prevodjenja, naidje
na slovo azbuke ono se stavlja na stek. Zatim se u skladu sa
primenjenim gramati\v ckim pravilima, i koriste\' ci jednakosti sa
po\v cetka teksta, vrednosti sa vrha steka zamenjuju odgovaraju\'
cim zamenama. Proizvod regularnih izraza $a$ i $b$ se zamenjuje sa
$ab$, zatim se regularni izraz $a^+$ menja sa $aa^*$, $a^*$ ostaje
$a^*$, $a?$ se menja sa $a|\varepsilon$ i sli\v cno. Kada se
izvr\v si redukcija celog regularnog izraza, \v stampa se vrednost
sa vrha steka.

Kod je prilo\v zen u datoteci \textbf{decembar2002.y}

\begin{verbatim}
%{
#define yyerror printf
extern char* yytext;
#define YYSTYPE char*
#include <string.h>
%}

%left BAR
%token LOZ DOZ LUZ DUZ SLOVO UPITNIK ZVEZDA CRTICA PLUS
%start poc

%%
poc     :       ri       {  printf("Neprosireni regularni
                                    izraz je :\n%s\n",$1);
                            free($1);
                         }

ri  :   ri BAR riili     {  $$=ili($1,$3);
                            free($1); free($2);
                         }
        |   riili        {  $$=$1; }
        ;

riili   :   riili riputa {  $$=puta($1,$2);
                            free($1); free($2); }
        |   riputa       {  $$=$1; }
        ;

riputa  :   LOZ ri DOZ     {  $$=zagradi($2);
                              free($2);
                           }
        |   riputa UPITNIK {  $$=upitnik($1);
                              free($1);
                           }
        |   riputa PLUS    {  $$=plus($1);
                              free($1);
                           }
        |   riputa ZVEZDA  {  $$=zvezda($1);
                              free($1);
                           }
        |   LUZ slovo CRTICA slovo DUZ
                           {  $$=klasa($2[0],$4[0]);
                              free($2); free($4);
                           }
        |   slovo          {  $$=$1; }
        ;

slovo   :       SLOVO      { $$=strdup(yytext); }

%%

char* zagradi(char* s)
{   char* r=(char *)malloc(strlen(s)+3);
    sprintf(r,"(%s)",s);
    return r;
}

char* ili(char* s, char* t)
{   char* r=(char *)malloc(strlen(s)+strlen(t)+2);
    sprintf(r,"%s|%s",s,t);
    return r;
}

char* puta(char* s, char *t)
{   char* r=(char *)malloc(strlen(s)+strlen(t)+1);
    sprintf(r,"%s%s",s,t);
    return r;
}


char* upitnik(char* s)
{   char* r=(char *)malloc(strlen(s)+7);
    sprintf(r,"(%s|eps)",s);
    return r;
}

char* plus(char* s)
{   char* r=(char *)malloc(2*strlen(s)+4);
    sprintf(r,"%s(%s)*",s,s);
    return r;
}

char* zvezda(char* s)
{   char* r=(char *)malloc(strlen(s)+2);
    sprintf(r,"%s*",s);
    return r;
}

char* klasa(char a, char b)
{   char* r;
    char c;
    if (b>=a)
    {   r=(char *)malloc(2*(b-a)+4);
        r[0]='(';
        for (c=a; c<=b; c++)
        {   r[2*(c-a)+1]=c;
            r[2*(c-a)+2]='|';
        }
        r[2*(b-a)+2]=')';
        r[2*(b-a)+3]='\0';
    }
    else
    {  r=(char *)malloc(1);
       r[0]='\0';
    }
    return r;
}

main()
{ yyparse();
}
\end{verbatim}

\end{document}
