Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)

The Problem

There is no easy way to get a permutation with a regex.

• Permutation: Getting a word $$w=x_1…x_n$$ ("aabc") to another order, without changing number or kind of letters.

• Regex: Regular expression.

For verification:

• "Regex permutations without repetition" The answer creates JavaScript code instead of a regex, assuming this would be more simple.

• "How to find all permutations of a given word in a given text" – The answer doesn't use regexes either.

• "Regex to match all {1, 2, 3, 4} without repetition" – The answer uses regexes, but it's neither adaptable nor simple.

• This answer even claims: "A regular expression cannot do what you're asking for. It cannot generate permutations from a string".

The kind of solution I am searching for

It should have the form:

• »aabc« (or anything else you could use a opening and closing parentheses)

• (aabc)! (similar to (abc)? but with another symbol in the end)

• [aabc]! (similar to [abc]+ but with another symbol in the end)

Advantages of these solutions

They are:

• easy

• adaptable

• reusable

Why this should exist

• Regexes are a way to describe a grammar of a regular language. They have the full power to be any kind of regular language.

• Let's say, regular languages are powerful enough for permutations (proof below) – why is there no easy way to express this?

So my question is:

• (Why) Is my proof wrong?

• If it is right: Why is there no easy way to express permutations?

The proof

• Regular expressions are one way to note the grammar of a regular language. They can describe any regular languages grammar.

• Another way to describe any regular languages (that have a finite number of letters within their alphabet) grammar are non-deterministic Automatons (with a finite number of states).

Having a finite number of letters I can create this automaton: (Example. Formal: see below)

Grammar that accepts permutations of "abbc":

(sry for numbers on top, maybe someone knows how to make thi

The fundamental theorems of formal language theory are that regular expressions, regular grammars, deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs) all describe the same kinds of languages: namely the regular languages. The fact that we can describe these languages in so many completely different ways suggests that there's something natural and important about these languages, in the same way that the equivalence of Turing machines, the lambda calculus and all kinds of other things suggests that the computable languages are natural and important. They're not just an artifact of whatever random decisions the original discoverer made.

Suppose we add a new rule for creating regular expressions: if $R$ is a regular expression, then $\pi(R)$ is a regular expression, and it matches every permutation of every string matched by $R$. So, for example, $L(\pi(abc)) = \{abc, acb, bac, bca, cab, cba\}$. The problem is that this breaks the fundamental equivalences described above. $L\big(\pi((ab)^*))\big)$ is the language of strings that contain an equal number of $a$s and $b$s and this isn't a regular language. Compare this with, for example, adding a negation or reversal operator to regular expressions, which doesn't change the class of languages that are accepted.

So, to answer the title question, regular expressions can't do permutations and we don't add that ability because then regular expressions wouldn't match regular languages. Having said that, it's possible that "regular expressions with permutations" would also be an interesting class of languages with lots of different characterizations.

StackExchange Computer Science Q#100206, answer score: 40