Normal Forms & BNF MCQs: 10 Solved Grammar Questions with Explanations

CNF, GNF, BNF, parse-tree height, and derivation length can look like a list of definitions until one option changes a symbol and invalidates an entire production. Each question tests a definition against an actual production or a numeric tree count.

Attempt each question before reading its explanation, and write one reason beside your choice. Questions 1 to 6, 9 and 10 open on their own solved-question pages, and Questions 7 and 8 are practised on the Normal Forms & BNF practice page. For the wider syllabus around this topic, start from UGC NET CS Exam Preparation.

CNF, GNF, and BNF Rules to Check Before the Questions

For S -> aAB | b, A -> a, B -> b, every alternative starts with a terminal and any remainder contains only variables. It is already in GNF.

For CNF, introduce X_a -> a and C -> AB: S -> X_a C | b, X_a -> a, C -> AB, A -> a, B -> b. The first and third right-hand sides contain two variables; all others contain one terminal. If CFG and normal-form restrictions still blur together, revise Context-Free Grammar MCQs: 11 Solved CFG, CFL, PDA Questions.

BNF sits at a different level from CNF and GNF. It is a way of writing a grammar down, not a restriction on its productions: <expr> ::= <expr> + <term> | <term> and E -> E + T | T are the same two rules in two notations. A grammar written in BNF can therefore be left-recursive, ambiguous, or already in CNF, and converting it still means rewriting the productions rather than changing the brackets. Options that offer BNF as a third normal form beside CNF and GNF are testing exactly this distinction.

Normal-Form MCQs 1-2: CNF Yield and GNF Recognition

Question 1

The maximum yield length of the following CNF CFG is

S → AB

A → CD

B → e

C → a

D → b

• A. 8

• B. 7

• C. 4

• D. 3

Correct answer: D. 3.

Here e is a terminal, not epsilon. S => AB => CDB => aDB => abB => abe, so the yield length is 3. No nonterminal branches. Open the solved question.

Question 2

Which one of the following is not a Greibach Normal form grammar?

(i)                     (ii)                 (iii)
S → a / bA / aA / bB     S → a / aA / AB      S → a / A / aA
A → a                   A → a                A → a
B → b                   B → b

• A. (i) and (ii)

• B. (i) and (iii)

• C. (ii) and (iii)

• D. (i), (ii) and (iii)

Correct answer: C. (ii) and (iii).

Grammar (i) starts with a terminal throughout. Grammar (ii) has S -> AB, and (iii) has S -> A; both variable-leading rules fail GNF. Open the solved question.

Greibach and Chomsky Normal Form MCQs 3-4: Language Shape and Parse-Tree Path Length

Question 3

The Greibach normal form grammar for the language L = {aⁿ bⁿ⁺¹ | n ≥ 0} is

• A. S → aSB
B → bB / λ

• B. S → aSB
B → bB / b

• C. S → aSB / b
B → b

• D. S → aSb / b

Correct answer: C. S -> aSB / b, B -> b.

Option C is GNF. Test it: n=0 gives S => b; n=1 gives S => aSB => abB => abb; n=2 gives S => aSB => aaSBB => aabBB => aabbB => aabbb. Each is a^n b^(n+1). Open the solved question.

Question 4

If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i, then the word w is of length

• A. no greater than 2^(i+1)

• B. no greater than 2^i

• C. no greater than 2^(i−1)

• D. no greater than i

Correct answer: C. no greater than 2^(i-1).

A CNF tree branches two ways at every variable, so if no path exceeds i edges the variables occupy at most i-1 levels of branching before the final terminal step, leaving at most 2^(i-1) leaves. Take i=3: S -> AB, A -> CD, B -> EF with C, D, E and F each rewriting to one terminal gives a longest path of 3 edges and exactly 2^2 = 4 terminals, which is the tight case. Open the solved question.

Chomsky Normal Form MCQs 5-6: Production Counts and Height Bounds

Question 5

To obtain a string of n terminals from a given Chomsky normal form grammar, the number of productions to be used is

• A. 2n-1

• B. 2n

• C. n + 1

• D. n²

Correct answer: A. 2n-1.

A binary CNF tree has n-1 binary expansions plus n terminal productions, totalling 2n-1.

For n=4, use S -> AB, A -> a, B -> CD, C -> b, D -> EF, E -> c, F -> d. Then S => AB => aB => aCD => abD => abEF => abcF => abcd: three binary plus four terminal steps, so 7=2(4)-1. Open the solved question.

Question 6

Let \(G = (V,T,S,P)\) be a context-free grammer such that every one of its productions is of the form \(A → v,\) with \(|v| = K > 1\) . The derivation tree for any \(W∈L(G)\) has a height \(h\) such that

• A. \(\log_{K}|W| \leq h \leq \log_{K}\left(\frac{|W|-1}{K-1}\right)\)

• B. \(\log_{K}|W| \leq h \leq \log_{K}(K|W|)\)

