Context-Free Languages & PDA

One or more correct

• AThe grammar is ambiguous
• BThe string $abb$ has two distinct derivations in this grammar
• CThe string $abab$ has only one rightmost derivation
• DThe language generated by the grammar is undecidable

One or more correct

• AThere is a string $s \in L(G)$ such that $n_1(s) < n_2(s)$
• BFor every string $s \in L(G)$, $n_1(s) \ge n_2(s)$
• CThere is a string $s \in L(G)$ such that $n_1(s) > 2n_2(s)$
• DFor every string $s \in L(G)$, $n_1(s) \le 2n_2(s)$

One or more correct

• A$S \to aSb \mid \epsilon$
• B$E \to E + E \mid E * E \mid id$
• C$S \to aS \mid Sa \mid \epsilon$
• D$S \to aS \mid \epsilon$

One or more correct

• A$i + k = j + \ell$
• B$i = k$ and $j = \ell$
• C$i = \ell$ and $j = k$
• D$i + j = k + \ell$

Single correct

• A$L(G) = \{a^2 b^n \mid n \ge 1\} \cup \{a^n b^2 \mid n \ge 1\}$
• B$L(G) = \{a^n b^{2n} \mid n \ge 1\} \cup \{a^{2n} b^n \mid n \ge 1\}$
• C$L(G) = \{a^n b^n \mid n \ge 1\}$
• D$L(G) = \{a^{2n} b^{2n} \mid n \ge 1\}$

Single correct

• ABoth $L_1$ and $L_2$ are context-free languages.
• B$L_1$ is a context-free language but $L_2$ is not a context-free language.
• C$L_1$ is not a context-free language but $L_2$ is a context-free language.
• DNeither $L_1$ nor $L_2$ are context-free languages.

Single correct

• AAny regular language.
• BAny context-free language.
• CAny language accepted by a non-deterministic pushdown automaton.
• DAny decidable language.

Numerical answer

One or more correct

• A$n_a(w) > n_b(w)$
• B$n_a(w) > n_c(w) - 2$
• C$n_c(w) = n_b(w) + 1$
• D$n_c(w) = n_b(w) * 2$

One or more correct

• AThe intersection of two regular languages is regular.
• BThe intersection of two context-free languages is context-free.
• CThe intersection of two recursive languages is recursive.
• DThe intersection of two recursively enumerable languages is recursively enumerable.

Answer key coming soon

Single correct

• AThe language generated by $G$ is $(a + b)^*$
• BThe language generated by $G$ is $a^*(a + b)b^*$
• CThe language generated by $G$ is $a^*b^*(a + b)$
• DThe language generated by $G$ is not a regular language

Answer key coming soon

Single correct

• A$\{a^m b^n \mid 1 \le m \text{ and } n < m\}$
• B$\{a^m b^n \mid 0 \le n \le m\}$
• C$\{a^m b^n \mid 0 \le m \text{ and } 0 \le n\}$
• D$\{a^m \mid 0 \le m\} \cup \{b^n \mid 0 \le n\}$

Answer key coming soon

One or more correct

• A$L_1$ and $L_2$ are regular.
• B$L_1$ and $L_2$ are context-free.
• C$L_1$ is regular and $L_2$ is context-free.
• D$L_1$ and $L_2$ are context-free but not regular.

Answer key coming soon

One or more correct

• A$L_1$ is not context-free but $L_2$ and $L_3$ are deterministic context-free.
• BNeither $L_1$ nor $L_2$ is context-free.
• C$L_2$, $L_3$ and $L_2 \cap L_3$ all are context-free.
• DNeither $L_1$ nor its complement is context-free.

Answer key coming soon

Single correct

• A$L_1 \cap L_2$
• B$L_1 \cdot L_2$
• C$L_1 - L_2$
• D$L_1 \cup L_2$

Answer key coming soon

Numerical answer

Answer key coming soon

One or more correct

• A$L_1 \cap \overline{L_2}$
• B$\overline{\overline{L_1} \cup \overline{L_2}}$
• C$L_1 \cup (L_2 \cup \overline{L_2})$
• D$(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$

Answer key coming soon

One or more correct

• A$\{wxw^Rx^R \mid w, x \in \{0,1\}^*\}$
• B$\{ww^Rxx^R \mid w, x \in \{0,1\}^*\}$
• C$\{wxw^R \mid w, x \in \{0,1\}^*\}$
• D$\{wxx^Rw^R \mid w, x \in \{0,1\}^*\}$

Answer key coming soon

Single correct

• AI only
• BII only
• CI and III only
• DIII only

Answer key coming soon

Single correct

• A$L_1$ is regular and $L_2$ is context-free.
• B$L_1$ is context-free but not regular and $L_2$ is context-free.
• CNeither $L_1$ nor $L_2$ is context-free.
• D$L_1$ is context-free but $L_2$ is not context-free.

Answer key coming soon