Please thoroughly explain how you got to your answer. Suppose I have a CFG (not
ID: 3798003 • Letter: P
Question
Please thoroughly explain how you got to your answer.
Suppose I have a CFG (not necessarily in CNF) and a string of length 5 in its language. What can I tell about a derivation of this string in the grammar? The derivation involves exactly 10 applications of rules to derive this string. The derivation involves exactly 9 applications of rules to derive this string. The derivation involves at least 5 applications of rules to derive this string, but can be arbitrarily large. The derivation involves some number of applications of rules to derive this string, but is at most 32. None of the above are true. Suppose I have a CFG in CNF and a string of length 5 in its language. What can I tell about a derivation of this string in the grammar? The derivation involves exactly 10 applications of rules to derive this string. The derivation involves exactly 9 applications of rules to derive this string. The derivation involves at least 5 applications of rules to derive this string, but can be arbitrarily large. The derivation involves some number of applications of rules to derive this string, but is at most 32. None of the above are true.Explanation / Answer
Question 7
Ans: The derivation involves at least 5 applications of rules to derive this string, but can be arbitrarily large. Because in CFG to derive a string of length |W|, minimum number of steps needed is |W| and maximum is 2* |W|. So minimum steps required is 5 as the length of given string is 5.
Question 8
Ans: The derivation involves exactly 9 application of rules to derive this string. Because in CNF every production is either
A => BC or A => a
So, to derive |W| length, in |W|-1 step we can set |W| length of all variable, then in another |W|, step we will get all terminal.
So, exactly |W| - 1 + |W| = 2|W| -1 step
So for the given string of length 5 the derivation involves 2* 5 -1 = 9 steps exactly