Q.1 Which of the following is a context-free grammar production rule?
A -> aB
AB -> a
a -> B
AB -> ε
Explanation - In context-free grammars, the left-hand side of a production must be a single non-terminal.
Correct answer is: A -> aB
Q.2 Which language is generated by the grammar S -> aSb | ε?
{a^n b^n | n ≥ 0}
{a^n b^m | n, m ≥ 0}
{a^n | n ≥ 0}
{a^n b^n c^n | n ≥ 0}
Explanation - The grammar generates strings where the number of a's equals the number of b's.
Correct answer is: {a^n b^n | n ≥ 0}
Q.3 Which of the following is true about context-free languages?
All regular languages are context-free
All context-free languages are regular
No regular languages are context-free
Context-free languages are not closed under union
Explanation - Every regular language can be described by a context-free grammar, but not every context-free language is regular.
Correct answer is: All regular languages are context-free
Q.4 Which normal form requires all productions to be of the form A -> BC or A -> a?
Chomsky Normal Form
Greibach Normal Form
Kleene Normal Form
Backus-Naur Form
Explanation - Chomsky Normal Form restricts productions to either two non-terminals or a single terminal.
Correct answer is: Chomsky Normal Form
Q.5 In a CFG, which symbol cannot appear on the left-hand side of a production?
Terminal
Non-terminal
Start symbol
Epsilon
Explanation - Only non-terminal symbols can appear on the left-hand side of a production in a CFG.
Correct answer is: Terminal
Q.6 Which of the following languages is not context-free?
{a^n b^n | n ≥ 0}
{a^n b^n c^n | n ≥ 0}
{a^i b^j | i,j ≥ 0}
{ε}
Explanation - The language {a^n b^n c^n} requires counting three types of symbols, which cannot be done with a CFG.
Correct answer is: {a^n b^n c^n | n ≥ 0}
Q.7 What is the purpose of the start symbol in a CFG?
It generates terminal strings
It generates non-terminals only
It terminates derivations
It is used for simplification
Explanation - The start symbol is used to derive strings of the language by eventually producing terminal symbols.
Correct answer is: It generates terminal strings
Q.8 Which of the following operations is CFL closed under?
Intersection with a regular language
Intersection with another CFL
Complement
Set difference
Explanation - Context-free languages are closed under union and concatenation, and intersection with regular languages, but not general intersection or complement.
Correct answer is: Intersection with a regular language
Q.9 Which derivation technique produces the leftmost non-terminal first?
Leftmost derivation
Rightmost derivation
Bottom-up parsing
Top-down parsing
Explanation - Leftmost derivation always replaces the leftmost non-terminal at each step.
Correct answer is: Leftmost derivation
Q.10 What does the language L(G) denote for a CFG G?
Set of all non-terminals
Set of all terminals
Set of all strings generated by G
Set of all production rules
Explanation - L(G) is the language generated by the grammar G, i.e., all strings of terminals derivable from the start symbol.
Correct answer is: Set of all strings generated by G
Q.11 Which CFG rule generates ε directly?
A -> ε
A -> B
a -> ε
A -> aB
Explanation - Only a non-terminal can produce ε in a CFG.
Correct answer is: A -> ε
Q.12 Which type of CFG production is used in Greibach Normal Form?
A -> aα
A -> BC
A -> ε only
A -> B | a
Explanation - In Greibach Normal Form, the leftmost symbol of the production is a terminal, followed by zero or more non-terminals.
Correct answer is: A -> aα
Q.13 For the CFG S -> aSb | ε, what is the derivation of 'aaabbb'?
S -> aS b -> aaS bb -> aaaS bbb -> aaabbb
S -> aSb -> aaSb -> aaaSb -> aaabbb
S -> aSb -> aabSbb -> aaabbb
S -> aSb -> aaSb -> ab
Explanation - Each 'a' adds a matching 'b', and the empty string terminates the derivation.
Correct answer is: S -> aS b -> aaS bb -> aaaS bbb -> aaabbb
Q.14 Which of these is NOT a property of context-free grammars?
Left recursion
Ambiguity
Right recursion
Closure under intersection with any CFL
Explanation - CFLs are not closed under general intersection, though they may have left/right recursion or ambiguity.
Correct answer is: Closure under intersection with any CFL
Q.15 What is ambiguity in a CFG?
A string has multiple derivations
A terminal symbol cannot be derived
A non-terminal has no production
Grammar is not in CNF
Explanation - Ambiguity occurs if a string can have more than one leftmost or rightmost derivation in a grammar.
Correct answer is: A string has multiple derivations
Q.16 Which parsing technique is suitable for any context-free language?
CYK algorithm
LL(1) parsing
LR(0) parsing
Recursive descent parsing
Explanation - CYK parsing works for all CFGs in Chomsky Normal Form.
Correct answer is: CYK algorithm
Q.17 Which statement is true about left recursion in CFGs?
It must be eliminated for top-down parsing
It is required for CNF
It makes CFGs regular
It cannot generate terminals
Explanation - Left recursion causes infinite recursion in top-down parsers, so it needs to be removed.
Correct answer is: It must be eliminated for top-down parsing
Q.18 Which CFG generates palindromes over {a, b}?
S -> aSa | bSb | a | b | ε
S -> aSb | ε
S -> AB
S -> aAbB
Explanation - The grammar correctly produces palindromes by mirroring a or b around S, including the empty string.
Correct answer is: S -> aSa | bSb | a | b | ε
Q.19 What is the result of eliminating ε-productions from a CFG?
No ε can be derived
All non-terminals are removed
All terminals are removed
Grammar becomes regular
Explanation - Eliminating ε-productions removes productions that derive the empty string, except possibly for the start symbol.
Correct answer is: No ε can be derived
Q.20 Which of these is a typical example of a non-context-free language?
{a^n b^n c^n | n ≥ 0}
{a^n b^n | n ≥ 0}
{a^i b^j | i,j ≥ 0}
{ε}
Explanation - Requires counting three different symbols, which is beyond the power of CFGs.
Correct answer is: {a^n b^n c^n | n ≥ 0}
Q.21 In CFG simplification, what is a unit production?
A -> B
A -> a
A -> BC
A -> ε
Explanation - A unit production has a single non-terminal on the right-hand side.
Correct answer is: A -> B
Q.22 Which of the following is a method to remove ambiguity from CFG?
Redesigning the grammar
Adding ε-productions
Adding unit productions
Converting to CNF
Explanation - Ambiguity is resolved by restructuring the grammar to ensure each string has a unique derivation.
Correct answer is: Redesigning the grammar
Q.23 What is the language of the CFG: S -> 0S1 | 01?
{0^n 1^n | n ≥ 1}
{01}
{0^n 1^n | n ≥ 0}
{0^i 1^j | i,j ≥ 0}
Explanation - The CFG generates strings with equal numbers of 0s and 1s, starting with '01' as base.
Correct answer is: {0^n 1^n | n ≥ 1}
Q.24 Which of these is a valid method to convert a CFG to CNF?
Eliminate ε-productions and unit productions
Add ambiguity
Add more terminals on LHS
Introduce left recursion
Explanation - Conversion to CNF involves eliminating ε-productions, unit productions, and reducing RHS to 2 non-terminals or a terminal.
Correct answer is: Eliminate ε-productions and unit productions
Q.25 Which of the following languages is inherently ambiguous?
{a^i b^j c^k | i=j or j=k}
{a^n b^n | n ≥ 0}
{a^n b^m | n,m ≥ 0}
{ε}
Explanation - Some strings can be derived in multiple ways due to overlapping conditions, making the language inherently ambiguous.
Correct answer is: {a^i b^j c^k | i=j or j=k}