Context Free Grammars Questions and Answers

Q: Which of the following languages is generated by the given grammar?\[ S \rightarrow aS \mid bS \mid \varepsilon \]

The grammar generates \(\{a,b\}^{*}\).\(S \rightarrow aS \mid bS \mid \varepsilon\) lets each step add either an a or a b at the front and continue, or stop. Any string of a's and b's in any order, including the empty string, can be built letter by letter, so the language is all strings over \(\{a, b\}\).\(\{a^{n}b^{m}\}\) forces all a's before the b's, but the grammar also gives ba. Nothing in the grammar counts letters, so the 'equal number' and \(a^{n}b^{n}\) options are far too narrow, and the grammar also produces strings like aab.

Q: Consider the following context-free grammars:\(G_{1}\): \(S \rightarrow aS \mid B\), \(B \rightarrow b \mid bB\)\(G_{2}\): \(S \rightarrow aA \mid bB\), \(A \rightarrow aA \mid B \mid \varepsilon\), \(B \rightarrow bB \mid \varepsilon\)Which one of the following pairs of languages is generated by \(G_{1}\) and \(G_{2}\), respectively?

\(G_{1}\) and \(G_{2}\) generate \(\{a^{m}b^{n} \mid m \ge 0 \text{ and } n \gt 0\}\) and \(\{a^{m}b^{n} \mid m \gt 0 \text{ or } n \gt 0\}\).\(G_{1}\): \(S \rightarrow aS \mid B\) produces any number of a's, possibly none, then switches to \(B\). \(B \rightarrow b \mid bB\) produces one or more b's. So \(m \ge 0\) and \(n \gt 0\).\(G_{2}\): \(S\) must start with a (then \(A\)) or b (then \(B\)). From \(A\), any number of further a's, then optionally \(B\), which gives any number of b's including none. From the b start, only b's follow. So every string is \(a^{m}b^{n}\) with at least one symbol: \(m \gt 0\) or \(n \gt 0\). The empty string is excluded because \(S\) has no \(\varepsilon\) rule.The other options get one of these conditions wrong, for example 'm \(\gt\) 0 and n \(\gt\) 0' for \(G_{2}\) would exclude 'a' and 'b', which \(G_{2}\) generates.

Q: Consider the following context-free grammar \(G\), where \(S\), \(A\), and \(B\) are the variables (non-terminals), \(a\) and \(b\) are the terminal symbols, \(S\) is the start variable, and the rules of \(G\) are described as:\(S \rightarrow aaB \mid Abb\)\(A \rightarrow a \mid aA\)\(B \rightarrow b \mid bB\)Which ONE of the languages \(L(G)\) is accepted by \(G\)?

The language is \(\{a^{2}b^{n} \mid n \ge 1\} \cup \{a^{n}b^{2} \mid n \ge 1\}\).B generates \(b^{n}\) for \(n \ge 1\) and A generates \(a^{n}\) for \(n \ge 1\). The first rule \(S \rightarrow aaB\) therefore gives exactly two a's followed by one or more b's, \(a^{2}b^{n}\). The second rule \(S \rightarrow Abb\) gives one or more a's followed by exactly two b's, \(a^{n}b^{2}\). The language is the union of the two.The other options demand a link between the numbers of a's and b's (such as \(a^{n}b^{n}\) or \(a^{n}b^{2n}\)), but in this grammar the a's and b's are generated by separate rules with nothing tying the counts together. For example aabbb is in L(G) but has unequal counts.

Q: Language \(L_{1}\) is defined by the grammar: \(S_{1} \rightarrow aS_{1}b \mid \varepsilon\)Language \(L_{2}\) is defined by the grammar: \(S_{2} \rightarrow abS_{2} \mid \varepsilon\)Consider the following statements:\(P\): \(L_{1}\) is regular\(Q\): \(L_{2}\) is regularWhich one of the following is TRUE?

P is false and Q is true.\(S_{1} \rightarrow aS_{1}b \mid \varepsilon\) generates \(L_{1} = \{a^{n}b^{n} : n \ge 0\}\). Recognising it needs to count the a’s to match the b’s, and the pumping lemma shows it is not regular, so P is false.\(S_{2} \rightarrow abS_{2} \mid \varepsilon\) generates \(L_{2} = (ab)^{*}\), any number of repetitions of the string ab. It is a right-linear grammar, and the regular expression \((ab)^{*}\) describes it, so Q is true.Options calling \(L_{1}\) regular, or \(L_{2}\) non-regular, are therefore wrong.

