Redirected
edited by
1,395 views
1 votes
1 votes

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:

  1. $(K-1) \mid P \mid + \mid T \mid -1$
  2. $(K-1) \mid P \mid + \mid T \mid $
  3. $K \mid P \mid + \mid T \mid -1$
  4. $K \mid P \mid + \mid T \mid$

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

edited by

2 Answers

Best answer
3 votes
3 votes
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 |$
selected by
1 votes
1 votes

$\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

edited by

Related questions

1 votes
1 votes
2 answers
1
4 votes
4 votes
6 answers
3
soujanyareddy13 asked May 12, 2021
1,865 views
The Boolean expression $AB+A \overline{B}+\overline{A}C+AC$ is unaffected by the value of the Boolean variable _________.$A$$B$$C$$A, B$ and $C$