Context Free Grammar Practice Questions

A language is context-free if a Pushdown Automaton (PDA) can recognize it. We examine the given constraints for the language $L = \{a^ib^jc^kd^\ell \mid i, j, k, \ell \ge 0\}$.

For Option A: The constraint is $i + k = j + \ell$. The language $L_A = \{a^ib^jc^kd^\ell \mid i+k = j+\ell\}$ is context-free because a PDA can manage these counts using its stack and states.

For Option C: The constraints are $i = \ell$ and $j = k$. This implies strings of the form $a^i b^j c^j d^i$. The language $L_C = \{a^i b^j c^j d^i \mid i, j \ge 0\}$ is context-free. It can be generated by the Context-Free Grammar:
$S \to a S d \mid T$
$T \to b T c \mid \epsilon$

For Option D: The constraint is $i + j = k + \ell$. The language $L_D = \{a^ib^jc^kd^\ell \mid i+j = k+\ell\}$ is context-free. A PDA can recognize this by pushing a marker for each 'a' or 'b' onto the stack and popping a marker for each 'c' or 'd'. If the stack is empty at the end, the condition is met.

Therefore, the constraints $i+k=j+\ell$, $i=\ell$ and $j=k$, and $i+j=k+\ell$ ensure that $L$ is context-free.

Hello! Let's break down this grammar problem step-by-step, just like we would in a class.

A. The grammar is ambiguous

A grammar is called ambiguous if there is at least one string that can be generated in more than one way. This means a string has more than one leftmost derivation, more than one rightmost derivation, or more than one parse tree.

As we will show for the next statement, the string $abb$ has two different derivations. Since we found a string with multiple derivations, the grammar is indeed ambiguous.

Therefore, statement A is True.

B. The string $abb$ has two distinct derivations in this grammar

Let's try to derive the string $abb$ from the start symbol $S$. We need to find two different sequences of rule applications.

Derivation 1:
Here, we apply $S \rightarrow \epsilon$ to the first $S$ in $aSbS$.
$S \Rightarrow aSbS$
$\rightarrow a(\epsilon)bS \quad \text{(using } S \rightarrow \epsilon \text{)}$
$\rightarrow abS$
$\rightarrow ab(bS) \quad \text{(using } S \rightarrow bS \text{)}$
$\rightarrow abbS$
$\rightarrow abb(\epsilon) \quad \text{(using } S \rightarrow \epsilon \text{)}$
$\rightarrow abb$

Derivation 2:
Here, we apply $S \rightarrow bS$ to the first $S$ in $aSbS$.
$S \Rightarrow aSbS$
$\rightarrow a(bS)bS \quad \text{(using } S \rightarrow bS \text{)}$
$\rightarrow ab(\epsilon)bS \quad \text{(using } S \rightarrow \epsilon \text{)}$
$\rightarrow abbS$
$\rightarrow abb(\epsilon) \quad \text{(using } S \rightarrow \epsilon \text{)}$
$\rightarrow abb$

Since we found two distinct derivation paths to get the string $abb$, this statement is correct.

Therefore, statement B is True.

C. The string $abab$ has only one rightmost derivation

A rightmost derivation (RMD) is one where we always replace the rightmost non-terminal at each step. Let's try to construct the RMD for $abab$ and see if we have any choices along the way.

To get a string starting with 'a', our only first step is:
$S \Rightarrow aSbS$

Now, we must expand the rightmost $S$. To get the final string $abab$, the part generated by this rightmost $S$ must be $ab$. The only way to generate a string starting with 'a' is using $S \rightarrow aSbS$.
$S \Rightarrow aS b (aSbS)$

The rightmost non-terminal is now the final $S$. Our target string is $abab$, which ends with b. Our current form is $...bS$. This forces the final $S$ to derive $\epsilon$.
$S \Rightarrow aS b (aSb\epsilon)$ which is $aSb(aSb)$

The rightmost non-terminal is now the $S$ inside the parenthesis. Our target is $abab$. We have ...a S b corresponding to ...a b. This forces this $S$ to derive $\epsilon$.
$S \Rightarrow aS b (a\epsilon b)$ which is $aSb(ab)$

The rightmost (and only) non-terminal is now the first $S$. We have $aSbab$. To match $abab$, this $S$ must derive $\epsilon$.
$S \Rightarrow a(\epsilon)bab$ which is $abab$

At every step of this rightmost derivation, the choice of which production rule to use was forced upon us to match the target string $abab$. Since we had no alternative choices, the rightmost derivation is unique.

Therefore, statement C is True.

D. The language generated by the grammar is undecidable

