\documentclass[a4paper]{article}
\setlength{\oddsidemargin}{-1cm} \setlength{\textwidth}{17cm}
\setlength{\textheight}{23cm} \setlength{\topmargin}{-2cm}
\pagestyle{empty}
\begin{document}
{\small

\begin{center}
{\bf Prevodioci i interpretatori - Jun 2006. - teorijski deo}
\end{center}
\begin{enumerate}
    \item Dokazati ili opovrgnuti:
    \begin{enumerate}
        \item Klasa regularnih jezika je zatvorena za operaciju
        simetri\v cne razlike.
        \item Klasa kontekstno slobodnih jezika je zatvorena za
        operaciju unije.
        \item Klasa kontekstno slobodnih jezika je zatvorena za
        operaciju preseka.
        \item $\{a^nb^n, n\geq 2006\}$ je regularan.\hfill[4+4+4+4]
    \end{enumerate}

    \item LL(1) gramatikom opisati aritmeti\v cke izraze sa
    operacijama sabiranja i mno\v zenja celih brojeva. Npr.
    \verb"(2+3)*5". Odrediti skupove izbora. Gramatiku
    pro\v siriti atributima i akcijama kojima se izra\v cunava
    vrednost izraza, pri \v cemu su obe operacije \textit{levo}
    asocijativne. \hfill[5+12]

    \item Kontekstno slobodnom gramatikom opisati osnovne
    regularne izraze nad azbukom $\Sigma=\{a, b\}$ u kojima
    se ne koriste zagrade. Konstruisati
    zatim SLR(1) automat za datu gramatiku i predstaviti ga action i
    goto tablicama. Prikazati rad parsera na prihvatanju niske
    \verb"ba|b*". \hfill[3+9+5]

\end{enumerate}


\begin{center}
{\bf Prevodioci i interpretatori - Jun 2006. - teorijski deo}
\end{center}
\begin{enumerate}
    \item Dokazati ili opovrgnuti:
    \begin{enumerate}
        \item Klasa regularnih jezika je zatvorena za operaciju
        simetri\v cne razlike.
        \item Klasa kontekstno slobodnih jezika je zatvorena za
        operaciju unije.
        \item Klasa kontekstno slobodnih jezika je zatvorena za
        operaciju preseka.
        \item $\{a^nb^n, n\geq 2006\}$ je regularan.\hfill[4+4+4+4]
    \end{enumerate}

    \item LL(1) gramatikom opisati aritmeti\v cke izraze sa
    operacijama sabiranja i mno\v zenja celih brojeva. Npr.
    \verb"(2+3)*5". Odrediti skupove izbora. Gramatiku
    pro\v siriti atributima i akcijama kojima se izra\v cunava
    vrednost izraza, pri \v cemu su obe operacije \textit{levo}
    asocijativne. \hfill[5+12]

    \item Kontekstno slobodnom gramatikom opisati osnovne
    regularne izraze nad azbukom $\Sigma=\{a, b\}$ u kojima
    se ne koriste zagrade. Konstruisati
    zatim SLR(1) automat za datu gramatiku i predstaviti ga action i
    goto tablicama. Prikazati rad parsera na prihvatanju niske
    \verb"ba|b*". \hfill[3+9+5]

\end{enumerate}


\begin{center}
{\bf Prevodioci i interpretatori - Jun 2006. - teorijski deo}
\end{center}
\begin{enumerate}
    \item Dokazati ili opovrgnuti:
    \begin{enumerate}
        \item Klasa regularnih jezika je zatvorena za operaciju
        simetri\v cne razlike.
        \item Klasa kontekstno slobodnih jezika je zatvorena za
        operaciju unije.
        \item Klasa kontekstno slobodnih jezika je zatvorena za
        operaciju preseka.
        \item $\{a^nb^n, n\geq 2006\}$ je regularan.\hfill[4+4+4+4]
    \end{enumerate}

    \item LL(1) gramatikom opisati aritmeti\v cke izraze sa
    operacijama sabiranja i mno\v zenja celih brojeva. Npr.
    \verb"(2+3)*5". Odrediti skupove izbora. Gramatiku
    pro\v siriti atributima i akcijama kojima se izra\v cunava
    vrednost izraza, pri \v cemu su obe operacije \textit{levo}
    asocijativne. \hfill[5+12]

    \item Kontekstno slobodnom gramatikom opisati osnovne
    regularne izraze nad azbukom $\Sigma=\{a, b\}$ u kojima
    se ne koriste zagrade. Konstruisati
    zatim SLR(1) automat za datu gramatiku i predstaviti ga action i
    goto tablicama. Prikazati rad parsera na prihvatanju niske
    \verb"ba|b*". \hfill[3+9+5]

\end{enumerate}


\begin{center}
{\bf Prevodioci i interpretatori - Jun 2006. - teorijski deo}
\end{center}
\begin{enumerate}
    \item Dokazati ili opovrgnuti:
    \begin{enumerate}
        \item Klasa regularnih jezika je zatvorena za operaciju
        simetri\v cne razlike.
        \item Klasa kontekstno slobodnih jezika je zatvorena za
        operaciju unije.
        \item Klasa kontekstno slobodnih jezika je zatvorena za
        operaciju preseka.
        \item $\{a^nb^n, n\geq 2006\}$ je regularan.\hfill[4+4+4+4]
    \end{enumerate}

    \item LL(1) gramatikom opisati aritmeti\v cke izraze sa
    operacijama sabiranja i mno\v zenja celih brojeva. Npr.
    \verb"(2+3)*5". Odrediti skupove izbora. Gramatiku
    pro\v siriti atributima i akcijama kojima se izra\v cunava
    vrednost izraza, pri \v cemu su obe operacije \textit{levo}
    asocijativne. \hfill[5+12]

    \item Kontekstno slobodnom gramatikom opisati osnovne
    regularne izraze nad azbukom $\Sigma=\{a, b\}$ u kojima
    se ne koriste zagrade. Konstruisati
    zatim SLR(1) automat za datu gramatiku i predstaviti ga action i
    goto tablicama. Prikazati rad parsera na prihvatanju niske
    \verb"ba|b*". \hfill[3+9+5]

\end{enumerate}


\end{document}

%r' -> regex

%regex -> regex | rdisj          1
%    |    rdisj                  2

%rdisj -> rdisj rstar            3
%    |    rstar                  4
%
%rstar -> relem *                5
%    | relem                     6
%
%relem -> a                      7
%     | b
%
%        first    follow
%regex   a        EOI, |
%rdisj   a        EOI, |, a
%rstar   a        EOI, |, a
%relem   a        EOI, |, a, *
%
%
%0: r' -> . regex
%   regex -> .regex | rdisj
%   regex -> .rdisj
%   rdisj -> .rdisj rstar
%   rdisj -> .rstar
%   rstar -> .relem *
%   rstar -> .relem
%   relem -> .a
%
%   regex 1
%   rdisj 2
%   rstar 3
%   relem 4
%   a 5
%
%
%1:
%   r' ->  regex .
%   regex -> regex .| rdisj
%
%   | 6
%
%2:
%   regex -> rdisj .
%   rdisj -> rdisj .rstar
%   rstar -> .relem *
%   rstar -> .relem
%   relem -> .a
%
%   rstar 7
%   relem 4
%   a 5
%
%3:
%   rdisj -> rstar.
%
%4:
%   rstar -> relem. *
%   rstar -> relem.
%
%* 8
%
%5:
%   relem -> a.
%6:
%   regex -> regex | .rdisj
%   rdisj -> .rdisj rstar
%   rdisj -> .rstar
%   rstar -> .relem *
%   rstar -> .relem
%   relem -> .a
%
%   rdisj 9
%   rstar 3
%   relem 4
%   a 5
%
%7:
%   rdisj -> rdisj rstar.
%
%8:
%   rstar -> relem *.
%
%9:
%   regex -> regex | rdisj.
%   rdisj -> rdisj . rstar
%   rstar -> .relem *
%   rstar -> .relem
%   relem -> .a
%
%   rstar 3
%   relem 4
%   a 5
%
%    a     |      *    EOI   regex     rdisj      rstar     relem
%0  s5                         1         2          3         4
%1         s6          acc
%2  s5     r2          r2                           7         4
%3  r4     r4          r4
%4  r6     r6     s8   r6
%5  r7     r7     r7   r7
%6  s5                                   9           3        4
%7  r3     r3          r3
%8  r5     r5          r5
%9  s5     r1          r1                            3        4
%
%
%0                   aa|a*
%0a5                 a|a*
%0relem4             a|a*
%0rstar3             a|a*
%0rdisj2             a|a*
%0rdisj2a5           |a*
%0rdisj2relem4       |a*
%0rdisj2rstar7       |a*
%0rdisj2             |a*
%0regex1             |a*
%0regex1|6           a*
%0regex1|6a5         *
%0regex1|6relem4     *
%0regex1|6relem4*8
%0regex1|6rstar3
%0regex1|6rdisj9
%0regex1
%
%E -> T {E'.i = T.v} E' {E.v = E'.v}
%E1' -> + T {E2'.i = E1'.i + T.v} E2' {E1'.v = E2'.v}
%    | eps {E1'.v = E1'.i}
%
%T -> F {T'.i = F.v} T' {T.v = T'.v}
%T1' -> * F {T2'.i = T1'.i * F.v} T2' {T1'.v = T2'.v}
%    | eps {T1'.v = T1'.i}
%F -> (E)    {F.v = E.v}
%    | a     {F.v = a.v}
