Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment 4

MATH 239 Fall 2022

A-4-1.  {5 marks} Consider the following ambiguous regular expression:

(1*   00  0*)*

(i) Explain why the expression is ambiguous.

(ii) Describe in words the rational language the expression produces.

(iii) Provide an unambiguous regular expression for the rational language the expression produces. You do not need to justify why your expression is unambiguous.

A-4-2.  {5 marks} Consider the following ambiguous regular expression:

(1  1*   00  0*   1  1*)*

(i) Explain why the expression is ambiguous.

(ii) Describe in words the rational language the expression produces.

(iii) Provide an unambiguous regular expression for the rational language the expression produces. You do not need to justify why your expression is unambiguous.

A-4-3.  {5 marks} Let R be the set of all binary strings where each block of 0s has length 1, 2, or 7, and each block of 1s has length at least 4.

(i) Write an unambiguous regular expression that produces R. You do not need to justify why your expression is unambiguous.

(ii) Determine the generating series ΦR(x) with respect to length (simplify your expression so your answer is a rational function, that is a ratio of polynomials).

A-4-4.  {5 marks} Let R be the set of all binary strings where each block of 0s has length divisible by

2022 and each block of 1s has length not divisible by 2022.

(i) Write an unambiguous regular expression that produces R. You do not need to justify why your expression is unambiguous.

(ii) Determine the generating series ΦR(x) with respect to length (simplify your expression so your answer is a rational function, that is a ratio of polynomials).