Time Left - 15:00 mins

GATE 2022: Theory Of Computation Quiz-1

Attempt now to get your rank among 300 students!

Question 1

Consider the following FSM.


Find the number of strings of length 5 accepted by the above machine.

Question 2

((((((r*)+)*)+)*)+)* + ϕ+ + ϕ = ?

Question 3

Language L has following string –
L= {abbbab,babba,bbbb,abab,abbbabb,aaabbabba……….}
Which of the following could be true ?

Question 4

Consider the following DFA

How does this DFA accepts string, which one of the following holds true?

Question 5

Consider a Mealy machine for performing 1's complement of the given binary string . And a Moore machine for performing 1's complement of the given binary string. Let the number of states in Mealy machine be 'x' and number of states in Moore machine be 'y'. Then find the value of 4x-y __________

Question 6

Consider a 4 states Moore machine which has 4 different outputs. When this Moore machine is converted into Mealy machine , then what is the maximum number of states possible in the Mealy machine _____________.
  • 300 attempts
  • 1 upvote
  • 0 comments
Aug 19GATE & PSU CS