Theory of computation miscellaneous

Theory of computation miscellaneous

Easy Questions

Theory of Computation

Theory of computation miscellaneous

Direction: Consider the following Finite State Automata:

  1. The minimum state automata equivalent to the above FSA has the following number of states








  1. View Hint View Answer Discuss in Forum

    The behaviour as per the given PDA is an seen below
    q0 to q1 → b*a
    q1 to q2 → (a + b) *
    Regular expression = b * a (a + b)*

    Correct Option: B

    The behaviour as per the given PDA is an seen below
    q0 to q1 → b*a
    q1 to q2 → (a + b) *
    Regular expression = b * a (a + b)*

  1. The language accepted by this automata is given by the regular expression








  1. View Hint View Answer Discuss in Forum

    The FSA as obtained in the previous question is b* a (a + b)*
    The minimum number of states are thus given by

    q0 and q1 are the state: that are required at most and hence the minimum number of states is 2 (q0 and q1).

    Correct Option: B

    The FSA as obtained in the previous question is b* a (a + b)*
    The minimum number of states are thus given by

    q0 and q1 are the state: that are required at most and hence the minimum number of states is 2 (q0 and q1).

  1. A minimum state deterministic finite automata accepting the language L = {W | W ∈ {0, 1}*, number of 0's and 1's in W are divisible by 3 and 5, respectively as.









  1. View Hint View Answer Discuss in Forum

    It is given that the 0's and 1's are divisible by 3 and 5 and we know that 3 and 5 do not have any factor other than themselves or 1 i.e., these cannot be further breakdown.
    Therefore, number of states = 3 × 5 = 15
    The schematic representation is as follows:

    Correct Option: A

    It is given that the 0's and 1's are divisible by 3 and 5 and we know that 3 and 5 do not have any factor other than themselves or 1 i.e., these cannot be further breakdown.
    Therefore, number of states = 3 × 5 = 15
    The schematic representation is as follows:

  1. Which of the following is true?









  1. View Hint View Answer Discuss in Forum

    Finite subset of non-regular set is regular as we know that Pumping Lemma can be applied on all the finite sets that states that all finite sets are regular. Infinite union of finite set is not regular because regular sets can never be closed under infinite union.

    Correct Option: B

    Finite subset of non-regular set is regular as we know that Pumping Lemma can be applied on all the finite sets that states that all finite sets are regular. Infinite union of finite set is not regular because regular sets can never be closed under infinite union.

  1. Given below are two finite state automata ( → indicates the start state and F indicates a final state)

    Which of the following represents the product automata Z × Y?








  1. View Hint View Answer Discuss in Forum

    Given : Transition table for Y and Z
    The number of states of Z = 2
    The number of states of Y = 2
    Z × Y

    No. of states of the product of Z and Y = 2 × 2 = 4
    Now, the states as per the given options are P, Q, R and S. The finite state automata is

    Correct Option: A

    Given : Transition table for Y and Z
    The number of states of Z = 2
    The number of states of Y = 2
    Z × Y

    No. of states of the product of Z and Y = 2 × 2 = 4
    Now, the states as per the given options are P, Q, R and S. The finite state automata is