UGC NET CSE | December 2019 | Part 2 | Question: 49

Question

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) \mid P \mid + \mid T \mid -1$
• B. $(K-1) \mid P \mid + \mid T \mid $
• C. $K \mid P \mid + \mid T \mid -1$
• D. $K \mid P \mid + \mid T \mid$

Where $\mid \cdot \mid$ denotes the cardinality of the set.

Comments

This is asked directly from the Peter Linz Textbook.

https://gateoverflow.in/310287/peter-linz-edition-4-exercise-6-2-question-6-page-no-169

https://math.stackexchange.com/questions/1792866/prove-that-there-exists-an-equivalent-grammar-in-chomsky-normal-form-like-g-s

Answer is $\mathbf{B}$.

Answer 1

Option B.

Let’s say there’s a production rule where all symbols on R.H.S are terminals. So to convert that into CNF we’ll have maximum   $\left | T \right |$  new variables and hence maximum $\left | T \right |$ new production rules.

After that we’ll be left with all variables on the R.H.S of a production rules. If we have A → BCD we can do like,

A→ VD , V → BC.

If we have A→ BCDE , we can convert that into A→ VE , V→ UD , U→ BC.  Notice that for ‘n’ number of variables we can have a maximum of (n – 1) production rules.

 

Hence for ‘K’ symbols on the R.H.S we’ll have (K – 1) production rules for each production rule in G.

so for $\left | P \right |$  productions we can have a maximum of (K – 1) $\left | P \right |$ rules. This added with  $\left | T \right |$ will make the final answer as

(K – 1) $\left | P \right |$ + $\left | T \right |$

Answer 2

$\underline{\textbf{Answer:}\Rightarrow}(2)\;\color{blue}{\mathbf{(k-1)|P|+|T|}}$

For any context-free grammar $\mathbf{G = (V,T,P,S)}$ without any $\lambda$-productions or unit-productions.

The maximum number of production rules are:

$\color{blue}{\mathbf{(k-1)|P|+|T|}}$

where $\mathbf k$ is the maximum number of the symbol on the right of production $\mathbf P$.

---

It is a direct textbook question from Peter Linz.

https://gateoverflow.in/310287/peter-linz-edition-4-exercise-6-2-question-6-page-no-169

Comments

for example take this grammar in CNF

A -> BC

B -> a

c-> b

here K = 2, cardinality of P = 2 and cardinality of T = 2

will the formula support it ?

correct me lease?