6
$\begingroup$

Many computer languages have complex regular expressions tools. For example, in Javascript you have global flags, escape characters, whitespace character, assertions, character classes, groups and ranges etc. I'm wondering if using just the 3 basic regular expressions operators as defined in formal languages, that is concatenation, alternation and Kleene star can achieve the same result as any pattern described with more tools as for example in Javascript. Is there a theorem about this?

$\endgroup$
3
  • 1
    $\begingroup$ Alternation? Why didn't the book or doc you're reading call it disjunction? $\endgroup$ Sep 25 '20 at 17:01
  • 4
    $\begingroup$ The features that you list include things that aren't part of the regular expression ("global flags"), are mere syntactic representation ("escape characters"), or are shorthands for alternation ("character classes", "range"). You already have an answer for your question as written, but if you're interested in this subject, you might want to spend some time understanding regular expressions better. $\endgroup$
    – ruakh
    Sep 25 '20 at 21:27
  • 5
    $\begingroup$ @JohnnyApplesauce -- "alternation" is often used in describing regular expressions. I suspect it's more common than "disjunction", but both mean the same thing. $\endgroup$ Sep 26 '20 at 15:31
25
$\begingroup$

Regular expressions using only concatenation, alternation and Kleene star describe regular languages. In contrast, extended regular expressions available in modern programming languages can describe non-regular languages. For example, (.*)\1 describes the language $\{ ww : w \in \Sigma^* \}$, which is not even context-free.

$\endgroup$
2
  • 1
    $\begingroup$ What about extended regexes that don’t have back references? Or without look aheads or look behinds? Such as Thompson NFA approaches like Go. $\endgroup$ Sep 25 '20 at 17:03
  • 22
    $\begingroup$ If you change the question, you might get a different answer. The exact answer depends on the exact question. $\endgroup$ Sep 25 '20 at 17:04
1
$\begingroup$

Most real-world regular expression constructs can be converted to what I lovingly call ivory tower regular expressions.

For example:

  • $a? = (\epsilon + a)$
  • $a+ = a(a*)$
  • $a\{n,m\} = aaa\ldots{}a(a?)(a?)\ldots{}(a?)$ where $a$ is repeated $n$ times and $(a?)$ is repeated $m$ times.

Most lookahead operations can be expressed as the intersection of two languages (perhaps you need some clever product constructions, starting from the state you are currently at, or some such tricks and techniques).

Back-references make the whole exercise NP-complete, though; see e.g. https://perl.plover.com/NPC/NPC-3COL.html.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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