The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
119 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.8k points)
reshown by | 119 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 (20.7k points)
selected by
0
Got it bro :)

Related questions

–1 vote
1 answer
7


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

44,235 questions
49,718 answers
163,882 comments
65,834 users