Is it a bigger regex?

Question

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 iff r1 or r2 matches
• r1r2 - This matches iff r1 matches a prefix of the string and r2 matches the remaining string
• r1* - 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
```

Answer 1

Python 3, 1206 bytes

l=len
r=range
def R(a):return r(l(a))
def A(a,b):
 for x in b:
  for z in[0,1]:x[z]<<=l(a)-1
 for x in a:
  if x[2]:
   x[2]=b[0][2]
   for z in[0,1]:x[z]|=b[0][z]
 return a+b[1:]
def B(a,b):
 c=[]
 for i in R(a):
  for j in R(b):
   c+=[[0,0,a[i][2]or b[j][2]]]
   for z in[0,1]:
    for k in R(a):
     if(a[i][z]>>k)%2:c[-1][z]|=b[j][z]<<k*l(b)
 return c
def C(s,i):
 S=[];T=[]
 while i<l(s):
  c=s[i]
  if c=="(":a,i=C(s,i+1);T+=[a]
  if c==")":break
  if c=="0"or c=="1":X=[[4,4,0],[4,4,1],[4,4,0]];X[0][int(c)]=2;T+=[X]
  if c=="ε":T+=[[[2,2,1],[2,2,0]]]
  if c=="|":
   t=T[0]
   for j in r(1,l(T)):t=A(t,T[j])
   S+=[t];T=[]
  if c=="*":
   a=T[-1];a[0][2]=1
   for x in a:
    if x[2]:
     for z in[0,1]:x[z]|=a[0][z]
  i+=1
 t=T[0]
 for j in r(1,l(T)):t=A(t,T[j])
 S+=[t]
 t=S[0]
 for j in r(1,l(S)):t=B(t,S[j])
 return t,i
I=input().split(",")
a=C(I[0],0)[0]
b=C(I[1],0)[0]
Q=[(1,1)]
V=set(Q)
d=1
while l(Q):
 p,q=Q.pop();f=any([(p>>i)%2 and a[i][2]for i in R(a)]);g=any([(q>>i)%2 and b[i][2]for i in R(b)])
 if f and not g:d=0
 for z in[0,1]:
  s=0;t=0
  for i in R(a):
   if(p>>i)%2:s|=a[i][z]
  for i in R(b):
   if(q>>i)%2:t|=b[i][z]
  u=(s,t)
  if u not in V:V.add(u);Q.append(u)
print(d)

Try it online!

Input

The two regex expressions on one line, separated by a comma. The expressions are not allowed to be empty and they also must be well-formed. That means that each opening bracket has to have a corresponding closing one, there has to be a non-empty subexpression before every *, and two non-empty subexpressions left and right of every |. ε can be used to match the empty string. The order of precedence is *, concatenation, | (just as normal regex).

Output

1 when the first regex is a subset of the second one, else 0.

How it works

In the beginning, the algorithm converts both regex expressions into a deterministic finite automaton. Then it calculates the product of the two automatons and does a search beginning at the start node. If it finds a node that is an accepting state for the first regex but not for the second, the first regex can't be a subset of the second one. If it can't find such a node, it is a subset.

Complexity

The worst-case time complexity is roughly \$O\left(2^{2^n}\right)\$ (I might have ignored some insignificant terms), where \$n\$ is the length of the input. In practice, the runtime is much better than expected: All the example test cases and even the example 0(0|ε)(00|ε)(0000|ε)(000000000)*,00000000(00000000)* from l4m2 run in less than 0.1 seconds.

Code length

I'm not good at minifying my code, so there might be still a lot of room for improvement.

Answer 2

JavaScript (Node.js), 105 99 bytes

a=>b=>(g=n=>!n||g(n-1)&(h=x=>!n.toString(2).slice(1).match(`^${x}$`))(a)>=h(b))(2**2**(a+b).length)

Try it online!

Assuming any mismatch found in \$2^{\left|a\right|+\left|b\right|}-1\$ length. Actually \$\left|a\right|\cdot\left|b\right|\$ should be enough because of number of states, but 2**(a+b).length is shorter than a.length*b.length.

\${\left|a\right|+\left|b\right|}-1\$ is not enough for 0(0|)(00|)(0000|)(000000000)* >= 00000000(00000000)* (shortest counterexample 72 "0"s)

Answer 3

Python3, 677 bytes

import itertools as it,re
I=isinstance
def t(q):
 if I(q,str):yield q;return
 if all(I(i,str)for i in q):yield from q;return
 yield from map(''.join,it.product(*[[j for k in i for j in t(k)]for i in q]))
def p(s):
 q=[];f=0
 while s:
  if(n:=s[0])==')':return s[1:],q
  if n=='(':
   s,v=p(s[1:])
   if f:q[-1]=(q[-1],v);f=0
   else:q+=v
  elif n=='*':q[-1]=[*q[-1],''];s=s[1:]
  elif n=='|':f=1;s=s[1:]
  else:
   s=s[len((v:=re.findall('^[10ε]+',s))[0]):]
   v=[''.join([i if i in'10'else '' for i in v[0]])]
   if f:q[-1]=[*q[-1],*v];f=0
   else:q+=[v]
 return s,q
G=lambda x:[*t(p(x)[1])]
def f(a,b):
 j,k=G(a),G(b)
 return all(i in k for i in j if len(i)<=max(map(len,k)))

Try it online!