Has anyone studied the consequences of the Kleene star in regular expressions to

Question

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?

Explanation / Answer

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+={a1a2?ak?k?1,a1,

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.