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

cs.stackexchange https://cs.stackexchange.com/questions/130500

質問

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?

役に立ちましたか?

解決

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.

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top