You are given two regexes and your task is to determine if the strings matched by the first regex are a subset of the strings matched by the second regex.
For this we are going to use a limited mathematical definition of a regex. A regex is defined recursively as one of:
ε- This matches only the string
0- This matches only the string
1- This matches only the string
r1|r2- This matches iff
r1r2- This matches iff
r1matches a prefix of the string and
r2matches the remaining string
r1*- This matches iff any of
r1r1r1, etc. matches.
Input format is flexible. If you use a string with some kind of syntax, make sure that it can represent every regex (you may need parenthesis). Output as per standard decision-problem rules.
(0|1)*, (0(1*))* -> False The first regex matches every string, the second one only ones that start with a 0 0(0*)1(1*), (0*)(1*) -> True The first regex matches strings that consists of a run of 0 and a run of 1, and both runs have to have length >0. The second regex allows runs of length 0. ((10)|(01)|0)*, (1001)*0 -> False The first regex matches "10" which is not matched by the second regex. 0, 1 -> False Neither is a subset of one another 1(1*), (1|ε)*1 -> True Both regexes match nonempty strings that consist of only ones 10((10)*), 1((01)*)0 -> True Both regexes match nonempty strings made by concatenating "10" ε*, ε -> True Both only match the empty string ```