1
$\begingroup$

how can you find if a regex call is a subset of another regex call on an predictable set of data

I have a string (chess Forsyth–Edwards Notation (FEN) stringrnbqkbnr/pppp1ppp/8/4p3/3P4/8/PPP1PPPP/RNBQKBNR w KQkq e6 0 2)

If I use /(.)/g it matches the super set of any possible chess position, i.e. /(r/)/g matches r/ , a sub set of /(.)/g

is it possible to apply set theory to regex (or another parser) on stings that follow a pattern like FEN? if so, how can I calculate if one regex is a subset, superset, or equal set of another for this data type?

my goal is to find if a parsing function will find a subset of the possible fen positions that another function will find. is it possible to do this without mapping every possible fen string? that's not an option. should I use regex? or a different parsing system because the characters follow a pattern already?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

There is an algorithm that checks, for every two regular languages $L_1,L_2$ given as DFAs, whether $L_1 \subseteq L_2$. The idea is to construct a DFA for $L_1 \setminus L_2$ using the product construction, and then to check emptiness, by checking whether some accepting state is reachable from the initial state.

If your regular expressions are "TCS-regular" (they don't use backreferences), then you can convert them to DFAs and use the algorithm above. While the conversion to DFA incurs exponential blow-up in the worst case, in practice this probably won't happen.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I had to google a lot of terms in what you wrote and it sent me down some good paths thank you. can you help me understand "and then to check emptiness, by checking whether some accepting state is reachable from the initial state." I understand set emptiness but not the rest. $\endgroup$
    – cubesareneat
    Oct 19, 2021 at 18:50
  • $\begingroup$ cs.cornell.edu/courses/cs312/2007fa/recitations/rec26.html mentions " a deterministic finite automaton (DFA) can be constructed that recognizes any string that the regular expression describes in time linear in the length of the string" dose that contradict "While the conversion to DFA incurs exponential blow-up in the worst case" ? $\endgroup$
    – cubesareneat
    Oct 19, 2021 at 18:53
  • $\begingroup$ The recitation notes from Cornell are worded in a funny way. My guess is that they wanted to say that every regular expression has an equivalent DFA which can be construct in linear time. This is provable wrong, but is true if you replace DFA by NFA. $\endgroup$
    – Yuval Filmus
    Oct 19, 2021 at 19:10
  • $\begingroup$ Any decent textbook will contain a description of the algorithm for checking emptiness of the language accepted by a DFA; or you could come up with one yourself. $\endgroup$
    – Yuval Filmus
    Oct 19, 2021 at 19:11

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.