This grammar is a Context-Free Grammar (CFG). Any language generated by a CFG is a Context-Free Language (CFL).

A fundamental result in the theory of computation is that the membership problem for CFLs is decidable. This means there is an algorithm (like the CYK algorithm) that can always determine whether or not a given string belongs to the language generated by a given CFG. Since the language is decidable, this statement is false.

Therefore, statement D is False.

For $G_1: S \to \text{if } E \text{ then } S \mid \text{if } E \text{ then } S \text{ else } S \mid a$ and $E \to b$:
To check if $G_1$ is LL(1), we need to ensure that for any non-terminal $A$, for any two distinct productions $A \to \alpha$ and $A \to \beta$, First($\alpha$) $\cap$ First($\beta$) = $\emptyset$. If $\epsilon \in$ First($\alpha$), then First($\alpha$) $\cap$ Follow($A$) = $\emptyset$.
For $S$:

1. $S \to \text{if } E \text{ then } S$: First(\text{if } E \text{ then } S$) = {if}
2. $S \to \text{if } E \text{ then } S \text{ else } S$: First(\text{if } E \text{ then } S \text{ else } S$) = {if}
3. $S \to a$: First($a$) = {a}
   Since First(\text{if } E \text{ then } S$)$\cap$First(\text{if } E \text{ then } S \text{ else } S$) = {if} $\neq \emptyset$, $G_1$ is NOT LL(1).

For $G_2: S \to \text{if } E \text{ then } S \mid M$, $M \to \text{if } E \text{ then } M \text{ else } S \mid c$ and $E \to b$:
For $S$:

1. $S \to \text{if } E \text{ then } S$: First = {if}
2. $S \to M$: First = First($M$) = {if, c}
   Since First(\text{if } E \text{ then } S$)$\cap$First($M$) = {if}$\neq \emptyset$,$G_2$is NOT LL(1). Therefore, statement (C) "$G_1$and$G_2$ are not LL(1)" is CORRECT.

To check for ambiguity, we can find a string that has multiple parse trees.
For $G_1$, consider the string "if b then if b then a else a". This string has two different parse trees, as illustrated in the solution, making $G_1$ ambiguous.
For $G_2$, consider the string "if b then if b then c else if b then c else c". This string also has two different parse trees, as illustrated in the solution, making $G_2$ ambiguous.
Therefore, statement (D) "$G_1$ and $G_2$ are ambiguous" is CORRECT.

1. To check if a grammar is LL(1), we need to ensure that for any non-terminal $A$, if $A \to \alpha | \beta$ are two productions, then $FIRST(\alpha) \cap FIRST(\beta) = \emptyset$.
2. For grammar $G_1$, the productions for $S$ are $S \to \text{if E then S}$, $S \to \text{if E then S else S}$, and $S \to \text{a}$.
3. $FIRST(\text{if E then S}) = \{\text{if}\}$ and $FIRST(\text{if E then S else S}) = \{\text{if}\}$. Since their intersection is not empty, $G_1$ is not LL(1).
4. For grammar $G_2$, the productions for $S$ are $S \to \text{if E then S}$ and $S \to M$.
5. $FIRST(\text{if E then S}) = \{\text{if}\}$ and $FIRST(M) = FIRST(A) = \{\text{d}\}$. Their intersection is empty. However, the productions for $E$ are $E \to \text{if E then M else S}$ and $E \to b$. $FIRST(\text{if E then M else S}) = \{\text{if}\}$ and $FIRST(b) = \{b\}$. So, this is fine.
6. The issue for $G_2$ arises from its ambiguity, as shown by two parse trees for the same string "if b then if b then c else if b then c else c". An ambiguous grammar cannot be LL(1).
7. For SLR(1) and LALR(1), we construct parsing tables. The provided solution indicates a Shift/Reduce (S/R) conflict for SLR(1) parsing of $G_1$ due to $FIRST(\text{A}) \cap FOLLOW(\text{S})$ overlapping, meaning $G_1$ is not SLR(1).
8. The grammar $G_2$ is also ambiguous, meaning it cannot be SLR(1) or LALR(1). However, the explanation for $G_1$ indicates it is LALR(1) but not SLR(1).
9. The solution text indicates $G_1$ is LALR(1) and CLR(1). $G_1$ is not SLR(1) due to the S/R conflict.

A context-free grammar (CFG) is in Chomsky Normal Form (CNF) if all production rules are of the form $A \rightarrow BC$ or $A \rightarrow a$, where $A, B, C$ are non-terminals and $a$ is a terminal.
For a string $w$ of length $|w|$ generated by a grammar in CNF, the number of steps (applications of rules) in the derivation $S \rightarrow^* w$ is always $2|w|-1$.
Given string $w = a^{30}b^{30}c^{30}$.
The length of the string $|w| = 30 + 30 + 30 = 90$.
The number of steps in the derivation is $2|w|-1$.
Number of steps = $2 \times 90 - 1 = 180 - 1 = 179$.

