ADG is said to be in Chomsky Form (CNF), if all the productions are of the form A --> BC or
A --> a. Let G be a CFG in CNF. To derive a string of terminals of length x , the number of productions to be used is
| A. | 2x - 1 |
| B. | 2x |
| C. | 2x + I |
| D. | None of these |
Answer : A Explanation : kavita said: (1:11pm on Sunday 9th June 2013)
why option a?
Akhil Babu said: (9:55pm on Monday 26th February 2018)
So in each step when we try to derive a string, there are two possibilities1) Either at every step we are increasing number of variables(Non terminals) by 12) OR we are going to increase number of terminals by 1Therefore we first try to get string of variables whose length is equal to the given string, in this procedure the number of steps required = n-1 and from there on we keep on replacing every variable with a terminal, in this procedure the number of steps requires =nSo total = n -1 n =2*n-1 steps
|
|
|
Option: A Explanation : Explanation will come here. Explanation will come here. Explanation will come here. Explanation will come here. Explanation will come here. |
