(a) Let S be the set of binary strings with the following decomposition: S = ({0}*{11}{1}*)*...

 

Transcribed Image Text:

(a) Let S be the set of binary strings with the following decomposition: S = ({0}*{11}{1}*)* Explain why this is an ambiguous expression for S. (b) Suppose the weight of a string is its length. Let Þs(x) be the generating series for S. Suppose we obtain 's(x) by applying the product and sum lemmas for strings using the ambiguous expression in part (a). Which of the following are true? i. For all n ≥ 1, [xª]Þs(x) > [x²]Þ's(x). ii. For all n ≥ 1, [x²]Þs(x) < [x²]Þ's(x). iii. There exists an n ≥ 1 such that [x²]Þs(x) > [x²]Þ's(x). iv. There exists an n ≥ 1 such that [x]Þs(x) < [x²] Þ's(x). Circle all that are true, and briefly justify your answer. (a) Let S be the set of binary strings with the following decomposition: S = ({0}*{11}{1}*)* Explain why this is an ambiguous expression for S. (b) Suppose the weight of a string is its length. Let Þs(x) be the generating series for S. Suppose we obtain 's(x) by applying the product and sum lemmas for strings using the ambiguous expression in part (a). Which of the following are true? i. For all n ≥ 1, [xª]Þs(x) > [x²]Þ's(x). ii. For all n ≥ 1, [x²]Þs(x) < [x²]Þ's(x). iii. There exists an n ≥ 1 such that [x²]Þs(x) > [x²]Þ's(x). iv. There exists an n ≥ 1 such that [x]Þs(x) < [x²] Þ's(x). Circle all that are true, and briefly justify your answer.

Answer rating: 100% (QA)

aThis is an ambiguous expression for S because it is not clear if the 1 is supposed to be part of th... View the full answer