Q4.tex

%نام و نام خانوادگی:
%شماره دانشجویی: 
\مسئله{نام سؤال}

\پاسخ{}

قسمت الف:


\begin{latin}
    \begin{tikzpicture}
        [>=latex, 
        node distance=2.5cm, 
        block/.style={state, rectangle, text width=8em}
        ]
        \node [block, label=above left: 0] (q0) 
        {
            \(S \rightarrow .R \hfill \$\)
            \\
            \(R \rightarrow .RR \hfill \$a(|* \)
            \\
            \(R \rightarrow .R|R \hfill \$a(|* \)
            \\
            \(R \rightarrow .R* \hfill \$a(|* \)
            \\
            \(R \rightarrow . \hfill \$a(|* \)
            \\
            \(R \rightarrow .a \hfill \$a(|* \)
            \\
            \(R \rightarrow .(R) \hfill \$a(|* \)
            \\
        };

        \node [block, label=above left: 1] (q1) [right=1cm of q0]
        {
            \(S \rightarrow R. \hfill \$\)
            \\
            \(R \rightarrow R.R \hfill \$a(|* \)
            \\
            \(R \rightarrow R.|R \hfill \$a(|* \)
            \\
            \(R \rightarrow R.* \hfill \$a(|* \)
            \\
            \(R \rightarrow .RR \hfill \$a(|* \)
            \\
            \(R \rightarrow .R|R \hfill \$a(|* \)
            \\
            \(R \rightarrow .R* \hfill \$a(|* \)
            \\
            \(R \rightarrow . \hfill \$a(|* \)
            \\
            \(R \rightarrow .a \hfill \$a(|* \)
            \\
            \(R \rightarrow .(R) \hfill \$a(|* \)
            \\
        };

        \node [block, label=above left: 2] (q2) [below=1cm of q0]
        {
            \(R \rightarrow a. \hfill \$a(|* \)
            \\
        };

        \node [block, label=above left: 3] (q3) [below=1cm of q1]
        {
            \(R \rightarrow (.R) \hfill \$a(|* \)
            \\
            \(R \rightarrow .RR \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R|R \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R* \hfill )\$a(|* \)
            \\
            \(R \rightarrow . \hfill )\$a(|* \)
            \\
            \(R \rightarrow .a \hfill )\$a(|* \)
            \\
            \(R \rightarrow .(R) \hfill )\$a(|* \)
            \\
        };

        \node [block, label=above left: 4] (q4) [right=1cm of q1]
        {
            \(R \rightarrow RR. \hfill \$a(|* \)
            \\
            \(R \rightarrow R.R \hfill \$a(|* \)
            \\
            \(R \rightarrow R.|R \hfill \$a(|* \)
            \\
            \(R \rightarrow R.* \hfill \$a(|* \)
            \\
            \(R \rightarrow .RR \hfill \$a(|* \)
            \\
            \(R \rightarrow .R|R \hfill \$a(|* \)
            \\
            \(R \rightarrow .R* \hfill \$a(|* \)
            \\
            \(R \rightarrow . \hfill \$a(|* \)
            \\
            \(R \rightarrow .a \hfill \$a(|* \)
            \\
            \(R \rightarrow .(R) \hfill \$a(|* \)
            \\
        };
        
        \node [block, label=above left: 5] (q5) [below=1cm of q4]
        {
            \(R \rightarrow R|.R \hfill \$a(|* \)
            \\
            \(R \rightarrow .RR \hfill \$a(|* \)
            \\
            \(R \rightarrow .R|R \hfill \$a(|* \)
            \\
            \(R \rightarrow .R* \hfill \$a(|* \)
            \\
            \(R \rightarrow . \hfill \$a(|* \)
            \\
            \(R \rightarrow .a \hfill \$a(|* \)
            \\
            \(R \rightarrow .(R) \hfill \$a(|* \)
            \\
        };

        \node [block, label=above left: 6] (q6) [above=1cm of q1]
        {
            \(R \rightarrow R*. \hfill \$a(|* \)
            \\
        };

        \node [block, label=above left: 7] (q7) [below=1cm of q3]
        {
            \(R \rightarrow (R.) \hfill \$a(|* \)
            \\
            \(R \rightarrow R.R \hfill )\$a(|* \)
            \\
            \(R \rightarrow R.|R \hfill )\$a(|* \)
            \\
            \(R \rightarrow R.* \hfill )\$a(|* \)
            \\
            \(R \rightarrow .RR \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R|R \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R* \hfill )\$a(|* \)
            \\
            \(R \rightarrow . \hfill )\$a(|* \)
            \\
            \(R \rightarrow .a \hfill )\$a(|* \)
            \\
            \(R \rightarrow .(R) \hfill )\$a(|* \)
            \\
        };

        \node [block, label=above left: 10] (q10pp) [below=1cm of q2]
        {};

        \node [block, label=above left: 8] (q8) [below=1cm of q10pp]
        {
            \(R \rightarrow a. \hfill \$a(|* \)
            \\
        };

        \node [block, label=above left: 9] (q9) [right=1cm of q4]
        {
            \(R \rightarrow (.R) \hfill )\$a(|* \)
            \\
            \(R \rightarrow .RR \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R|R \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R* \hfill )\$a(|* \)
            \\
            \(R \rightarrow . \hfill )\$a(|* \)
            \\
            \(R \rightarrow .a \hfill )\$a(|* \)
            \\
            \(R \rightarrow .(R) \hfill )\$a(|* \)
            \\
        };

        \node [block, label=above left: 2] (q2p) [above=1cm of q9]
        {};

        \node [block, label=above left: 10] (q10) [right=1cm of q5]
        {
            \(R \rightarrow R|R. \hfill \$a(|* \)
            \\
            \(R \rightarrow R.R \hfill \$a(|* \)
            \\
            \(R \rightarrow R.|R \hfill \$a(|* \)
            \\
            \(R \rightarrow R.* \hfill \$a(|* \)
            \\
            \(R \rightarrow .RR \hfill \$a(|* \)
            \\
            \(R \rightarrow .R|R \hfill \$a(|* \)
            \\
            \(R \rightarrow .*R \hfill \$a(|* \)
            \\
            \(R \rightarrow . \hfill \$a(|* \)
            \\
            \(R \rightarrow .a \hfill \$a(|* \)
            \\
            \(R \rightarrow .(R) \hfill \$a(|* \)
            \\
        };

        \node [block, label=above left: 2] (q2pp) [below=1cm of q5]
        {};

        \node [block, label=above left: 11] (q11) [below=1cm of q8]
        {
            \(R \rightarrow (R). \hfill \$a(|* \)
            \\
        };

        \node [block, label=above left: 12] (q12) [below=1cm of q11]
        {
            \(R \rightarrow RR. \hfill )\$a(|* \)
            \\
            \(R \rightarrow R.R \hfill )\$a(|* \)
            \\
            \(R \rightarrow R.|R \hfill )\$a(|* \)
            \\
            \(R \rightarrow R.* \hfill )\$a(|* \)
            \\
            \(R \rightarrow .RR \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R|R \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R* \hfill )\$a(|* \)
            \\
            \(R \rightarrow . \hfill )\$a(|* \)
            \\
            \(R \rightarrow .a \hfill )\$a(|* \)
            \\
            \(R \rightarrow .(R) \hfill )\$a(|* \)
            \\
        };

        \node [block, label=above left: 13] (q13) [below=1cm of q12]
        {
            \(R \rightarrow R|.R \hfill )\$a(|* \)
            \\
            \(R \rightarrow .RR \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R|R \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R* \hfill )\$a(|* \)
            \\
            \(R \rightarrow . \hfill )\$a(|* \)
            \\
            \(R \rightarrow .a \hfill )\$a(|* \)
            \\
            \(R \rightarrow .(R) \hfill )\$a(|* \)
            \\
        };
    
        \node [block, label=above left: 14] (q14) [below=1cm of q7]
        {
            \(R \rightarrow R*. \hfill )\$a(|* \)
            \\
        };

        \node [block, label=above left: 9] (q9p) [below=1cm of q2pp]
        {};

        \node [block, label=above left: 8] (q8p) [below=1cm of q9p]
        {};

        \node [block, label=above left: 15] (q15) [right=1cm of q9p]
        {
            \(R \rightarrow (R.) \hfill )\$a(|* \)
            \\
            \(R \rightarrow R.R \hfill )\$a(|* \)
            \\
            \(R \rightarrow R.|R \hfill )\$a(|* \)
            \\
            \(R \rightarrow R.* \hfill )\$a(|* \)
            \\
            \(R \rightarrow .RR \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R|R \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R* \hfill )\$a(|* \)
            \\
            \(R \rightarrow . \hfill )\$a(|* \)
            \\
            \(R \rightarrow .a \hfill )\$a(|* \)
            \\
            \(R \rightarrow .(R) \hfill )\$a(|* \)
            \\
        };

        \node [block, label=above left: 10] (q10p) [left=1cm of q6]
        {};

        \node [block, label=above left: 9] (q9ppp) [below=1cm of q14]
        {};

        \node [block, label=above left: 16] (q16) [below=1cm of q8p]
        {
            \(R \rightarrow R|R. \hfill )\$a(|* \)
            \\
            \(R \rightarrow R.R \hfill )\$a(|* \)
            \\
            \(R \rightarrow R.|R \hfill )\$a(|* \)
            \\
            \(R \rightarrow R.* \hfill )\$a(|* \)
            \\
            \(R \rightarrow .RR \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R|R \hfill )\$a(|* \)
            \\
            \(R \rightarrow .R* \hfill )\$a(|* \)
            \\
            \(R \rightarrow . \hfill )\$a(|* \)
            \\
            \(R \rightarrow .a \hfill )\$a(|* \)
            \\
            \(R \rightarrow .(R) \hfill )\$a(|* \)
            \\
        };

        \node [block, label=above left: 8] (q8pp) [below=1cm of q9ppp]
        {};

        \node [block, label=above left: 12] (q12p) [below=1cm of q15]
        {};

        \node [block, label=above left: 17] (q17) [below=1cm of q12p]
        {
            \(R \rightarrow (R). \hfill )\$a(|* \)
            \\
        };

        \draw[->] (q0) edge[right] node[above] {R} (q1);
        \draw[->] (q0) edge[below] node[right] {a} (q2);
        \draw[->] (q0) edge[below] node[right] {(} (q3);
        \draw[->] (q1) edge[right] node[above] {R} (q4);
        \draw[->] (q1) edge[right] node[above] {|} (q5);
        \draw[->] (q1) edge[above] node[right] {*} (q6);
        \draw[->] (q1) edge[above] node[right] {a} (q2);
        \draw[->] (q1) edge[above] node[right] {(} (q3);
        \draw[->] (q3) edge[above] node[right] {R} (q7);
        \draw[->] (q3) edge[above] node[above] {a} (q8);
        \draw[->] (q4) edge[above] node[above] {R} (q9);
        \draw[->] (q4) edge[loop above,looseness=2] node[above] {R} (q4);
        \draw[->] (q4) edge[above] node[right] {|} (q5);
        \draw[->] (q4) edge[above] node[right] {*} (q6);
        \draw[->] (q4) edge[above] node[right] {a} (q2p);
        \draw[->] (q4) edge[above] node[right] {(} (q3);
        \draw[->] (q5) edge[above] node[above] {R} (q10);
        \draw[->] (q5) edge[above] node[right] {a} (q2pp);
        \draw[->] (q5) edge[above] node[above] {(} (q3);
        \draw[->] (q7) edge[above] node[above] {)} (q11);
        \draw[->] (q7) edge[above] node[above] {R} (q12);
        \draw[->] (q7) edge[above] node[above] {|} (q13);
        \draw[->] (q7) edge[above] node[right] {*} (q14);
        \draw[->] (q7) edge[above] node[right] {a} (q8);
        \draw[->] (q7) edge[above] node[above] {(} (q9p);
        \draw[->] (q9p) edge[above] node[above] {R} (q15);
        \draw[->] (q9p) edge[above] node[right] {a} (q8p);
        \draw[->] (q9p) edge[loop above,looseness=3] node[above] {a} (q9p);
        \draw[->] (q10) edge[above] node[right] {R} (q4);
        \draw[->] (q10) edge[bend left] node[above] {|} (q5);
        \draw[->] (q10p) edge[right] node[above] {*} (q6);
        \draw[->] (q10pp) edge[above] node[right] {a} (q2);
        \draw[->] (q10pp) edge[right] node[above] {(} (q3);
        \draw[->] (q12) edge[loop above,looseness=1] node[above] {R} (q12);
        \draw[->] (q12) edge[below] node[right] {|} (q13);
        \draw[->] (q12) edge[right] node[above] {*} (q14);
        \draw[->] (q12) edge[above] node[above] {a} (q8);
        \draw[->] (q12) edge[right] node[below] {(} (q9ppp);
        \draw[->] (q13) edge[right] node[above] {R} (q16);
        \draw[->] (q13) edge[right] node[below] {a} (q8pp);
        \draw[->] (q13) edge[right] node[above] {(} (q9ppp);
        \draw[->] (q15) edge[below] node[right] {)} (q17);
        \draw[->] (q15) edge[bend left] node[left] {R} (q12p);

        \draw[->] (q15) edge[left] node[below] {|} (q13);
        \draw[->] (q15) edge[left] node[below] {*} (q14);
        \draw[->] (q15) edge[left] node[below] {a} (q8);
        \draw[->] (q15) edge[left] node[below] {(} (q9);
        \draw[->] (q16) edge[left] node[below] {R} (q12);
        \draw[->] (q16) edge[left] node[below] {|} (q13);
        \draw[->] (q16) edge[left] node[below] {*} (q14);
        \draw[->] (q16) edge[left] node[below] {a} (q8);
        \draw[->] (q16) edge[left] node[below] {(} (q9);
    \end{tikzpicture} 
\end{latin}
\begin{center}
    \begin{latin}
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|}
    \hline
    State  & |        & *        & a        & (        & )        & \$        & S        & R \\ \hline
    0      & r5       & r5       &s2/r5     &s3/r5     &          &r5         &          & g1\\ \hline
    1      &s5/r5     &s6/r5     &s2/r5     &s3/r5     &          &acc/r5     &          & g4\\ \hline
    2      &r6        &r6        &r6        &r6        &          &r6         &          &   \\ \hline
    3      &r5        &r5        &s8/r5     &s9/r5     &r5        &           &          & g7\\ \hline
    4      &s5/r2/r5  &s6/r2/r5  &s2/r2/r5  &s3/r2/r5  &          &r2/r5      &          & g4\\ \hline
    5      &r5        &r5        &s2/r5     &s3/r5     &          &r5         &          &g10\\ \hline
    6      &r4        &r4        &r4        &r4        &          &r4         &          &   \\ \hline
    7      &s13/r5    &s14/r5    &s8/r5     &s9/r5     &s11/r5    &           &          &g12\\ \hline
    8      &r6        &r6        &r6        &r6        &r6        &           &          &   \\ \hline
    9      &r5        &r5        &s8/r5     &s9/r5     &r5        &           &          &g15\\ \hline
    10     &s5/r3/r5  &s6/r3/r5  &s2/r3/r5  &s3/r3/r5  &          &r3/r5      &          & g4\\ \hline
    11     &r7        &r7        &r7        &r7        &          &r7         &          &   \\ \hline
    12     &s13/r2/r5 &s14/r2/r5 &s8/r2/r5  &s9/r2/r5  &r2/r5     &           &          &g12\\ \hline
    13     &r5        &r5        &s8/r5     &s9/r5     &r5        &           &          &g16\\ \hline
    14     &r4        &r4        &r4        &r4        &r4        &           &          &   \\ \hline
    15     &s13/r5    &s14/r5    &s8/r5     &s9/r5     &s17/r5    &           &          &g12\\ \hline
    16     &s13/r3/r5 &s14/r3/r5 &s8/r3/r5  &s9/r3/r5  &r3/r5     &           &          &g12\\ \hline
    17     &r7        &r7        &r7        &r7        &r7        &           &          &   \\ \hline
    \end{tabular}
    \end{latin}
\end{center}

قسمت ب:

کانفلیکت‌ها در جدول مشخص هستند، هر خانه که بیش از یک امکان برای آن وجود دارد، یک کانفلیکت خواهد بود.
هر گرامری که SLR(1) است حتما LR(1) هم خواهد بود، پس با توجه به این عبارت، اگر گرامری LR(1) نیست پس SLR(1) نیز نخواهد بود.
در نتیجه گرامر مورد نظر ما SLR(1) هم نیست.

قسمت د:

\begin{center}
    \begin{latin}
    0.$R' \rightarrow R$
    \\
    1.$R \rightarrow R|S$
    \\
    2.$R \rightarrow S$
    \\
    3.$S \rightarrow ST$
    \\
    4.$S \rightarrow T$
    \\
    5.$T \rightarrow {T}^{*}$
    \\
    6.$T \rightarrow U$
    \\
    7.$U \rightarrow a | b | c .... | z$
    \\
    8.$U \rightarrow (R)$
    \\
    \end{latin}
\end{center}

قسمت ه:

\begin{center}
\begin{latin}
\begin{tikzpicture}
    [node distance=1.5cm]
    \node[state] (R') {R'};

    %right
    \node[state,below of=R'] (R0) {R};
    \node[state,yshift=-1.5cm,right of=R0] (S0) {S};
    \node[state,yshift=-1.5cm,right of=S0] (R3) {S};
    \node[state,yshift=-1.5cm,right of=R3] (S4) {S};
    \node[state,yshift=-1.5cm,right of=S4] (T3) {T};
    \node[state,yshift=-1.5cm,right of=T3] (U2) {U};
    \node[state,below of=U2] (E) {e};
    
    %left of S0
    \node[state,left of=S0] (OR0) {|};
    \node[state,left of=OR0] (R1) {R};
    
    \node[state,below of=OR0] (S1) {S};
    \node[state,left of=S1] (OR1) {|};
    \node[state,left of=OR1] (R2) {R};

    %left
    \node[state,yshift=-1.5cm,left of=R2] (S2) {S};
    \node[state,yshift=-1.5cm,left of=S2] (T1) {T};
    \node[state,yshift=-1.5cm,left of=T1] (U1) {U};
    \node[state,below of=U1] (A) {a};

    \node[state,xshift=-1cm,below of=S1] (S3) {S};
    \node[state,xshift=1cm,below of=S1] (T0) {T};

    \node[state,xshift=1cm,below of=T0] (U0) {U};
    \node[state,xshift=1cm,below of=U0] (D) {d};

    \node[state,xshift=1cm,below of=S3] (T2) {T};
    \node[state,xshift=-1cm,below of=S3] (S5) {S};

    \node[state,xshift=-1cm,below of=S5] (T4) {T};
    \node[state,xshift=-1cm,below of=T4] (U3) {U};
    \node[state,xshift=-1cm,below of=U3] (B) {b};


    \node[state,xshift=-1cm,below of=T2] (T5) {T};
    \node[state,xshift=1cm,below of=T2] (ST) {*};

    \node[state,below of=T5] (U4) {U};
    \node[state,below of=U4] (C) {c};

    \draw[-] (R') to (R0);
    \draw[-] (R0) to (R1);
    \draw[-] (R0) to (OR0);
    \draw[-] (R0) to (S0);
    \draw[-] (R1) to (R2);
    \draw[-] (R1) to (OR1);
    \draw[-] (R1) to (S1);
    \draw[-] (S0) to (R3);
    \draw[-] (R2) to (S2);
    \draw[-] (S1) to (S3);
    \draw[-] (S1) to (T0);
    \draw[-] (R3) to (S4);
    \draw[-] (S2) to (T1);
    \draw[-] (S3) to (S5);
    \draw[-] (S3) to (T2);
    \draw[-] (T0) to (U0);
    \draw[-] (S4) to (T3);
    \draw[-] (T1) to (U1);
    \draw[-] (S5) to (T4);
    \draw[-] (T2) to (T5);
    \draw[-] (T2) to (ST);
    \draw[-] (U0) to (D);
    \draw[-] (T3) to (U2);
    \draw[-] (U1) to (A);
    \draw[-] (T4) to (U3);
    \draw[-] (U3) to (B);
    \draw[-] (T5) to (U4);
    \draw[-] (U4) to (C);
    \draw[-] (U1) to (A);
    \draw[-] (U2) to (E);



\end{tikzpicture}
\end{latin}
\end{center}