13
$\begingroup$

It appears that "Basic Regular Expressions" as defined by POSIX.1-2008 do not support alternation, a|b (although some grep implementations recognize the escaped version, \|).

Since the regular languages are closed under union by definition, does this mean that POSIX BRE has less expressive power than a finite automaton? Or is there some way to simulate alternation using other constructs?

$\endgroup$
17
$\begingroup$

Indeed the POSIX BRE language cannot express all regular expressions because it lacks alternation. It can't even recognize all finite languages, let alone all regular languages.

For example, $\{ab, ba\}$ is not recognizable as a BRE. To prove this, consider what the toplevel syntactic form could be:

  • It can't be one of the single-character forms since the language has words of length $\gt 1$.
  • It can't be $R^*$ because that would match the empty string.
  • It can't be $R^{\{m,n\}}$ except with $m=n=1$ (in which case we're back to the original problem) because that would match strings of different lengths or the empty string.
  • So it has to be concatenation: $R_1 R_2$. Now consider how $ab$ is recognized:
    • If $R_1$ recognizes $ab$ then $R_2$ must not recognize anything anything other than the empty string. So $R_1$ must recognize $\{ab,ba\}$ and we're back to the original problem.
    • If $R_1$ recognizes $a$ but not $ab$ then $R_2$ must recognize $b$. But then $R_1R_2$ recognizes all words of the form $u b$ where $R_1$ recognizes $u$, so $R_1$ must not recognize anything other than $a$. There's no way to recognize $ba$.
    • If $R_1$ recognizes neither $ab$ nor $a$ then the only way for $R$ to recognize $ab$ is if $R_1$ recognizes the empty string, in which case we're back to the original problem as above, but for $R_2$ this time.

When “we're back to the original problem”, that means that the only solution to find a BRE recognizes the language is to find a smaller BRE that has the same property. This is an infinite descent, so there's no BRE that has the desired property.

I don't think there's a “nice” characterization of BRE-recognizable languages, for example as languages recognizable by a “nice” class of automata.

Note that BRE-recognizable languages are actually not a subclass of regular languages, since backreferences add expressive power. For example $\{w w \mid w \in \{a,b\}^*\}$ is recognized by the BRE \(.*\)\1 but is famously not regular. BRE without backreferences are just syntactic sugar over regular expressions so the languages they can recognize are a subclass of the regular languages.

$\endgroup$
2
  • 1
    $\begingroup$ If you are using a tool like grep which can accept multiple newline-separated expressions to match, is taking the cartesian product of all would-be alternations (e.g. {ab,ba}{ab,ba} becoming {abba,abba,baab,baba}) sufficient to be equivalent to any given "BRE-plus-alternation" and therefore any regular language? $\endgroup$
    – Random832
    Aug 28 '16 at 3:34
  • 1
    $\begingroup$ @Random832: Try to do (abc|bac)*. $\endgroup$
    – rici
    Aug 28 '16 at 4:00

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.