Search code examples
.netregextheoryfinite-automataregular-language

What are the theoretical implications of unbounded lookbehind?


Most languages allow fixed-length or finite-length lookbehind. One notable exception is .NET, which allows the use of the * operator.

However, .NET regexs can already recognize balanced parentheses using named capture, which is not a regular language. Are regexs still regular with * in lookbehind? Extended answers for subexpressions other than * (for example, additional lookaround!) would also be appreciated.

tl;dr: Do regexs stay regular with * in lookbehind?


Solution

  • I believe the answer here: Does lookaround affect which languages can be matched by regular expressions? can be extended to prove that adding * in lookbehind (or even nesting such lookbehinds and lookaheads) does not affect the 'regularness' of the expressions. I haven't put more thought into it though.

    Hope that helps!