HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Is it possible to build any regular expression in a computer language with just 3 basic operators?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
expressionwithjustanyregularlanguageoperatorspossiblecomputerbuild

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#130500, answer score: 25

Revisions (0)

No revisions yet.