edited by
22,935 views
41 votes
41 votes

The string $1101$ does not belong to the set represented by

  1. $110^*(0 + 1)$
  2. $1(0 + 1)^*101$
  3. $(10)^*(01)^*(00 + 11)^*$
  4. $(00 + (11)^*0)^*$
edited by

7 Answers

Best answer
52 votes
52 votes

Only (a) and (b) can generate $1101$.

In (c) after $11$, we can not have $01$ and so $1101$ cannot be generated.

In (d) Every $11$ followed by $0$ and no single occurrence of $1$ is possible. So it cannot generate $1101$ or $11011$.

edited by
10 votes
10 votes

I think option (c) is more appropriate to choose from, because even option (d) can generate 11011 or 110110 in which 1101 is a substring.

2 votes
2 votes

option d is quite inviting to choose it as we can have only even number of 1's with this regular set where as our original string contains 3 1's

Answer:

Related questions

29 votes
29 votes
5 answers
1
Arjun asked Oct 17, 2014
8,696 views
Give a regular expression for the set of binary strings where every $0$ is immediately followed by exactly $k$ $1$'s and preceded by at least $k$ $1$’s ($k$ is a fixed...
37 votes
37 votes
4 answers
2
Kathleen asked Sep 25, 2014
11,109 views
If the regular set $A$ is represented by $A = (01 + 1)^*$ and the regular set $B$ is represented by $B = \left(\left(01\right)^*1^*\right)^*$, which of the following is t...
23 votes
23 votes
3 answers
4
Kathleen asked Sep 25, 2014
6,323 views
Which of the following statements is false?Every finite subset of a non-regular set is regularEvery subset of a regular set is regularEvery finite subset of a regular set...