Theory of computation miscellaneous

Theory of computation miscellaneous

Easy Questions

Theory of Computation

Theory of computation miscellaneous
  1. The length of the shortest string NOT in the language (over ∑ = {a, b}) of the following regular expression is
    ______________.
    a*b* (ba)*a*








  1. View Hint View Answer Discuss in Forum

    a * b * (ba) * a *
    Length O is present (as it accepts ∈)
    Length 1 is present (a, b)
    Length 2 is present (aa, ab, ba, bb)
    Length 3 is not present (bab not present)
    ∴ it is 3

    Correct Option: B

    a * b * (ba) * a *
    Length O is present (as it accepts ∈)
    Length 1 is present (a, b)
    Length 2 is present (aa, ab, ba, bb)
    Length 3 is not present (bab not present)
    ∴ it is 3

  1. Let ∑ be a finite non-empty alphabet and let 2∑* be the power set of ∑*. Which one of the following is TRUE?








  1. View Hint View Answer Discuss in Forum

    ∑* is countabily finite 2∑* is power set of ∑*
    The powerset of countabily infinite set is uncountable
    ∴ 2∑* is uncountable and ∑* is countable.

    Correct Option: C

    ∑* is countabily finite 2∑* is power set of ∑*
    The powerset of countabily infinite set is uncountable
    ∴ 2∑* is uncountable and ∑* is countable.

  1. Let L1 = {w ∈ {0, 1}*| w has at least as many occurrences of (110)'s as (011)'s}. Let L2 = {w ∈ {0, 1}* | w has at least as many occurrences of (000)'s as (111)'s}. Which one of the following is TRUE?








  1. View Hint View Answer Discuss in Forum

    L1 is regular but L2 is not

    Correct Option: A

    L1 is regular but L2 is not

  1. Which of the regular expressions given below represent the following DFA?

    I 0*1(1+00*1)*
    II 0*1*1+11*0*1
    III (0+1)*1








  1. View Hint View Answer Discuss in Forum

    (I) 0 *1(1 + 0 0 *1)*
    (II) 0 *1*1+11*0 *1
    (III) (0 +1)*1
    (I) and (III) represent DFA.
    (II) Doesn't represent as the DFA accepts strings like 11011, but the given regular expression doesn't accept.

    Correct Option: B

    (I) 0 *1(1 + 0 0 *1)*
    (II) 0 *1*1+11*0 *1
    (III) (0 +1)*1
    (I) and (III) represent DFA.
    (II) Doesn't represent as the DFA accepts strings like 11011, but the given regular expression doesn't accept.

  1. Consider the finite automata in the following figure.

    Which is the set of reachable states for the input string 0011?








  1. View Hint View Answer Discuss in Forum

    Following paths can be taken by the finite Automata for the input string “0011”:––


    We note that no other path is possible for the input string "0011". So, finally union of all three cases gives us the set of Reachable states which is {q0, q1, q2}

    Correct Option: A

    Following paths can be taken by the finite Automata for the input string “0011”:––


    We note that no other path is possible for the input string "0011". So, finally union of all three cases gives us the set of Reachable states which is {q0, q1, q2}