The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
129 views
What will be the regular expression for the language consisting of all binary strings which have at most one pair of consecutive zeroes?
asked in Theory of Computation by Active (2k points)
reshown by | 129 views
0
is(1+01)*(0+00+epsilon)(1+01)* correct?
0
No. It generates 0001.

1 Answer

+5 votes
Best answer

Break it down into : "Exactly One Pair of Consecutive Zeroes" $+$ "NO pair of Consecutive zeroes"

Now,  

"Exactly One Pair of Consecutive Zeroes" =  $(1 + 01)^* \,00  (1+10)^*$

"NO pair of Consecutive zeroes" =  $(1 + 01)^*(0 + \in) $

So, Now combine these Two and We will have :

 The regular expression for the language consisting of all binary strings which have at most one pair of consecutive zeroes :

 $(1 + 01)^* \,00  (1+10)^*$  $+$   $(1 + 01)^*(0 + \in) $


(You could take  $(1 + 01)^*$ common and simplify further But for understanding purpose, let it be the way it is)

answered by Boss (23.4k points)
selected by
0
Got it bro :)

Related questions

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
48,437 questions
52,746 answers
183,345 comments
68,219 users