TC

Quiz 1

Given the languages A=\{a^ib^jc^k \mid i=j+k\}, B=\{a^ib^jc^k \mid j=i+k\}, and C=\{a^ib^jc^k \mid k=i+j\} and the context-free grammars \small G_1: \begin{cases} S \longrightarrow S_1 S_2 \\ S_1 \longrightarrow aS_1b \mid \lambda \\ S_2 \longrightarrow bS_2c \mid \lambda \end{cases} \quad G_2: \begin{cases} S \longrightarrow aSc \mid S' \\ S' \longrightarrow bS'c \mid \lambda \\ \end{cases} \quad G_3: \begin{cases} S \longrightarrow aSc \mid S' \\ S' \longrightarrow aS'b \mid \lambda \\ \end{cases} Which of the following options is correct?

1. A = \mathscr L(G_1), B = \mathscr L(G_2), C = \mathscr L(G_3).
2. A = \mathscr L(G_3), B = \mathscr L(G_1), C = \mathscr L(G_2).
3. A = \mathscr L(G_2), B = \mathscr L(G_3), C = \mathscr L(G_1).
4. A = \mathscr L(G_3), B = \mathscr L(G_2), C = \mathscr L(G_1).

Quiz 2

Given the following grammars: G_1: \begin{cases} S \longrightarrow A B\\ A \longrightarrow Aaa \mid a \mid \lambda\\ B \longrightarrow Baa \mid aa \mid \lambda \end{cases} \quad G_2: \begin{cases} S \longrightarrow A \mid B \mid \lambda \\ A \longrightarrow Aaa \mid a \\ B \longrightarrow Baa \mid aa \end{cases}

1. \mathscr L(G_1) = \mathscr L(G_2) and exactly one is ambiguous.
2. \mathscr L(G_1) \ne \mathscr L(G_2) and exactly one is ambiguous.
3. \mathscr L(G_1) = \mathscr L(G_2) and both are ambiguous.
4. \mathscr L(G_1) \ne \mathscr L(G_2) and both are ambiguous.

Quiz 3

Consider the following grammar with 5 productions: \small \begin{align*} S &\rightarrow A\,B \\ A &\rightarrow a\,A \mid \lambda \\ B &\rightarrow b\,B \mid \lambda\end{align*} How many productions has the grammars obtained by depurating it? There is no need to define a new initial symbol, but you need to remove \lambda-productions and unary productions.

1. 10
2. 11
3. 12
4. 13

Quiz 4

We want to show that L= \{a^mb^nc^md^n \mid m,n \geq 0\} is not context-free using directly the pumping lemma for CFL. Given the pumping length N, we choose a word w to apply the lemma.

Which of the following choices has some hope to make the rest of the argument correct?

1. w = abcd.
2. w = a^N bc^N d.
3. w = ab^N cd^N.
4. w = a^N b^N c^N d^N.