How many min and max number of productions will be required in Chomsky Normal Form(CNF) and Greibach Normal From(GNF) each if string length = n ?
I've heard somewhere that in GNF, minimum and max productions both are "n". Unable to understand this and have no idea about CNF. Someone please explain. I know the basics of GNF, CNF but unable to derive this formula intuitionally as well as mathematically.
Asked
Active
Viewed 344 times
0
SpawN
- 67
-
Regarding CNF, there is an answer in https://math.stackexchange.com/questions/1257688/computational-theory-proof-chomsky-normal-form – frabala Jul 03 '20 at 08:40
-
In GNF, the rules are of the form $A\to a B_1 B_2\ldots B_k$, so each rule "establishes" one character of the string. How many rules would you need to produce a string of size $n$? I think you can prove the answer by induction, in a similar way as in the answer of the above link about CNF. – frabala Jul 03 '20 at 08:51