Time Left - 20:00 mins
GATE CS : Theory of Computation Champion Quiz 1
Attempt now to get your rank among 1233 students!
Question 1
Identify the language accepted by the following deterministic finite automata over the input alphabet 
Question 2
Consider the following DFA's.
Which of the above DFA's are equivalent?
Which of the above DFA's are equivalent?
Question 3
Consider the following regular expression (RE).
RE=(a+b)*(a+b+epsilon)a
Which of the following is equivalent to the above RE?
RE=(a+b)*(a+b+epsilon)a
Which of the following is equivalent to the above RE?
Question 4
Find the minimum number of states in DFA that accepts a language where each string starts with 'a' and ends with 'ab' over Σ = {a,b}.
Question 5
How many minimum number of states required to construct a DFA that accepts a language represented by the regular expression 
Question 6
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.
The missing arcs in the DFA are
The missing arcs in the DFA are
Question 7
A minimum state deterministic finite automaton accepting the language 
number of 0s and 1s in w are divisible by 3 and 5, respectively}
number of 0s and 1s in w are divisible by 3 and 5, respectively} Question 8
Definition of a language L with alphabet {a} is given as following.
L= {ank | k>0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
Question 9
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.
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 10
Which of the following languages is regular?
- 1233 attempts
- 4 upvotes
- 55 comments
Nov 29GATE & PSU CS
