The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
Options are

a) (0*10*1)*

b) 0*(10*10*)

c) 0*(10*1)*0*

d) 0*(10*1)*10*


I have doubt in b and c.which one is correct and why.?
asked in Theory of Computation by Active (2k points) | 1.5k views

6 Answers

0 votes
IT would be option c
answered by Junior (751 points)
0 votes
Answer is C, Check for string 110 neither a) nor b) can express it, and since d) is clearly expressing strings containing odd number of 0's so option c is correct. Moreover, option b) is expressing strings containing only two 1's, in case you have not done a typo. ;)
answered by Boss (14k points)
in c check for 110011
It can be represented.
Use the RE once to generate 110 and then use it to generate 011, & concatenate them.

you are using RE 2 times . 

after generating 110 it will over but if the RE will like this (0*(10*1)*0*)* then you can do it .

Yes, you are right, I am sorry,I did not cared that we can only use one time.
so none of the options are matchin
Yeah! None of the options are matching for sure. Possibly there is some mistake in the question.
0 votes
ans is None of the options are matching .

For A check with 110

For B and C check with 110011

for D this is pretty much obvious that it can support odd length also .
answered by Boss (10.4k points)

You are right..and if b) were  0*(10*10*)*..then it would be answer. 

0 votes
clearly none of the answers actually match .try 110011 as already mentioned. .. I dont think ambiguous questions will be given in GATE.
answered by Active (2.6k points)
0 votes

Option b and d is eliminated because it doesn't produce epsilon . Epsilon has also even no of 1's.

Option a can't produce 110. so a is also eliminated.

So Ans is option C

answered by (121 points)
0 votes
Option A will accept either epsilon or a string that is ending with 1 only,It may happen that string have even no. of 1's but it is ending with 0,So it won't be right answer.

Option B will generate string having only 2 1's,so it won't be the right answer because we are looking for that solution that may generate even strings having even no. of 1's.

Option C will generate string having even no. of 1's so it will be the correct answer.

Option D will generate string having odd no. of 1's so definitely it is not going to be the right answer.

So,according to me C will be the right Regex for generating string having even no. of 1's.

Correct me if I'm wrong.
answered by (37 points)

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

46,668 questions
51,139 answers
66,556 users