Assignment 4
COMP 330
计算机Assignment代写 There are 5 questions for credit and one for you to ponder. Show that this grammar is ambiguous by giving two difffferent parse…
There are 5 questions for credit and one for you to ponder.
Question 1[15 points] Consider the grammar 计算机Assignment代写
S → aS|aSbS|ε.
Show that this grammar is ambiguous by giving two difffferent parse trees for the string aab.
Question 2[30 points] Show that the grammar of the last question defifines all strings, and only those strings, in which every prefifix contains at least as many as as bs. Note that this requires two proofs. First, you must show that every string produced by the grammar has this property. Second, you must show that every string that has this property can be produced by this grammar.
Question 3[15 points] Give an unambiguous grammar for the language defifined by the grammar in question 1.
Question 4[20 points] Give an unambiguous context-free grammar to defifine the following language:
L = {ai+j bj+kci+k|i, j, k ≥ 1.}
Question 5[20 points] Construct a PDA that accepts the following language
{a3ibi|i ≥ 0}.
Your answer should be a drawing of the states and transitions. 计算机Assignment代写
Question 6[0 points] Show that the language L = {anbn|n ≥ 0} ∪ {anb2n|n ≥ 0} is context free, but is not accepted by any deterministic PDA.
