Your implementation need not
Define a recursive function (rem r b) that, given a regular expression r and a bool b, returns a new regular expression r′ that matches exactly the set of all strings s such that string bs is matched by r. We will call r′ the remainder of r after division by b. For example, if r matches {T,FF T,TFF} and b = T, then r′ can be any regular expression that matches exactly the set {ε,FF} (because T and TFF are the only strings matched by r that begin with b = T, and their remainders are ε and FF, respectively). Here are some examples of what your function could output (but these are not the only answers!):
• rem (false(false+true)∗) false = (false+true)∗ • rem (false(false+true)∗) true = ∅
• rem (false∗ + true∗) true = true∗
• rem ((false∗)(true∗)) true = true∗
Your implementation need not output these exact regular expressions as long as it always outputs an equivalent regular expression (i.e., one that matches the same set of strings as the given answer). These are also not the only test cases; your solution should output a correct answer for every input, not just for these four examples.
Step by step
Solved in 4 steps with 2 images