To determine the correct entries, we calculate the FIRST and FOLLOW sets for the grammar:

1. FIRST sets: $FIRST(A) = \{c, \epsilon\}$, $FIRST(B) = \{d, \epsilon\}$.
   • For $S \rightarrow AaAb$: $FIRST(AaAb) = FIRST(A) \cup \{a\} = \{c, a\}$.
   • For $S \rightarrow BbBa$: $FIRST(BbBa) = FIRST(B) \cup \{b\} = \{d, b\}$.
2. Parsing Table Entries ($M[Non-terminal, Terminal]$):
   • For $S \rightarrow AaAb$: Add to columns $\{c, a\}$. Thus, $M[S, c] = S \rightarrow AaAb$ (Cell 1) and $M[S, a] = S \rightarrow AaAb$.
   • For $S \rightarrow BbBa$: Add to columns $\{d, b\}$. Thus, $M[S, d] = S \rightarrow BbBa$ (Cell 2) and $M[S, b] = S \rightarrow BbBa$.
   • For $A \rightarrow \epsilon$: Add to $FOLLOW(A)$. Since $A$ is followed by $a$ or $b$, $FOLLOW(A) = \{a, b\}$. Thus, $M[A, a] = A \rightarrow \epsilon$ and $M[A, b] = A \rightarrow \epsilon$ (Cell 3).
   • For $B \rightarrow \epsilon$: Add to $FOLLOW(B)$. Since $B$ is followed by $b$ or $a$, $FOLLOW(B) = \{b, a\}$. Thus, $M[B, a] = B \rightarrow \epsilon$ (Cell 4) and $M[B, b] = B \rightarrow \epsilon$.

Comparing with the options: (1) $S \rightarrow AaAb$, (2) $S \rightarrow BbBa$, (3) $A \rightarrow \epsilon$, (4) $B \rightarrow \epsilon$.

To find the items in $I_1 = \operatorname{GOTO}(I_0, S)$, we transition from $I_0$ on the symbol $S$. The items resulting from the transition are $\{S^{\prime} \rightarrow S \bullet, S \rightarrow S \bullet S\}$. To complete the set, we perform $\operatorname{CLOSURE}(\{S^{\prime} \rightarrow S \bullet, S \rightarrow S \bullet S\})$, which adds all items with $\bullet$ followed by $S$:

$

$

Counting these, we find exactly 9 items in $\operatorname{GOTO}(I_0, S)$.

[CORRECT_OPTION: 9]

The given context-free grammar G has the rules:
$S \rightarrow aS$
$S \rightarrow aSbS$
$S \rightarrow c$

Let's derive some strings in $L(G)$ and analyze the counts of $a, b, c$.

1. $S \rightarrow c$:
   $w = c$. $n_a(w)=0, n_b(w)=0, n_c(w)=1$.
   Check options:
   (A) $n_a(w) > n_b(w)$: $0 > 0$ is false.
   (B) $n_a(w) > n_c(w)-2$: $0 > 1-2 = -1$. $0 > -1$ is true.
   (C) $n_c(w) = n_b(w)+1$: $1 = 0+1$. $1=1$ is true.
   (D) $n_c(w) = n_b(w) * 2$: $1 = 0 * 2 = 0$. $1=0$ is false.

2. $S \rightarrow aS \rightarrow ac$:
   $w = ac$. $n_a(w)=1, n_b(w)=0, n_c(w)=1$.
   (A) $n_a(w) > n_b(w)$: $1 > 0$ is true.
   (B) $n_a(w) > n_c(w)-2$: $1 > 1-2 = -1$. $1 > -1$ is true.
   (C) $n_c(w) = n_b(w)+1$: $1 = 0+1$. $1=1$ is true.
   (D) $n_c(w) = n_b(w) * 2$: $1 = 0$. False.

3. $S \rightarrow aSbS \rightarrow acbS \rightarrow acbc$:
   $w = acbc$. $n_a(w)=2, n_b(w)=1, n_c(w)=2$.
   (A) $n_a(w) > n_b(w)$: $2 > 1$ is true.
   (B) $n_a(w) > n_c(w)-2$: $2 > 2-2 = 0$. $2 > 0$ is true.
   (C) $n_c(w) = n_b(w)+1$: $2 = 1+1$. $2=2$ is true.
   (D) $n_c(w) = n_b(w) * 2$: $2 = 1 * 2$. $2=2$ is true.

