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 (1.9k points) | 1.4k views

6 Answers

0 votes
IT would be option c
answered by Junior (731 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 (13.7k 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.2k 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 (93 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 (21 points)

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

37,977 questions
45,471 answers
48,426 users