Q: Consider the context-free grammar \(G\) below\(S \to aSb \mid X\)\(X \to aX \mid Xb \mid a \mid b\),where \(S\) and \(X\) are non-terminals, and \(a\) and \(b\) are terminal symbols. The starting non-terminal is \(S\).Which one of the following statements is CORRECT?

The language is \(a^{*}(a+b)b^{*}\).Start with X. The rules X \(\to\) aX and X \(\to\) Xb add any number of a's on the left and b's on the right, and the derivation ends with a single a or b in the middle. So X generates \(a^{*}(a+b)b^{*}\): some a's, then one a or b, then some b's.S \(\to\) aSb wraps that in n further a's and n further b's, giving \(a^{n}a^{*}(a+b)b^{*}b^{n}\), which is still \(a^{*}(a+b)b^{*}\). The matching counts add nothing, because X can already produce any numbers of a's and b's on its own.\((a+b)^{*}\) includes the empty string and strings like ba, which G cannot produce, since every b comes after every a. \(a^{*}b^{*}(a+b)\) contains bba, which G cannot generate. And since the language is given by a regular expression, it is regular.

Q: Consider the context free Grammar with 7 (seven) productions.S \(\rightarrow\) Aa / BB \(\rightarrow\) A / bbA \(\rightarrow\) a / bc / BAfter removing all unit productions the resulting equivalent grammar will contain ................................. productions.

The resulting grammar has 10 productions.The unit productions are S \(\to\) B, B \(\to\) A and A \(\to\) B, so B and A can each derive the other, and S can derive both. Removing them, each variable takes the non-unit productions of every variable it can reach through unit productions. The non-unit productions are S \(\to\) Aa, B \(\to\) bb and A \(\to\) a | bc.S \(\to\) Aa | bb | a | bc: 4 productionsB \(\to\) bb | a | bc: 3 productionsA \(\to\) a | bc | bb: 3 productionsThat makes 4 + 3 + 3 = 10. Counts such as 11, 12 or 18 come from keeping a unit production or duplicating a substituted one.

Q: Consider the context free grammar with productions :\(S \rightarrow ABa\)\(A \rightarrow aab\)\(B \rightarrow Ac\)After constructing an equivalent grammar in Chomsky Normal form, the resulting grammar will contain ..............productions.

The Chomsky Normal Form grammar has 8 productions.In CNF every production is either \(A \rightarrow BC\) or \(A \rightarrow a\). Introduce a variable for each terminal and break the long right-hand sides into pairs:\[ \begin{aligned} S &\rightarrow A X_1, \quad X_1 \rightarrow B T_a \\ A &\rightarrow T_a X_2, \quad X_2 \rightarrow T_a T_b \\ B &\rightarrow A T_c \\ T_a &\rightarrow a, \ T_b \rightarrow b, \ T_c \rightarrow c \end{aligned} \]That is 2 for S, 2 for A, 1 for B and 3 terminal productions: 8 in all. The grammar has no null or unit productions to remove first. Six productions are too few once the two length-3 right-hand sides are split into pairs, and 9 or 10 would include productions CNF does not need.

Q: The language \(L = \{a^{n}b^{n}c^{n} : n \ge 1\}\) is a content sensitive language. Give a content sensitive grammar for L :

The correct grammar is option (B).Start with \(S \to abc\) for \(n = 1\). For larger \(n\), \(S \to aAbc\) begins a derivation, and the rules \(Ab \to bA\) and \(Ac \to Bbcc\) move \(A\) to the right past the b and turn it into one more b and c. Then \(bB \to Bb\) carries \(B\) back left to the a's, and \(aB \to aa\) ends with one more a. For \(n = 2\):\[ \begin{aligned} S &\Rightarrow aAbc \Rightarrow abAc \\ &\Rightarrow abBbcc \Rightarrow aBbbcc \Rightarrow aabbcc \end{aligned} \]The rule \(aB \to aaA\) restarts the cycle for larger \(n\). Option A has no rule giving \(abc\), and its \(S \to aSbc\) puts the b and c in the wrong places (it derives \(aaabbccbc\)). Option C has \(Ab \to Ab\), which changes nothing, so \(A\) never reaches the c. Option D drops the contexts: \(S \Rightarrow aAbc \Rightarrow aBbccbc \Rightarrow aabccbc\), which is not of the form \(a^{n}b^{n}c^{n}\).

