Context Free Grammar Practice Questions

A grammar is free from left recursion if no non-terminal can derive a string that starts with itself.

• Grammar A has direct left recursion: $A \rightarrow Aa|b$.
• Grammar C has indirect left recursion: $S \Rightarrow Aa \Rightarrow Sca...$.
• Grammar D has indirect left recursion: $A \Rightarrow Bd \Rightarrow Aed...$.
• Grammar B has no productions where a non-terminal derives a string starting with itself, either directly or through a series of derivations. Therefore, it is free from left recursion.

For $G1$, $S \rightarrow aS | B$ expands to $a^* B$, and since $B \rightarrow b | bB$ generates $b^+$, $G1$ produces strings $\{a^m b^n \mid m \geq 0, n > 0\}$.
For $G2$, $S \rightarrow aA | bB$ splits into two branches:

1. $S \rightarrow aA$ where $A \rightarrow aA | B | \varepsilon$ generates $a^+ (a^* b^*)$ which simplifies to $\{a^m b^n \mid m > 0, n \geq 0\}$.
2. $S \rightarrow bB$ where $B \rightarrow bB | \varepsilon$ generates $b^+$, which is $\{a^0 b^n \mid n > 0\}$.
   Combining these, $G2$ produces strings $\{a^m b^n \mid m > 0 \text{ or } n > 0\}$.
   Comparing these results with the given choices, Option D matches both derivations.

The given grammar is $S\rightarrow aS|bS|\varepsilon$. The productions $S \rightarrow aS$ and $S \rightarrow bS$ allow for prefixing the derived string with either an 'a' or a 'b' and then continuing the derivation from $S$. The production $S \rightarrow \varepsilon$ provides the base case to terminate the recursion. This process can generate any sequence of 'a's and 'b's of any length, including the empty string ($\varepsilon$). This is the definition of the set of all strings over the alphabet {a, b}, which is denoted by $\{a,b\}^*$.

To derive the string "aabbaab" from the given CFG, we apply the production rules in the following sequence:

1. $S \rightarrow aS$
2. $S \rightarrow A$ (applied to the $S$ in $aS$)
3. $A \rightarrow aAb$
4. $A \rightarrow bAa$ (applied to the $A$ in $a(aAb)$)
5. $A \rightarrow bAa$ (applied to the $A$ in $aa(bAa)b$)
6. $A \rightarrow \epsilon$ (applied to the $A$ in $aab(bAa)ab$)

The derivation $S \Rightarrow aS \Rightarrow aA \Rightarrow a(aAb) \Rightarrow aa(bAa)b \Rightarrow aab(bAa)ab \Rightarrow aabbaa\epsilon b = aabbaab$ involves exactly 6 production steps. Since the grammar is unambiguous for this string, there is only 1 parse tree.

The production $B \to 0B00 \mid 1$ recursively generates strings where each 1 is surrounded by 0s in a $1:2$ ratio, specifically $L(B) = \{0^n 1 0^{2n} \mid n \geq 0\}$.
The production $A \to 0A \mid A0 \mid 1$ allows adding 0s anywhere relative to the single terminal 1, resulting in all strings containing exactly one 1: $L(A) = \{0^i 1 0^j \mid i, j \geq 0\}$.
Concatenating $AA$ produces strings with exactly two 1s: $L(AA) = \{0^i 1 0^j 1 0^k \mid i, j, k \geq 0\}$.
Since $S \to AA \mid B$, the grammar generates the union of these two sets.
Thus, the total language is $\{0^i 1 0^j 1 0^k \mid i, j, k \geq 0\} \cup \{0^n 1 0^{2n} \mid n \geq 0\}$.

• Statement I is true because left-recursive grammars can be transformed into equivalent right-recursive ones using standard algorithmic techniques.
• Statement II is false because $\varepsilon$-productions cannot be removed from a context-free grammar if the language contains the empty string $\varepsilon$ (the transformation typically generates $L \setminus \{\varepsilon\}$).
• Statement III is true because a grammar with productions $X \rightarrow w$ or $X \rightarrow wY$ is a right-linear grammar, and all right-linear grammars generate regular languages.
• Statement IV is true because, in Chomsky Normal Form, productions are restricted to $A \rightarrow BC$ (binary branching) or $A \rightarrow a$, ensuring every internal node in a derivation tree has exactly two children.
• Since statements I, III, and IV are correct, the correct choice is C.

