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

#1 mrsenim   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • 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

Any suggestion please?

Thanks!

Is This A Good Question/Topic? 0
  • +

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

#2 mrsenim   User is offline

  • New D.I.C Head

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

Re: RE for language not containing consecutive a's

Posted 23 April 2010 - 11:54 AM

View Postmrsenim, 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*

Please help!

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

Was This Post Helpful? 0
  • +
  • -

#3 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#4 mrsenim   User is offline

  • New D.I.C Head

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

Re: RE for language not containing consecutive a's

Posted 24 April 2010 - 10:37 AM

View Postmojo666, 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?

View Postmojo666, 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!
Was This Post Helpful? 0
  • +
  • -

#5 just_saying   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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)*) .
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • 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)*.
Was This Post Helpful? 0
  • +
  • -

#7 andrewsw   User is offline

  • never lube your breaks
  • member icon

Reputation: 6829
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1