• C. \(\log_{K}|W| \leq h \leq K\log_{K}|W|\)

• D. \(\log_{K}|W| \leq h \leq \frac{|W|-1}{K-1}\)

Correct answer: D. \(\log_{K}|W| \leq h \leq (|W|-1)/(K-1)\).

At most K^h leaves gives h >= log_K |W|. Skewed growth adds K-1 leaves per expansion, giving h <= (|W|-1)/(K-1).

For K=3, |W|=13, the bounds are log_3 13 ≈ 2.335 and (13-1)/(3-1)=6. Integer heights are 3 through 6, matching D. Open the solved question.

Grammar-Transformation MCQs 7-8: GNF Derivations, Epsilon Rules, and Left Recursion

Question 7

Consider the grammar G

S → xSy | xAy | ϵ

A → zA | ϵ

We convert the above Grammar to GNF. The number of steps required in GNF to derive the string “xxzzzyy”.

• A. 5

• B. 6

• C. 7

• D. 8

Correct answer: C. 7.

xxzzzyy has 2+3+2=7 terminals. One GNF step contributes one terminal, so the converted grammar needs seven steps, not the displayed grammar's rewrite count.

Question 8

Choose the Correct statement(s) from the following.

• A. ϵ-production removal from grammar is always possible

• B. We can't convert every CFG into CNF if it has ϵ-production

• C. Number of LMDs and RMDs are always equal for a particular string from a given grammar.

• D. There is no CFGs from which we can't remove left recursion

Correct answer: A, C, and D.

This is the one MSQ. A uses epsilon elimination while retaining an allowed start-symbol epsilon rule when needed. That exception still permits CNF conversion, so B is false.

Each parse tree yields one LMD and one RMD, so C is true. D's double negative selects universal left-recursion removal under the item's convention.

Mixed Normal-Form MCQs 9-10: Match the Grammar and Bound the Conversion

Question 9

Match List I with List II Choose the correct answer from the options given below :

List I: Production Rules                         List II: Grammar

A. S → XY                                           I. Greibach Normal Form
   X → 0
   Y → 1

B. S → aS | bSS | c                              II. Context Sensitive Grammar

C. S → AB                                         III. Chomsky Normal Form
   A → 0A | 1A | 0
   B → 0A

D. S → aAbc                                      IV. S-Grammar
   Ab → bA
   Ac → Bbcc
   bB → Bb
   aB → aa | aaA

• A. A ‐ III, B ‐I , C ‐ IV, D ‐ II

• B. A ‐ III, B ‐II , C ‐ I, D ‐ IV

• C. A ‐ III, B ‐IV, C ‐ I, D ‐ II

• D. A ‐ IV, B ‐III , C ‐ I, D ‐ II

Correct answer: C. A-III, B-IV, C-I, D-II.

A is CNF, B fits the S-grammar pattern, and D is context-sensitive because its rules preserve context and do not shorten strings.

Pair C is listed as Greibach Normal Form even though S -> AB is not terminal-leading on its own. Substituting A's alternatives gives S -> 0AB | 1AB | 0B, and with A -> 0A | 1A | 0 and B -> 0A every rule then begins with a terminal. Open the solved question.

Question 10

Let \(G=(V,T,S,P)\) be any context-free grammar without any \(\lambda-\) productions or unit productions. Let \(K\) be the maximum number of symbols on the right of any production in \(P\) . The maximum number of production rules for any equivalent grammar in Chomsky normal form is given by:

• A. \((K-1)|P| + |T| - 1\)

• B. \((K-1)|P| + |T|\)

• C. \(K|P| + |T| - 1\)

• D. \(K|P| + |T|\)

Correct answer: B. \((K-1)|P| + |T|\).

A length-K right-hand side needs at most K-1 binary rules. Across |P| productions and terminal helpers, the bound is (K-1)|P|+|T|.

For K=4, |P|=6, |T|=3, the bound is (4-1) x 6 + 3 = 21, option B. Open the solved question.

How Normal Forms and BNF Questions Are Tested: Short Version and Next Step

Use five checks: first right-hand-side symbol for GNF, right-hand-side shape for CNF, leaves plus binary nodes for the 2n-1 count, target terminals for GNF derivation steps, and ::= for BNF, which marks a notation rather than a normal form.

The answers are 1-D, 2-C, 3-C, 4-C, 5-A, 6-D, 7-C, 8-A/C/D, 9-C, 10-B.

Try a two-minute drill. For n=6, CNF uses 2(6)-1=11 productions. A nine-terminal GNF word takes 9 steps. For K=3, |P|=5, |T|=4, the conversion bound is (3-1) x 5 + 4 = 14. Recompute each first.

Next, try Parsing MCQs: 12 Solved Top-Down and Bottom-Up Questions, or take NTA-UGC-NET Paper - 2 for the wider syllabus. Redo all ten without explanations, naming the violated rule beside each error.