The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
95 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 (1.1k points)
reshown by | 95 views
0
is(1+01)*(0+00+epsilon)(1+01)* correct?

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 (18.3k points)
selected by
0
Got it bro :)


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

39,752 questions
46,767 answers
140,664 comments
58,538 users