Home » Theory of Computation » Theory of computation miscellaneous » Question

Theory of computation miscellaneous

Theory of Computation

  1. Which one of the following languages over the alphabet {0 1} is described by the regular expression (0 + 1) * 0(0 + 1) *?
    1. The set of all strings containing the substring 00
    2. The set of all strings containing at most two 0's
    3. The set of all strings containing at least two 0's
    4. The set of all strings that begin and end with either 0 or 1.
Correct Option: C

We are given with the relation
(0 + 1) * 0(0 + 1)* 0(0 + 1)*
Here, the accepting languages are L = {00, 000, 100, 001, 010, 0000, 0001, 1000, 1001, 0100, 1100, 0010, 0011, 0110, 0101, 1010,...}
The common feature in the accepting languages can be seen that they consist of atleast two 0's.



Your comments will be displayed only after manual approval.