The Gateway to Computer Science Excellence
0 votes
which one of the following regular expression describe the language over {a,b} consist of no pair of consecutive a’s?

a.    (b*abb*) (a+€)

b.    (b+ab)* (a+€)

c.     (b*abb*)*(a+€)+b*

d.    (b*ab*)*(a+€)+b*(a+€)

in Theory of Computation by Active (4.5k points) | 103 views

1 Answer

+1 vote
(b) is Correct.

(a) fails for L= {abab, ababa,..}, given regular expression doesn't represents {abab, ababa,..}. Observe this option is not capable of representing more than 2 a's in an expression. therefore abababa... and for all such expressions it will fail

(c) fails for L= {ba}, given regular expression doesn't represents {ba} which canbe easily observed

(d) fails because it represents aa,aaa,aaaa.., which it should not.
by Active (2.8k points)
edited by
Thank you

How A doesn't represent {a}

C doesn't represent {ba} explain
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,242 answers
95,943 users