How to tell if one regular expression matches a subset of another regular expression?

by

I think — in theory — to tell whether regexp A matches a subset of what regexp B matches, an algorithm could:

  1. Compute the minimal Deterministic Finite Automaton of B and also of the “union” A|B.
  2. Check if the two DFAs are identical. This is true if and only if A matches a subset of what B matches.

However, it would likely be a major project to do this in practice. There are explanations such as Constructing a minimum-state DFA from a Regular Expression but they only tend to consider mathematically pure regexps. You would also have to handle the extensions that Python adds for convenience. Moreover, if any of the extensions cause the language to be non-regular (I am not sure if this is the case) you might not be able to handle those ones.

But what are you trying to do? Perhaps there’s an easier approach…?

More Related Contents:

  1. How to use a variable inside a regular expression?
  2. Match a whole word in a string using dynamic regex
  3. How to check for valid email address? [duplicate]
  4. Case insensitive regular expression without re.compile?
  5. Split a string at uppercase letters
  6. Regex matching 5-digit substrings not enclosed with digits
  7. How to split but ignore separators in quoted strings, in python?
  8. Python regex match OR operator
  9. Regular expression to extract URL from an HTML link
  10. Python Regex escape operator \ in substitutions & raw strings
  11. How to extract an IP address from an HTML string?
  12. Regex for existence of some words whose order doesn’t matter
  13. Split string based on a regular expression
  14. Split string on commas but ignore commas within double-quotes?
  15. Python/Regex – How to extract date from filename using regular expression?
  16. How would I get everything before a : in a string Python
  17. Python regex: splitting on pattern match that is an empty string
  18. How to remove symbols from a string with Python? [duplicate]
  19. How to find and replace nth occurrence of word in a sentence using python regular expression?
  20. Python unicode regular expression matching failing with some unicode characters -bug or mistake?
  21. How to split a string by commas positioned outside of parenthesis?
  22. Regex to match digits of specific length
  23. Regex: match only outside parenthesis (so that the text isn’t split within parenthesis)?
  24. Creating a custom categorized corpus in NLTK and Python
  25. Warning raised by inserting 4-byte unicode to mysql
  26. How do I verify that a string only contains letters, numbers, underscores and dashes? [duplicate]
  27. Python regex: matching a parenthesis within parenthesis
  28. Regexp finding longest common prefix of two strings
  29. Splitting a math expression string into tokens in Python
  30. Download all pdf files from a website using Python

Leave a Comment