From these examples, (A), (B), (C) appear to be true, and (D) appears true for $acbc$. However, the question asks "Which of the following statements is/are TRUE?". This implies statements that are always true for all $w \in L(G)$.

Let's re-examine $S \rightarrow aS, S \rightarrow aSbS, S \rightarrow c$.
Each 'S' can be replaced by 'c' or 'aS' or 'aSbS'.
Each 'b' is introduced only with an 'a' (as aSbS).
When $S \rightarrow aS$, $n_a$ increases by 1, $n_b$ by 0, $n_c$ by 0.
When $S \rightarrow aSbS$, $n_a$ increases by 1, $n_b$ by 1, $n_c$ by 0.
When $S \rightarrow c$, $n_a$ by 0, $n_b$ by 0, $n_c$ by 1.

Let's use the property that in every derivation, the number of 'b's must be less than or equal to the number of 'a's. Specifically, each 'b' is accompanied by an 'a'.
Let $N(X)$ be the number of $X$ non-terminals.
A string is generated by starting with $S$ and repeatedly applying rules until only terminals remain.
Each $S \rightarrow c$ adds one $c$.
Each $S \rightarrow aS$ adds one $a$.
Each $S \rightarrow aSbS$ adds two $a$'s and one $b$.

Let's consider the balance of a and b. The aSbS rule generates one b and two as. The aS rule generates one a.
The number of as must always be greater than or equal to the number of bs.
Let $k$ be the number of times the rule $S \rightarrow aSbS$ is applied.
Let $j$ be the number of times the rule $S \rightarrow aS$ is applied.
Let $m$ be the number of times the rule $S \rightarrow c$ is applied.
For a valid string $w$, the initial $S$ must eventually derive a terminal string.
Each application of $S \rightarrow c$ terminates a non-terminal $S$.
Each application of $S \rightarrow aS$ replaces an $S$ with $S$. So $N_S$ is unchanged.
Each application of $S \rightarrow aSbS$ replaces an $S$ with two $S$'s. So $N_S$ increases by 1.
This implies $n_c(w)$ is the number of times the rule $S \rightarrow c$ is applied to replace a non-terminal $S$.
If $N_{aSbS}$ is the number of times $S \rightarrow aSbS$ is used, then $N_{aSbS}$ is exactly $n_b(w)$.
Each $S \rightarrow aSbS$ adds two 'a's. Each $S \rightarrow aS$ adds one 'a'.
$n_a(w)$ = $2 \times N_{aSbS}$ + $N_{aS}$ (where $N_{aS}$ is count of $S \rightarrow aS$ rule application).
$n_b(w)$ = $N_{aSbS}$.
$n_c(w)$ = total $S$ non-terminals replaced by $c$.

In any derivation tree, the number of 'a's at the leaves will be related to 'b's.
Consider a string $w$.
The rule $S \rightarrow c$ terminates a branch, contributing one 'c'.
The rule $S \rightarrow aS$ expands, contributing one 'a'.
The rule $S \rightarrow aSbS$ expands, contributing two 'a's and one 'b'.

Let's analyze the balance of S's.
Each use of $S \rightarrow aSbS$ increases the count of S-terminals by one.
Each use of $S \rightarrow aS$ leaves it unchanged.
Each use of $S \rightarrow c$ reduces it by one.
A derivation starts with one $S$ and ends with zero $S$.
So, the number of $S \rightarrow c$ derivations must be $1 + (\text{number of } S \rightarrow aSbS \text{ derivations})$.
Therefore, $n_c(w) = n_b(w) + 1$. This is statement (C).

Let's check this again.
Start with $S$.
The number of $S$ non-terminals that eventually produce 'c' terminals, let's call it $N_c$. This $N_c$ is $n_c(w)$.
Each $S \rightarrow aSbS$ takes one $S$ and produces two $S$'s. So it adds one $S$.
Each $S \rightarrow aS$ takes one $S$ and produces one $S$. So it adds zero $S$.
Each $S \rightarrow c$ takes one $S$ and produces zero $S$. So it removes one $S$.
Let $k_1$ be the number of times $S \rightarrow aS$ is used.
Let $k_2$ be the number of times $S \rightarrow aSbS$ is used. ($k_2 = n_b(w)$)
Let $k_3$ be the number of times $S \rightarrow c$ is used. ($k_3 = n_c(w)$)
The total number of $S$ non-terminals produced must equal total consumed.
Initial $S$: 1.
Final $S$: 0.
So, number of $S$ produced by $aSbS$ ($k_2$) must equal number of $S$ consumed by $c$ ($k_3$) MINUS 1 for the initial $S$.
So $k_3 - k_2 = 1$. This means $n_c(w) - n_b(w) = 1$, or $n_c(w) = n_b(w) + 1$.
This statement (C) is ALWAYS TRUE.

