Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)

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:

Where $|\ |$ denotes the cardinality of the set.





Solution

In Chomsky Normal Form, every production must be of the form:

$A\rightarrow BC$

or

$A\rightarrow a$

If a production has maximum $K$ symbols on the right side, then to convert it into binary productions, at most $K-1$ productions are needed.

So, for $|P|$ productions, maximum productions required are:

$(K-1)|P|$

Also, for terminals, we may need separate productions for each terminal.

Number of terminals $=|T|$

So, total maximum number of productions:

$(K-1)|P|+|T|$


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More
Ask Your Question or Put Your Review.

loading...