Which of the following languages is generated by the given grammar?

\[ S \rightarrow aS \mid bS \mid \varepsilon \]

A.\(\{a^{n}b^{m} \mid n,m \ge 0\}\)
B.\(\{w \in \{a,b\}^{*} \mid w\) has equal number of a’s and b’s \(\}\)
C.\(\{a^{n} \mid n \ge 0\}\) \(\cup\) \(\{b^{n} \mid n \ge 0\}\) \(\cup\) \(\{a^{n}b^{n} \mid n \ge 0\}\)
D.\(\{a,b\}^{*}\)

Exam Year(s)

GATE CS - 2016,

Answer: D

The grammar generates \(\{a,b\}^{*}\).

\(S \rightarrow aS \mid bS \mid \varepsilon\) lets each step add either an a or a b at the front and continue, or stop. Any string of a's and b's in any order, including the empty string, can be built letter by letter, so the language is all strings over \(\{a, b\}\).

\(\{a^{n}b^{m}\}\) forces all a's before the b's, but the grammar also gives ba. Nothing in the grammar counts letters, so the 'equal number' and \(a^{n}b^{n}\) options are far too narrow, and the grammar also produces strings like aab.

Discuss in Forum

Consider the following context-free grammars:

\(G_{1}\): \(S \rightarrow aS \mid B\), \(B \rightarrow b \mid bB\)
\(G_{2}\): \(S \rightarrow aA \mid bB\), \(A \rightarrow aA \mid B \mid \varepsilon\), \(B \rightarrow bB \mid \varepsilon\)

Which one of the following pairs of languages is generated by \(G_{1}\) and \(G_{2}\), respectively?

A.\(\{a^{m}b^{n} \mid m \gt 0 \text{ or } n \gt 0\}\) and \(\{a^{m}b^{n} \mid m \gt 0 \text{ and } n \gt 0\}\)
B.\(\{a^{m}b^{n} \mid m \gt 0 \text{ and } n \gt 0\}\) and \(\{a^{m}b^{n} \mid m \gt 0 \text{ or } n \ge 0\}\)
C.\(\{a^{m}b^{n} \mid m \ge 0 \text{ or } n \gt 0\}\) and \(\{a^{m}b^{n} \mid m \gt 0 \text{ and } n \gt 0\}\)
D.\(\{a^{m}b^{n} \mid m \ge 0 \text{ and } n \gt 0\}\) and \(\{a^{m}b^{n} \mid m \gt 0 \text{ or } n \gt 0\}\)

Exam Year(s)

GATE CS - 2016,

Answer: D

\(G_{1}\) and \(G_{2}\) generate \(\{a^{m}b^{n} \mid m \ge 0 \text{ and } n \gt 0\}\) and \(\{a^{m}b^{n} \mid m \gt 0 \text{ or } n \gt 0\}\).

\(G_{1}\): \(S \rightarrow aS \mid B\) produces any number of a's, possibly none, then switches to \(B\). \(B \rightarrow b \mid bB\) produces one or more b's. So \(m \ge 0\) and \(n \gt 0\).

\(G_{2}\): \(S\) must start with a (then \(A\)) or b (then \(B\)). From \(A\), any number of further a's, then optionally \(B\), which gives any number of b's including none. From the b start, only b's follow. So every string is \(a^{m}b^{n}\) with at least one symbol: \(m \gt 0\) or \(n \gt 0\). The empty string is excluded because \(S\) has no \(\varepsilon\) rule.

The other options get one of these conditions wrong, for example 'm \(\gt\) 0 and n \(\gt\) 0' for \(G_{2}\) would exclude 'a' and 'b', which \(G_{2}\) generates.

Discuss in Forum

Consider the following context-free grammar \(G\), where \(S\), \(A\), and \(B\) are the variables (non-terminals), \(a\) and \(b\) are the terminal symbols, \(S\) is the start variable, and the rules of \(G\) are described as:

