Question

Let sheep(x) be the string formed by replacing each b in x by the substring baa (this transformation is done once, not recursively ad infinitum). For example, sheep(babaab) = baaabaaaabaa. Furthermore, let sheep(L) be the language formed of strings sheep(x) for x ∈ L. In this question, you will prove that if L is regular, then so is sheep(L), where L ⊆ {a, b} ∗ . Observe that if L is regular, then L can be expressed as L(α) for some regular expression α. Hint: Use structural induction. You may assume that the following statement holds: for all strings x and y, sheep(xy) = sheep(x)sheep(y).

Answer 1