CODEWITHSUNDEEP
regex
jn1kk
jn1kk

Reputation: 5102

Does this regular expression generate a regular language?

I was told that the language generated by the regular expression:

(a*b*)*

is regular.

However, my thinking goes against this, as follows. Can anyone please provide an explanation whether I'm thinking right or wrong?

My Thoughts

(a*b*) refers to a single sequence of any amount of a, followed by any amount of b (can be empty). And this single sequence (which can't be changed) can be repeated 0 or more time. For example:

   a* = a  
   b* = bbbb  
-> (a*b*) = abbbb  
-> (a*b*)* = abbbbabbbbabbbb, ...

On the other hand, since aba is not an exact repetition of the sequence ab, it is not included in the language.

aaabaaabaaab  => is included in the language  
aba           => is not included in the language

Thus, the language consists of sequences that are an arbitrary-time repetition of a subsequence that is any amount of a followed by any amount of b. Therefore, the language is not regular since it requires a stack.

Upvotes: 1

Views: 640

Answers (7)

GolezTrol
GolezTrol

Reputation: 116110

You're wrong. :)

0 is also an amount, so aba is in this language. It wouldn't be if the regex was (a+b+)+, because + would mean '1 or more' where * means '0 or more'.

Upvotes: 0

SLaks
SLaks

Reputation: 887375

* is not +.

aba is in that language; it's just an overly-complicated way to say "the set of all strings consisting of as and bs".

EDIT: The repeating group doesn't mean that the contents of the group must be repeated exactly; that would require a backreference. ((a*b*)?\1*)
Rather, it means that the group itself should be repeated, matching any string that it can match.

Upvotes: 1

Thomas Hupkens
Thomas Hupkens

Reputation: 1590

Basically, it'll match any string thats empty or made by a bunch of a and b. It reads:

(('a' zero or + times)('b' zero or + times) zero of plus times

That's why it matches aba:

(('a' one time)('b' one time)) one time ((a one time)(b zero time)) one time

Upvotes: 0

David Rodrigues
David Rodrigues

Reputation: 12532

It is a regular expression, yes.

The * say something like "can repeat 0 or more times". The + is basically similar, different only that it need one repeatition on minimal (or be 1 or more times).

This regular expressions says, somethink like:

  • Repeat "below group" zero or more times;
    • Repeat a zero or more times;
    • Repeat b zero or more times;

Can works fine with all of your examples.

Edit/Note: the aba is validated too.

I hope to help :p

Upvotes: 0

J-_-L
J-_-L

Reputation: 9177

It's wrong, you don't need a stack. Your DFA just thinks "can I add just another a (or not)?" or "can I add just another b (or not)?" in an endless loop until the word is consumed.

Upvotes: 0

stevecomrie
stevecomrie

Reputation: 2483

Technically /(a*b*)*/ will match everything and nothing.

Because all the operators are *'s it means zero or more. So since zero is an option, it will pretty much match anything.

Upvotes: 0

manji
manji

Reputation: 47978

It's a zero or more times, followed by b zero or more times, repeated zero or more times.

""
"a"
"b"
"ab"
"ba"
"aab"
"bbabb"
"aba"

all pass.

Upvotes: 4

Related Questions