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"0"
1
- This matches only the string"1"
r1|r2
- This matches iffr1
orr2
matchesr1r2
- This matches iffr1
matches a prefix of the string andr2
matches the remaining stringr1*
- This matches iff any ofε
,r1
,r1r1
,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.
Examples
(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
```
10((10)*), 1(01*)0 -> True
miswrite1(01)*0
? \$\endgroup\$