Let's verify (A): $n_a(w) > n_b(w)$.
$n_a(w) = k_1 + 2k_2$. $n_b(w) = k_2$.
So we need $k_1 + 2k_2 > k_2 \implies k_1 + k_2 > 0$.
Since $w$ must be derived, at least one $S \rightarrow c$ rule must be used, or $S \rightarrow aS$ or $S \rightarrow aSbS$.
If $w=c$, then $k_1=0, k_2=0, k_3=1$. $0>0$ is false. So (A) is not always true.

Let's verify (B): $n_a(w) > n_c(w)-2$.
From $n_c(w) = n_b(w)+1$, we have $n_b(w) = n_c(w)-1$.
$n_a(w) = k_1 + 2k_2$.
So we need $k_1 + 2k_2 > (k_2+1)-2 \implies k_1 + 2k_2 > k_2-1 \implies k_1+k_2 > -1$.
Since $k_1, k_2 \ge 0$, $k_1+k_2 \ge 0$, so $k_1+k_2 > -1$ is always true.
So statement (B) is always TRUE.

Let's verify (D): $n_c(w) = n_b(w) * 2$.
For $w=c$, $n_c=1, n_b=0$. $1 \ne 0 \times 2$. So (D) is not always true.
For $w=acbc$, $n_c=2, n_b=1$. $2 = 1 \times 2$. This is true for $acbc$. But not for $c$. So not always true.

The PDF solution for Q.32 is (b). So this corresponds to $n_a(w) > n_c(w)-2$.
But $n_c(w) = n_b(w)+1$ (statement C) is also always true.
If it is a single choice answer, then there might be some interpretation for (B) that makes it more fundamentally true or a nuance.
However, if it is multiple select, then both (B) and (C) are true.

Let's recheck the problem source. Often, problems like this have a unique true statement.
$n_c(w) = n_b(w) + 1$. This is a very strong structural property for this type of grammar.
$n_a(w) > n_c(w)-2 \implies n_a(w) > n_b(w)+1-2 \implies n_a(w) > n_b(w)-1$.
This means $n_a(w) \ge n_b(w)$.
If $n_a(w)=0, n_b(w)=0$ for $w=c$. Then $0 > 0-1$ ($0 > -1$) is true.
If $n_a(w)=1, n_b(w)=0$ for $w=ac$. Then $1 > 0-1$ ($1 > -1$) is true.
If $n_a(w)=2, n_b(w)=1$ for $w=acbc$. Then $2 > 1-1$ ($2 > 0$) is true.
So (B) is also always true.

The PDF solution lists (b) as the correct answer. This suggests it's a single correct answer question, or option (c) from the problem description is not among the options or considered less true.
If it's single correct option, both (B) and (C) are always true. This is problematic.
Let's assume the question maps to (a, b, c, d) options in the PDF. So (b) is $n_a(w) > n_c(w)-2$.
And option (c) $n_c(w) = n_b(w)+1$ is also true.
This can be an issue with the question itself. However, I must choose what the PDF marks.
The PDF mentions "Answer is option (d)." but "Ans. (b)" is listed. This is inconsistent. I will use the (b) provided in "Ans. (b)".
This means it is $n_a(w) > n_c(w)-2$.
===END_Q52===

To determine the language generated by $G$, we first analyze the production rules for the non-terminal $X$:
$X \rightarrow aX \mid Xb \mid a \mid b$
This defines the language $L(X) = a^*(a+b)b^+ \cup a^+b^* = a^*(a+b)b^*$. Essentially, $X$ generates any string consisting of at least one terminal ($a$ or $b$).

Next, we analyze the productions for the starting non-terminal $S$:
$S \rightarrow aSb \mid X$
This rule recursively adds matching $a$'s at the beginning and $b$'s at the end of any string generated by $X$. This corresponds to the form $a^n X b^n$ for $n \ge 0$. Substituting $L(X)$:
$L(G) = \{ a^n w b^n \mid w \in a^*(a+b)b^*, n \ge 0 \}$
Since $w$ already contains an arbitrary number of $a$'s and $b$'s, the prefix $a^n$ and suffix $b^n$ are absorbed into the $a^*$ and $b^*$ components of the regular expression. Specifically, $a^n a^* (a+b) b^* b^n$ simplifies to $a^* (a+b) b^*$. Thus, $L(G) = a^*(a+b)b^*$, which is a regular language.