Time Left - 30:00 mins

GATE 2020: TOC Rapid Mini Mock (App update required to attempt this test)

Attempt now to get your rank among 967 students!

Question 1

Consider the following graph.

Find which of the following is not a BFS traversal of above graph with ‘A’ as starting vertex

Question 2

The language accepted by a Pushdown Automaton in which the stack is limited to10 items is best described as

Question 3

Consider the transition table as given below

If A becomes an non-accepting state, then how many strings ending with 0 will be accepted (Maximum length of the string is n)

Question 4

Consider the following languages :

1) L = {(0+1)^* | it has equal number of occurrences of 01 and 10 }

2) L = Set of palindromes on unary alphabet

3) L = {ww^R | the strings of this language are limited upto length 100}

4) L = (0ⁿ1)^*

How many of the above languages are regular _______.

Question 5

Consider the following languages.

L1 = { aⁿ bⁿ c^m| m >= 0 and n >= 0 }
L2 = { a^m bⁿcⁿ| n >= 0 and m >= 0 }

L3 = L1 ∪ L2 = { aⁿbⁿc^m∪ a^mbⁿcⁿ| n >= 0, m >= 0 }

How many of the above language L₁, L₂, L₃ are context free language?

Question 6

Consider the following languages:
L1 = {ww|w∈{a,b} *}
L2 = {ww^R|w∈{a, b}*, w^Ris the reverse of w}
L3 = {0²ⁱ|i is a positive integer}
L3 = {

|i is an integer}
Which of the languages are regular?

Question 7

Find the number of DFA with 3 states which can be constructed over alphabet

with designated initial state and exactly 2 final states ___________.

Question 8

Consider the DFA A given below.

Which of the following are FALSE?
1. Complement of L(A) is context-free.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.

Question 9

Consider L be the set of all strings having exactly 1 ‘a’ and exactly 1 ‘b’ where Σ={a,b} . The number of states needed in the minimum states DFA accepting L is -

Question 10

Consider a language L={ab,ba,abab} represented in the form of DFA machine. Then what is the number of strings present in the function INIT(L) ?

Question 11

Given a language L, define

as follows:

The order of a language is defined as the smallest such that Consider the language (over alphabet 0) accepted by the following automaton.

The order of is ___________.

Question 12

Given the following state table of an FSM with two states A and B, one input and one output:

If the initial state is A = 0, B = 0, what is the minimum length of an input string which will take the machine to the state A= 0, B = 1 with Output = 1?

967 attempts
1 upvote
3 comments

Tags :

GATE & PSU CS Theory of Computation

Aug 16GATE & PSU CS