Redirected
in Theory of Computation retagged by
1,421 views
1 vote
1 vote

What is the meaning of regular expression $\Sigma^*001\Sigma^*$?

  1. Any string containing ‘$1$’ as substring
  2. Any string containing ‘$01$’ as substring
  3. Any string containing ‘$011$’ as substring
  4. All string containing ‘$001$’ as substring
in Theory of Computation retagged by
by
1.4k views

1 comment

Clearly D , as the above can be represented as (1+0)*001(1+0)*, so 001 is a substring.
0
0

4 Answers

4 votes
4 votes
Best answer

∑* 001 ∑*

Here, ∑* means any string using the input alphabets  of any length(0 or more).

So, 001 is surrounded by ∑* that means that 001 should come as a substring in the complete string.

So, the correct option is: (D) All string containing '001' as substring

selected by
2 votes
2 votes

Substring =  A string which is "in" a larger string .

∑* 001 ∑* = A string could be very long But it should contain "001" as a substring.

option D) defines it best .

1 vote
1 vote
∑* means it may be zero or any string. The above regular expression should contain 001.
0 votes
0 votes
The regular expression does not generate $1$ which is a substring of itself. So A is not the answer.

The R.E. does not generate $01$ which is also a substring of itself. So B is also not the answer.

The R.E. does not generate $011$ which is also a substring of itself. So C is also not the answer.

Option D is correct as it generates every string containing $001$ as a substring.
Answer:

Related questions