Give a regular expression for a language on Σ={a,b,c} that accepts all strings containing no more than three a.'s

WBahn

Joined Mar 31, 2012
26,037
What does "exactly one three a.'s" mean????

That somewhere in the string there is exactly one occurrence of the substring "aaa"?

Your expressing can generate strings that contain NO a's at all.

Make a short list of strings that are in the language and strings that are not. Perhaps five or six strings in each list. Include some real short and simple ones and include some that are more complex.

Then show how your regular expression can generate the strings that are in the language and explain why it can't generate the strings that are not in the language.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
633
Sorry I made some mistake in the title. Question is related to "no more than 3 a's".
(b+c)* (c+b)*+ (b+c)*a(c+b)* + (b+c)* a(b+c)* a (c+b)* + (b+c)* a (b+c)*a (b+c)* a(c+b)*

I think the above one looks correct.

Zulfi.
 

WBahn

Joined Mar 31, 2012
26,037
Sorry I made some mistake in the title. Question is related to "no more than 3 a's".
(b+c)* (c+b)*+ (b+c)*a(c+b)* + (b+c)* a(b+c)* a (c+b)* + (b+c)* a (b+c)*a (b+c)* a(c+b)*

I think the above one looks correct.

Zulfi.
That looks correct, but your first term is too complicated since

(b+c)* (c+b)* = (b+c)*

Also, as a rule, you should not use (b+c)* in some places and (c+b)* in others. Pick one (since they are equivalent). Using both leads the reader to assume that they are not the same (or that you think that they are not the same).

You can also simplify your expression by noting that the last term covers everything as long as you can make the each a optional. How could you do that?
 
Top