\(S \rightarrow aaB \mid Abb\)
\(A \rightarrow a \mid aA\)
\(B \rightarrow b \mid bB\)

Which ONE of the languages \(L(G)\) is accepted by \(G\)?

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\}\)

Exam Year(s)

GATE CS - 2025,

Answer: A

The language is \(\{a^{2}b^{n} \mid n \ge 1\} \cup \{a^{n}b^{2} \mid n \ge 1\}\).

B generates \(b^{n}\) for \(n \ge 1\) and A generates \(a^{n}\) for \(n \ge 1\). The first rule \(S \rightarrow aaB\) therefore gives exactly two a's followed by one or more b's, \(a^{2}b^{n}\). The second rule \(S \rightarrow Abb\) gives one or more a's followed by exactly two b's, \(a^{n}b^{2}\). The language is the union of the two.

The other options demand a link between the numbers of a's and b's (such as \(a^{n}b^{n}\) or \(a^{n}b^{2n}\)), but in this grammar the a's and b's are generated by separate rules with nothing tying the counts together. For example aabbb is in L(G) but has unequal counts.

Discuss in Forum

Language \(L_{1}\) is defined by the grammar: \(S_{1} \rightarrow aS_{1}b \mid \varepsilon\)
Language \(L_{2}\) is defined by the grammar: \(S_{2} \rightarrow abS_{2} \mid \varepsilon\)

Consider the following statements:

\(P\): \(L_{1}\) is regular
\(Q\): \(L_{2}\) is regular

Which one of the following is TRUE?

A.Both \(P\) and \(Q\) are true
B.\(P\) is true and \(Q\) is false
C.\(P\) is false and \(Q\) is true
D.Both \(P\) and \(Q\) are false

Exam Year(s)

GATE CS - 2016,

Answer: C

P is false and Q is true.

\(S_{1} \rightarrow aS_{1}b \mid \varepsilon\) generates \(L_{1} = \{a^{n}b^{n} : n \ge 0\}\). Recognising it needs to count the a’s to match the b’s, and the pumping lemma shows it is not regular, so P is false.

\(S_{2} \rightarrow abS_{2} \mid \varepsilon\) generates \(L_{2} = (ab)^{*}\), any number of repetitions of the string ab. It is a right-linear grammar, and the regular expression \((ab)^{*}\) describes it, so Q is true.

Options calling \(L_{1}\) regular, or \(L_{2}\) non-regular, are therefore wrong.

Discuss in Forum

Consider the context-free grammar \(G\) below

\(S \to aSb \mid X\)
\(X \to aX \mid Xb \mid a \mid b\),

where \(S\) and \(X\) are non-terminals, and \(a\) and \(b\) are terminal symbols. The starting non-terminal is \(S\).

Which one of the following statements is CORRECT?

A.The language generated by \(G\) is \((a+b)^{*}\)
B.The language generated by \(G\) is \(a^{*}(a+b)b^{*}\)
C.The language generated by \(G\) is \(a^{*}b^{*}(a+b)\)
D.The language generated by \(G\) is not a regular language

Exam Year(s)

GATE CS - 2023,

Answer: B

The language is \(a^{*}(a+b)b^{*}\).

Start with X. The rules X \(\to\) aX and X \(\to\) Xb add any number of a's on the left and b's on the right, and the derivation ends with a single a or b in the middle. So X generates \(a^{*}(a+b)b^{*}\): some a's, then one a or b, then some b's.

S \(\to\) aSb wraps that in n further a's and n further b's, giving \(a^{n}a^{*}(a+b)b^{*}b^{n}\), which is still \(a^{*}(a+b)b^{*}\). The matching counts add nothing, because X can already produce any numbers of a's and b's on its own.

\((a+b)^{*}\) includes the empty string and strings like ba, which G cannot produce, since every b comes after every a. \(a^{*}b^{*}(a+b)\) contains bba, which G cannot generate. And since the language is given by a regular expression, it is regular.

Discuss in Forum

Consider the context free Grammar with 7 (seven) productions.

S \(\rightarrow\) Aa / B
B \(\rightarrow\) A / bb
A \(\rightarrow\) a / bc / B

After removing all unit productions the resulting equivalent grammar will contain ................................. productions.

