18
$\begingroup$

Setting:

  • regular expressions with backreferences
  • unary language (1-symbol alphabet)

Is the following problem decidable in this setting:

  • Given a regular expression with backreferences, does it define a regular language?

For example, (aa+)\1 defines a regular language, while (aa+)\1+ doesn't. Can we decide which one is the case?


For concreteness, "regular expressions with backreferences" here refer to e.g. the following subset of the usual Perl-compatible regular expressions:

  • a matches character a (the only character in the alphabet)
  • X* matches 0 or more occurrences of X
  • X|Y matches X or Y
  • parentheses can be used for grouping and capturing
  • \1. \2, etc. match the same string as the 1st, 2nd, etc. pair of parentheses

We can also use the normal shorthands e.g. X+ = XX*.

$\endgroup$
  • 1
    $\begingroup$ Have you explored counting approaches, i.e. inspecting the sequence of $|L_n|$? I guess you are familiar with the work of Freydenberger? $\endgroup$ – Raphael Oct 9 '16 at 12:55
4
$\begingroup$

Evidence against the effective decidability of the problem is provided by the construction in the proof of Theorem 9 in my paper On Practical Regular Expressions: You could determine if there are finitely many Fermat primes.

$\endgroup$
  • $\begingroup$ Welcome to the site! I've added a fuller citation to your paper. $\endgroup$ – David Richerby Aug 27 '18 at 13:58

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.