To generate the string $aabbaab$ using the given grammar $G$:

1. Start with the start symbol $S$: $S \rightarrow aS$
2. Replace $S$ with $A$: $S \rightarrow aA$
3. Apply the production $A \rightarrow aAb$: $S \rightarrow a(aAb) = aaA b$
4. Replace $A$ with $bAa$: $S \rightarrow aa(bAa)b = aabA ab$
5. Replace $A$ with $bAa$: $S \rightarrow aab(bAa)ab = aabbA aab$
6. Use $A \rightarrow \epsilon$ to terminate the derivation: $S \rightarrow aabb(\epsilon)aab = aabbaab$

This demonstrates that $aabbaab$ is generated by the grammar $G$.

First, note that the production $A \to bA \mid \epsilon$ generates the regular language $b^*$.
Substituting this into the production for $S$, we get $S \to aSb^*b \mid \epsilon$, which simplifies to $S \to aSb^+ \mid \epsilon$.
Each recursive expansion of $S$ adds one $a$ and a string $w \in b^+$, meaning at least one $b$ is added.
After $m$ recursive steps, the grammar produces $a^m w_1 w_2 \dots w_m$ where each $w_i \in \{b, bb, bbb, \dots\}$.
Since each $w_i$ contributes at least one $b$, the total number of $b$'s ($n$) must satisfy $n \geq m$.
Therefore, the language generated is $\{a^m b^n \mid m \leq n\}$.

Grammar $G$ is ambiguous because the string $abab$ has multiple distinct parse trees (e.g., $S \rightarrow SS \rightarrow (ab)S \rightarrow ab(ab)$ and $S \rightarrow SS \rightarrow S(SS) \rightarrow (SS)S \dots$); thus, Statement 1 is TRUE.
$G$ generates only strings formed by concatenating blocks of $ab$ or $ba$, meaning $L(G) = \{ab, ba\}^*$. It fails to produce strings like $aabb \in \{w \mid n_a(w) = n_b(w)\}$, so Statement 2 is FALSE.
Since $L(G) = \{ab, ba\}^*$ is a regular language (defined by the regular expression $(ab|ba)^*$), it can be recognized by a deterministic finite automaton, and consequently by a deterministic PDA. Thus, Statement 3 is TRUE.
Combining these, only statements I and III are true.

The grammar $S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon$ generates all palindromes over the alphabet $\{a, b\}$ because every production rule adds matching characters to both ends or places a single character/empty string at the center.
A string $w$ is generated if and only if it is a palindrome (i.e., $w = w^R$).
Analyzing the options:

• $aaaa$, $abba$, and $babaaabab$ are all palindromes ($w = w^R$), so they are generated.
• $baba$ is not a palindrome because its reversal is $abab \neq baba$.
  Therefore, $baba$ cannot be generated by this grammar.

An operator grammar must satisfy two conditions: it contains no $\varepsilon$-productions, and no two nonterminals are adjacent in any production rule.
(i) $P \rightarrow QR$ violates the second condition because nonterminals $Q$ and $R$ are adjacent.
(ii) $P \rightarrow QsR$ is valid because the nonterminals $Q$ and $R$ are separated by the terminal $s$.
(iii) $P \rightarrow \varepsilon$ violates the first condition as it is an $\varepsilon$-production.
(iv) $P \rightarrow QtRr$ is valid because all adjacent nonterminals are separated by terminals.
Thus, only (i) and (iii) violate the requirements of an operator grammar.

The statement is FALSE because the class of languages accepted by Deterministic Pushdown Automata (DPDA), known as Deterministic Context-Free Languages (DCFLs), is a proper subset of the class of languages accepted by Non-deterministic Pushdown Automata (NPDA), which are the Context-Free Languages (CFLs). Mathematically, $DCFL \subsetneq CFL$. A classic example of a CFL that is not a DCFL is the language of even-length palindromes $L = \{w w^R \mid w \in \{a, b\}^*\}$, which requires non-determinism to identify the midpoint. Thus, the two automata do not accept the same set of languages.