A.18
B.12
C.10
D.11

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: C

The resulting grammar has 10 productions.

The unit productions are S \(\to\) B, B \(\to\) A and A \(\to\) B, so B and A can each derive the other, and S can derive both. Removing them, each variable takes the non-unit productions of every variable it can reach through unit productions. The non-unit productions are S \(\to\) Aa, B \(\to\) bb and A \(\to\) a | bc.

S \(\to\) Aa | bb | a | bc: 4 productions
B \(\to\) bb | a | bc: 3 productions
A \(\to\) a | bc | bb: 3 productions

That makes 4 + 3 + 3 = 10. Counts such as 11, 12 or 18 come from keeping a unit production or duplicating a substituted one.

Discuss in Forum

Consider the context free grammar with productions :

\(S \rightarrow ABa\)
\(A \rightarrow aab\)
\(B \rightarrow Ac\)

After constructing an equivalent grammar in Chomsky Normal form, the resulting grammar will contain ..............productions.

A.10
B.08
C.06
D.09

Exam Year(s)

MH SET - 2023, SET Exam - 2023,

Answer: B

The Chomsky Normal Form grammar has 8 productions.

In CNF every production is either \(A \rightarrow BC\) or \(A \rightarrow a\). Introduce a variable for each terminal and break the long right-hand sides into pairs:

\[ \begin{aligned} S &\rightarrow A X_1, \quad X_1 \rightarrow B T_a \\ A &\rightarrow T_a X_2, \quad X_2 \rightarrow T_a T_b \\ B &\rightarrow A T_c \\ T_a &\rightarrow a, \ T_b \rightarrow b, \ T_c \rightarrow c \end{aligned} \]

That is 2 for S, 2 for A, 1 for B and 3 terminal productions: 8 in all. The grammar has no null or unit productions to remove first. Six productions are too few once the two length-3 right-hand sides are split into pairs, and 9 or 10 would include productions CNF does not need.

Discuss in Forum

The language \(L = \{a^{n}b^{n}c^{n} : n \ge 1\}\) is a content sensitive language. Give a content sensitive grammar for L :

A.S → aSbc | aAbc / Ab → bA / Ac → Bbcc / bB → Bb / aB → aa | aaA
B.S → abc | aAbc / Ab → bA / Ac → Bbcc / bB → Bb / aB → aa | aaA
C.S → abc | aAbc / Ab → Ab / Ac → Bbcc / bB → Bb / aB → aa | aaA
D.S → abc | aAbc / A → bA / A → Bbcc / bB → Bb / aB → aa | aaA

Exam Year(s)

MH SET - 2025, SET Exam - 2025,

Answer: B

The correct grammar is option (B).

Start with \(S \to abc\) for \(n = 1\). For larger \(n\), \(S \to aAbc\) begins a derivation, and the rules \(Ab \to bA\) and \(Ac \to Bbcc\) move \(A\) to the right past the b and turn it into one more b and c. Then \(bB \to Bb\) carries \(B\) back left to the a's, and \(aB \to aa\) ends with one more a. For \(n = 2\):

\[ \begin{aligned} S &\Rightarrow aAbc \Rightarrow abAc \\ &\Rightarrow abBbcc \Rightarrow aBbbcc \Rightarrow aabbcc \end{aligned} \]

The rule \(aB \to aaA\) restarts the cycle for larger \(n\). Option A has no rule giving \(abc\), and its \(S \to aSbc\) puts the b and c in the wrong places (it derives \(aaabbccbc\)). Option C has \(Ab \to Ab\), which changes nothing, so \(A\) never reaches the c. Option D drops the contexts: \(S \Rightarrow aAbc \Rightarrow aBbccbc \Rightarrow aabccbc\), which is not of the form \(a^{n}b^{n}c^{n}\).

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Context Free Grammars Questions and Answers || Context Free Grammars MCQ Questions and Answers || Context Free Grammars GK Questions and Answers || Context Free Grammars GK MCQ Questions || Context Free Grammars Multiple Choice Questions and Answers || Context Free Grammars GK || GK on Context Free Grammars || Theory of Computation Questions and Answers || Theory of Computation MCQ Questions and Answers || Theory of Computation GK Questions and Answers || GK on Theory of Computation

Context Free Grammars Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications