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

Question

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 this part looking better)

s -> ah¹

s -> bh²

s -> ch³

h¹ -> bh¹¹

h¹ -> ch¹²

h² -> ah¹¹ (no typo! equivalence)

h² -> bh²²

h² -> ch²³

h³ -> ah¹²

h³ -> bh²³

h¹¹ -> bc

h¹¹ -> cb

h¹² -> bb

h²² -> ac

h²² -> ca

h²³ -> ab

h²³ -> ba

More formal: (using a finite-state-automaton but this could be made with grammar as well)

• A word q (with finite length) to which any permutation should reach an accepting state.
• X is the finite alphabet.
• Set of states S contains any order of letters up to the length of q. (So the size of S is finite.) Plus one state of "any longer word".
• state transition function d which takes a letter and moves on the state that corresponds to the now read part of the word.
• F is a set of that states that are exact permutations of q.

So it is possible to create a finite-state automaton for accepting permutations of a given word.

Moving on with the proof

So I have proven that regular languages have the power to check for permutations, haven't I?

So why is there no approach to reach this with Regexes? It's a useful functionality.

Answer 1

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.

Answer 2

So my question is:

• (Why) Is my proof wrong?
• If it is right: Why is there no easy way to express permutations?

Your "proof" only looked at permutations of single words, which are finite languages.

Every finite language is regular (e.g. just by listing all of the members with a | inbetween), but there are infinite regular languages (and those are generally the more interesting ones).

As soon as you get a regular expression (or grammar/automaton) which accepts an infinite language (i.e. an expression with the * operator, or an automaton with a loop), your construction doesn't work anymore (you get an infinite grammar/automaton).

The answer by David Richerby provided an example of a regular language whose permutation language is not regular anymore – all such examples are infinite languages.

Answer 3

Let $\Sigma$ be an alphabet of size $n$. A regular expression describing all permutations of $\Sigma$ must have exponential size. This follows from Theorem 9 in Lower bounds for context-free grammars, which gives an exponential lower bound on the much stronger model of context-free grammars (a regular expression of size $m$ can be converted to a context-free grammar of size $O(m)$).

So in some sense, there is no succinct way to specify all permutations of a word.

---

Here is a simple proof for a $\tilde\Omega(2^n)$ lower bound on the size of a regular expression for the language of all permutations of an alphabet $\Sigma$ of size $n$. Since a regular expression of size $m$ can be converted to an NFA with $O(m)$ states, it suffices to give a lower bound on NFAs.

We will use the fooling set method, which we now describe. Let $L$ be a language, and let $(x_i,y_i)_{1 \leq i \leq N}$ be a collection of pairs of words such that:

• $x_iy_i \in L$.
• If $i \neq j$ then either $x_i y_j \notin L$ or $x_j y_i \notin L$.

Then every NFA for $L$ contains at least $N$ states. Indeed, consider any NFA for $L$. For each $i$, consider some accepting computation of $x_iy_i$, and let $q_i$ be the state that the NFA is in after reading $x_i$ in this accepting computation. I claim that $q_i \neq q_j$ for $i \neq j$. Indeed, if $q_i = q_j$ then a "cut-and-paste" argument shows that both $x_iy_j$ and $x_jy_i$ are in $L$, contrary to assumption.

Now we can prove the lower bound on NFAs for the language $L_n$ of all permutations of the symbols $\sigma_1,\ldots,\sigma_n$; we assume for simplicity of exposition that $n$ is even. For each subset $S$ of $\sigma_1,\ldots,\sigma_n$ of size $n/2$, let $x_S$ consist of all symbols in $S$ in some arbitrary order, and let $y_S$ consist of all symbols not in $S$ in some arbitrary order. Clearly $x_Sy_S \in L_n$. Conversely, if $S \neq T$ then $x_S y_T \notin L_n$. This shows that every NFA for $L_n$ contains at least $\binom{n}{n/2} = \Omega(2^n/\sqrt{n})$ many states.

Answer 4

Why there is no way to write "permutation of" in Regexes

A permutation of a regular, infinite language (infinite amount of words) is not necessarily regular. Thus, it can't be written as regex.

Proof

Think of of the language (ab)*. (Example inspired by David Richerby.) One of its permutations is a*b*. This is not a regular language. qed.