The grammar $G$ with rules $S \rightarrow aSb \mid SS \mid \epsilon$ generates the Dyck language $L(G)$.
Option A is false because the rule $S \rightarrow SS$ makes $G$ ambiguous, as strings like $\epsilon$ have multiple distinct derivations.
Option B is false because $L(G)$ is closed under concatenation; thus, $x, y \in L(G)$ implies $xy \in L(G)$, meaning no such $x, y$ exist.
Option D is false because $L(G)$ is not a regular language, which implies it cannot be accepted by any deterministic finite state automaton.
By process of elimination, we conclude that the statement in option C must be the intended true answer.

$LL(1)$ grammars are a strict subset of Context-Free Grammars (CFGs) that define only a specific class of deterministic languages. Many CFGs describe languages that are inherently ambiguous or non-deterministic, and such languages cannot be represented by an $LL(1)$ grammar regardless of the transformations applied. While removing left recursion and left factoring are necessary steps to make a suitable grammar $LL(1)$, they are insufficient to convert an arbitrary CFG into an $LL(1)$ grammar because they cannot change the inherent nature of the language itself. Therefore, no finite combination of these transformations can transform every possible CFG into an $LL(1)$ grammar.

The given grammar consists of the productions $S \rightarrow CCC$ and $C \rightarrow cC \mid d$.
To determine if the grammar is $LL(1)$, we check if the $FIRST$ sets for the alternative productions of each non-terminal are disjoint.
For the non-terminal $C$, the productions are $C \rightarrow cC$ and $C \rightarrow d$.
We calculate the $FIRST$ sets: $FIRST(cC) = \{c\}$ and $FIRST(d) = \{d\}$.
Since $FIRST(cC) \cap FIRST(d) = \{c\} \cap \{d\} = \emptyset$, the grammar is deterministic and predictive.
There is no left recursion, and the predictive parsing table for this grammar contains no conflicts.
Thus, the grammar is $LL(1)$.

The problem (P1) asks about string membership in a finite state machine $M$ for a string $w$. This is decidable because one can simulate the execution of $M$ on the finite string $w$, which is guaranteed to terminate in $|w|$ transitions.
The problem (P2) asks if a context-free grammar $G$ generates an infinite language $L(G)$. This is decidable by analyzing the grammar to detect cycles in the variable dependency graph.
Specifically, $L(G)$ is infinite if and only if there exists a derivation $S \Rightarrow^* uAv \Rightarrow^* u(xAy)v \Rightarrow^* uxyv$, where $x$ and $y$ are non-empty strings.
Since cycles in the dependency graph can be identified using standard graph traversal algorithms in finite time, (P2) is also decidable.
As both (P1) and (P2) possess algorithms that are guaranteed to terminate with an answer, the correct conclusion is that both are decidable.

An $LR(k)$ grammar is a specific type of deterministic, unambiguous context-free grammar that can be parsed using a bottom-up approach with $k$ lookahead symbols. The provided production rules define a deterministic set of transitions, which allow for the construction of a unique shift-reduce parsing table. Because $LR(k)$ grammars encompass the class of deterministic context-free languages, this classification represents the most precise and specific description among the given options. The structure of the rules ensures that each input sequence leads to a unique parse tree, confirming the grammar's deterministic nature. Thus, the grammar is categorized as $LR(k)$.

Context-Free Grammars (CFGs) are well-suited for describing nested, hierarchical structures like $if-then-else$ statements (A) and recursive procedures (B) using recursive production rules. Variable names of arbitrary length (D) can be generated by regular expressions (e.g., $S \to \alpha S \mid \epsilon$), which are a subset of context-free languages. In contrast, requiring that a variable be declared before its use (C) necessitates checking an identifier against a symbol table or maintaining state to ensure a match, which is a context-sensitive dependency. CFGs operate under the rule $A \to \gamma$, where the non-terminal $A$ is replaced regardless of the surrounding context, making it impossible to enforce cross-referencing constraints between distant tokens. Consequently, "declaration before use" falls outside the capabilities of CFGs and requires more powerful formal systems.