15
\$\begingroup\$

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 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
```
\$\endgroup\$
6
  • \$\begingroup\$ It's probably worthwhile to add information about precedence and parentheses to the regex specification. \$\endgroup\$
    – DLosc
    Feb 12, 2022 at 18:32
  • \$\begingroup\$ @DLosc You can decide the input format so you can also decide what kind of precedence the operations have. The examples are unambiguous. \$\endgroup\$
    – AnttiP
    Feb 12, 2022 at 18:35
  • \$\begingroup\$ Is this solvable? \$\endgroup\$
    – l4m2
    Feb 12, 2022 at 18:38
  • 2
    \$\begingroup\$ @l4m2 Good question, yes it is. Regular languages are simple enough that you can do this. For example, see this Stackoverflow question \$\endgroup\$
    – AnttiP
    Feb 12, 2022 at 18:39
  • \$\begingroup\$ 10((10)*), 1(01*)0 -> True miswrite 1(01)*0? \$\endgroup\$
    – l4m2
    Feb 12, 2022 at 19:02

3 Answers 3

6
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ The deterministic finite automaton "link" is broken (it doesn't go to a valid website). Maybe you meant to put the Wikipedia link for it instead? \$\endgroup\$
    – Aiden Chow
    Feb 14, 2022 at 6:37
  • \$\begingroup\$ @l4m2 Yes, you're right. I fixed it. \$\endgroup\$
    – Tc14
    Feb 14, 2022 at 6:44
  • \$\begingroup\$ @AidenChow Thanks. Fixed that one too. \$\endgroup\$
    – Tc14
    Feb 14, 2022 at 6:45
  • \$\begingroup\$ 848 bytes by compressing the code and decompressing it at runtime. (I had to put the URL through a shortener because the TIO link was still too long for the comment box!) \$\endgroup\$ Feb 14, 2022 at 7:19
  • \$\begingroup\$ @MadisonSilver The link doesn't work for me. It just redirects me to the start page. \$\endgroup\$
    – Tc14
    Feb 14, 2022 at 17:51
4
\$\begingroup\$

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)

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Can you justify your assumption? Also, this definitely won’t work (even theoretically) for \$\lvert a\rvert + \lvert b\rvert ≥ 6\$, since 2**2**6 - 1 === 2**2**6 in JavaScript. \$\endgroup\$ Feb 12, 2022 at 20:53
  • \$\begingroup\$ @AndersKaseorg I think we can assume they're bigint so 2**2**6 - 1 != 2**2**6 to theoretically allow length 2**2**6 - 1. Assumption maybe later \$\endgroup\$
    – l4m2
    Feb 13, 2022 at 2:02
  • 2
    \$\begingroup\$ 2**2**6 is a double-precision float; 2n**2n**6n is a BigInt. We have consensus that you cannot assume by default that floats are infinitely precise, and while it seems reasonable to grant some leeway for code that might fail on inputs in the billions, it seems less reasonable to accept this on inputs of length 3. \$\endgroup\$ Feb 13, 2022 at 2:40
  • \$\begingroup\$ @AndersKaseorg You provide a link that more agree such assumption and text that it isn't? \$\endgroup\$
    – l4m2
    Feb 13, 2022 at 2:47
2
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.