# RE for language not containing consecutive a's

Page 1 of 1

## 6 Replies - 6463 Views - Last Post: 17 February 2019 - 07:03 AM

### #1 mrsenim

• New D.I.C Head

Reputation: 1
• Posts: 32
• Joined: 28-January 10

# RE for language not containing consecutive a's

Posted 23 April 2010 - 10:35 AM

Hello!

I am trying to solve following question but I am cofused in "not containing" condition.

Q:
Give regular expressions of the following languages over
Σ={a,b}: All strings having no pair of consecutive a's.

Following is my regular expression

A:
(b+ab)*(^+a)(b+ba)*



I am not sure if my RE fulfils the condition of language or not but I have taken the idea from
www(.)cs(.)odu(.)edu/~toida/nerzic/390teched/regular/reg-lang/examples(.)html -->> Ex:8

Thanks!

Is This A Good Question/Topic? 0

## Replies To: RE for language not containing consecutive a's

### #2 mrsenim

• New D.I.C Head

Reputation: 1
• Posts: 32
• Joined: 28-January 10

## Re: RE for language not containing consecutive a's

Posted 23 April 2010 - 11:54 AM

mrsenim, on 23 April 2010 - 09:35 AM, said:

Hello!

Q:
Give regular expressions of the following languages over
Σ={a,b}: All strings having no pair of consecutive a's.

Thanks!

Sorry I also need to know the regular expression of

All strings having exactly two b’s or three b’s not more than it, for the same above language.

I have tried it as follows:

aa* + a*bba* + a*bbba*

OR

aa* + a*(bb+bbb)a*

This post has been edited by mrsenim: 23 April 2010 - 12:15 PM

### #3 mojo666

Reputation: 409
• Posts: 883
• Joined: 27-June 09

## Re: RE for language not containing consecutive a's

Posted 23 April 2010 - 01:00 PM

Your first question: I think your answer is correct, but the last part is not needed. (b+ab)*(^+a)(b+ba)* and (b+ab)*(^+a) produce the same strings.

Your second question: aa* + a*bba* + a*bbba* is incorrect since it is possible to produce strings containing only a's. a*bba* + a*bbba* is still incorrect since it only accounts for consecutive b's. Your expression should be able to produce "ababa". change both a*bba* and a*bbba* to allow any number of a's in between each of the b's and you should be set.

### #4 mrsenim

• New D.I.C Head

Reputation: 1
• Posts: 32
• Joined: 28-January 10

## Re: RE for language not containing consecutive a's

Posted 24 April 2010 - 10:37 AM

mojo666, on 23 April 2010 - 12:00 PM, said:

Your second question: aa* + a*bba* + a*bbba* is incorrect since it is possible to produce strings containing only a's. a*bba* + a*bbba* is still incorrect since it only accounts for consecutive b's.

Yes that is right. But since single b is not allowed in this language so I think abab or ababab can't occur in this language.

What do you think about it?

mojo666, on 23 April 2010 - 12:00 PM, said:

Your expression should be able to produce "ababa". change both a*bba* and a*bbba* to allow any number of a's in between each of the b's and you should be set.

Do you mean something like a*ba*ba* + a*ba*ba*ba* ?

Thank You!

### #5 just_saying

• New D.I.C Head

Reputation: 0
• Posts: 1
• Joined: 17-February 19

## Re: RE for language not containing consecutive a's

Posted 17 February 2019 - 03:12 AM

According to me, it should be (a+(b+ba+bab)*) .

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12680
• Posts: 45,863
• Joined: 27-December 08

## Re: RE for language not containing consecutive a's

Posted 17 February 2019 - 05:39 AM

Try instead (a + a(b+ba)*) + \epsilon .

Your regular expression misses strings like ab and the empty string. Note that bab is captured by (b+ba)*.

### #7 andrewsw

• never lube your breaks

Reputation: 6829
• Posts: 28,318
• Joined: 12-December 12

## Re: RE for language not containing consecutive a's

Posted 17 February 2019 - 07:03 AM

Bear in mind that this topic is from 2010.

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }