5
$\begingroup$

Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"?

In other words, if * would always match as much as possible and no backtracking is allowed, would I still be able to express any regular language?

Let's say that @ is the possessive * operator.

There are cases where it doesn't matter: a*b and a@b both will match any string with 0 or more $a$ followed by a $b$.

However there are cases where being possessive is relevant: a.*b will match any string that starts with $a$ and ends with $b$ but a.@b will never match any string as the greedy @ will eat any character, including the ending $b$. The equivalent expression would be a[^b]@b.

One may be tempted to think that for any non-possesive expression there is an equivalent possessive expression and viceversa but I wasn't able to find any proof of this.

I'm limiting myself to * considering a+ equivalent to aa*.

As D.W. suggested in the comments below, I tried to start from the DFA. I didn't go much far, as this seems to have more to do with the way the non-determinism is handled, rather than with the structure of the automaton.

Could anyone point me in the right direction?

EDIT 3

I've posted an answer that I believe is correct.

EDIT 2

(REMOVED)

EDIT 1

(It has pointed out to me that the right term to use would be "possessive" (http://www.regular-expressions.info/possessive.html) rather than "greedy". Thanks.)

$\endgroup$
  • $\begingroup$ I would start by trying to prove that every regular language $L$ can be expressed using the $+$ and $@$ operators. Possible proof approach: If you start with a DFA for the regular language $L$, and then apply a standard NFA->regexp conversion algorithm (or some variant) to the DFA, can you use that to build up a regexp that uses $@$ instead of $*$ for $L$? Starting from a DFA might eliminate ambiguity that would cause $@$ to differ from $*$. Probably something will go wrong in the construction, but this is what I'd try first, to try to find out where the non-trivial part is. $\endgroup$ – D.W. Mar 24 '15 at 19:49
  • 1
    $\begingroup$ Alternatively, you could try adapting Brzozoswki's method for generating regular expressions. The key lemma is Arden's lemma: given an equation $X = AX+B$ where $A,B \subseteq \Sigma^*$ are given and the goal is to solve for $X \subseteq \Sigma^*$, the solution to the equation is $X=A^*B$ (assuming $A$ does not contain the empty string). We could ask whether there is a variation of Arden's theorem that expresses the solution using the $@$ operator instead of the $*$ operator. $\endgroup$ – D.W. Mar 24 '15 at 20:00
  • $\begingroup$ Could you define formally your operator @? $\endgroup$ – J.-E. Pin Mar 25 '15 at 0:16
  • $\begingroup$ Your definition of greedy seems at odds with what is commonly understood as greedy. The Kleene star * is already always greedy. $\endgroup$ – slebetman Mar 25 '15 at 4:27
  • 2
    $\begingroup$ @slebetman Kleene star is not always greedy. For example, the string $aa$ matches the regular expression $a^*a$ but it wouldn't if $a^*$ was forced to match both $a$s on its own. $\endgroup$ – David Richerby Mar 25 '15 at 8:53
4
$\begingroup$

I will share below my attempt to prove that you can express every regular language as a regular expression using just the $+$ and $@$ operators. Unfortunately, my attempt at a proof has a gap. Perhaps you can repair the gap. My attempt based upon Brzozoswki's method for generating regular expressions, so I'll assume you are already familiar with how that works.


First, some definitions and other preliminaries.

Definition. Define $A^+$ to be the language of one or more words from $A$, i.e., $A^+ = \{a_1 a_2 \cdots a_k \mid k \ge 1, a_1,\dots,a_k \in A\}$. In other words, $A^+ = A^* \setminus \{\epsilon\}$.

Definition. $\newcommand{\rp}{\backslash\backslash}$ For sets $A,B \subseteq \Sigma^*$, define $A\rp B$ by $A\rp B = (A^*\backslash B) - (A^+ \Sigma^*)$, where $A\backslash B$ is the left quotient, and $-$ represents the difference of two sets. In other words, $A\rp B$ is the smallest set $C \subseteq \Sigma^*$ such that $A^* B = A^* C$ and such that no word in $A^+$ is a prefix of any word in $C$.

Example: $\{01\}\rp \{0101010,101\} = \{0,101\}$.

Note that if $A,B$ are regular languages, then $A\rp B$ is also a regular language and can be computed effectively from $A,B$. (This follows from the standard closure properties of regular languages.)

Definition. The semantics of regular expressions using the $+$ and $@$ operators are defined inductively:

  • $L(w) = \{w\}$ if $w \in \Sigma^*$
  • $L(A_1+A_2+\dots+A_k) = L(A_1) \cup L(A_2) \cup \dots \cup L(A_k)$
  • $L(A^@ B) = \{ab : a \in L(A^*), b \in L(B), b \notin L(A^+ \Sigma^*)\}$
  • $L(w B) = \{wb : b \in L(B)\}$ if $w \in \Sigma^*$
  • $L(A^@) = L(A^*)$
  • $L((A_1+A_2)B) = L(A_1B + A_2 B)$, $L(A(B_1+B_2)) = L(AB_1 + AB_2)$
  • $L(A_1 A_2 \cdots A_k) = L(A_1 (A_2 \cdots A_k))$

(As a consequence, every regular expression using $+,@$ can be equivalently written as a sum of terms of the form $A_1 A_2 \cdots A_k$ where each $A_i$ is either of the form $w_i$ or $C_i^@$ for some $w_i \in \Sigma^*$ and some regular expression $C_i$ using $+,@$. Once it is rewritten in that sum-of-products form, the semantics of the resulting expression is given by the definition above.)

For instance, we have the following property: if there is no word in $L(A^+)$ that is a prefix of any word in $L(B)$, then $L(A^@ B) = L(A^* B)$.

In what follows, I won't try to distinguish between a regular expression $E$ and its corresponding language $L(E)$.

Now we can prove a generalization of Arden's lemma.

Lemma 1. Let $A,B \subseteq \Sigma^*$ be given, and assume $\epsilon \notin A$ and no word in $A^+$ is a prefix of any word in $B$. Suppose we have the equation $X=AX + B$ (i.e., $X=AX \cup B$). Then the least solution to this equation is $X=A^@ B$.

Proof. Arden's lemma says the least solution is $X=A^* B$. Now, since no word in $A^+$ is a prefix of any word in $B$, in fact $A^* B = A^@ B$, as there can be no ambiguity about how much the $*$ operator gobbles up.

Lemma 2. Let $A,B \subseteq \Sigma^*$ be given, and assume $\epsilon \notin A$. Suppose we have the equation $X=AX + B$ (i.e., $X=AX \cup B$). Then the least solution to this equation is $X=A^@ C$ where $C=(A\rp B)$.

Proof. Arden's lemma says the least solution is $X=A^* B$. As noted above, $A^* B = A^* C$. Moreover, no word in $A^+$ is a prefix of any word in $C$, so $A^* C = A^@ C$.

Now given any regular language $L$, we can apply Brzozoswki's method to it, but using Lemma 2 above instead of Arden's lemma. It's tempting to hope that the result will be a regular expression for $L$ that uses only the operators $+$ and $@$, but unfortunately there's a gap: I don't know whether one can prove that $A\rp B$ can be represented as a regular expression using only the $+$ and $@$ operators. So, this proof method has a big gaping hole in it.

But perhaps someone will see a way to build on this and prove the desired result.

$\endgroup$
  • $\begingroup$ @d-w Would you mind adding the formal definition of @ at the beginning of your answer? I asked the O.P. to do so, but he did not reply. This would be a great help. $\endgroup$ – J.-E. Pin Mar 26 '15 at 18:04
  • $\begingroup$ Sorry JE, I did not come out with a satisfactory formal definition, but I see your need for one. $\endgroup$ – Remo.D Mar 26 '15 at 20:13
  • $\begingroup$ @J.-E.Pin, good suggestion. I've added a formal definition of @ to my answer (in the 3rd definition) -- or, at least, my understanding/interpretation of what the OP presumably meant by @. Does it look right to you? $\endgroup$ – D.W. Mar 26 '15 at 20:56
  • $\begingroup$ @babou, yes, the definition of $L(AB)$ depends on the syntactic structure of $A$. There are four cases. If $A$ has the form $w$ (for some $w \in \Sigma^*$), use the 4th item in the list. If $A$ has the form $CD$ (a concatenation of two regexps), use the 7th item in the list. If $A$ has the form $C+D$ (a sum of two regexps), use the 6th item in the list. If $A$ has the form $C^@$ (an application of the $@$ operator), use the 3rd item in the list. This covers all the possibilities. See also the parenthetical remark after the definition. $\endgroup$ – D.W. Mar 27 '15 at 0:40
  • 1
    $\begingroup$ @babou, I'm with you. It does bother me too, but I couldn't see any other way to make sense of $@$ (it felt to me like this is inherent to $@$, since the meaning of $A^@ \dots$ depends on what appears in the $\dots$ part). That said, I'd be happy to be proven wrong on that. This may be one reason why we consider $*$ (Kleene star) to be natural in our study of formal languages and don't consider $@$ to be a natural operator. $\endgroup$ – D.W. Mar 27 '15 at 1:06
0
$\begingroup$

I believe I can prove that:

  • a RE using only possessive operators is equivalent to a RE without possessive operators.
  • any RE can be rewritten to an equivalent RE that uses only possessive operators.

For two expressions $A$ and $B$ to be equivalent means that they define the same language: $$A\equiv B \implies L(A) = L(B)$$

Let's mark with "$\hat{\ }$" the possessive operators.

I will use regular expression extended with the $\cap$ and $\neg$ operators.

1. Possessive Alternation

$$ A\ \hat{|}\ B \equiv A \ |\ (B \cap \neg A) $$

Which express the fact that if $A$ matches, $B$ is not even tried. In fact, if $A$ fails the only elements of $B$ that can match are those that are not in $B\cap A$, otherwise $A$ would have matched.

Actually, it's easy to see that: $$ A\ \hat{|}B\ \equiv A\ |\ B $$

because any string $s\in B$ will match $A\ |\ (B\cap \neg A)$, either because it is in $A\cap B$ (and hence in $A$) or because it's in $(B\cap \neg A)$. This means that it's not important to say if $|$ is possesive or not.

2. Possessive Repetition

$$ A \hat{*} B \equiv A * (B \cap \neg A) $$

In words: "$A\hat{*}B$ matches a, possibly empty, sequence of $A$ followed by an element of $B$ which is not in $A$".

The reason is that $A\hat{*}$ will consume any possible element of $L(A)$, including those element of $L(B)$ wich are in $L(B\cap A)$.

It's easy to see that: $A\cap B = \emptyset \implies A\hat{*}B \equiv A * B$

and that: $B\subset A \implies A\hat{*}B = \emptyset $

The last expressions explains why an expression like .@x can never match.

It is also clear that at the end of an expression $A\hat{*}\equiv A*$.

As usual, $A\hat{+} \equiv A A\hat{*}$

3. Non-possessive Repetition

We can also express the "greedy non-possessive repetition" using only possessive operators: $$A * B = A\hat{*} B\ |\ ((A\cap \neg B)\;\hat{*}\;(B \cap A))\hat{+} $$

The first term of the alterantion will match any sequence of $A$ followed by a $B$ that do not match $A$, the second will match the longest sequence of $A$ that end with a $B$ which is also in $A$ (otherwise it would have matched in the first alternation).

The non greedy version of $*$ (let's denote it with $*^?$) would be: $$A {*^?} B = A\hat{*} B\ |\ (A\cap \neg B)\;\hat{*}\;(B \cap A) $$

4. Optional Match

Reasoning in the same way, we can see that: $$ A \hat{?} B = A B \ |\ (B \cap \neg A) \\ A ? B = A \hat{?} B \ |\ (B \cap A) $$

5. Conclusions

Considering point 1-4 above, and reasoning by induction, we can prove that we can define any possible regular language using only possessive operators. Which answers my question.

6. Open points

  • Formality I'm well aware that what I wrote above is not a formal proof. I'm sure the reasoning is correct but a formal proof could highlight further details or additional hypotesis that are needed and I might have missed. Also, the properties of the possessive operators should be formalized (are they associative, left distributive, ...?).

  • Practicality Since I've used $\cap$ and $\neg$, it is left to determine if it is practical to use only possessive operators. There might be some RE that would become extremely complex to write with only possessive operators.

  • Speed Since there will be no ambiguities and the only source of backtracking is the alternate operator. I'm pretty sure that this means that the match can be done in linear time but it should be proven.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.