A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

Discussion Forum

Que. Let L be a set accepted by a non deterministic finite automaton. The number of states in non-deterministic finite automaton is |Q|. The maximum number of states in equivalent finite automaton that accepts L is
a. |Q|
b. 2|Q|
c. 2^|Q| – 1
d. 2^|Q|
Answer:2^|Q|

Similar Questions:

Given the following statements.

S1: The grammars S → asb | bsa |ss I a and s→ asb | bsa| a are not equivalent.
S2: The grammars S→. ss| sss | asb | bsa| λ and S → ss |asb |bsa| λ are equivalent.

Which of the following is true?
In parallel algorithm design, the process of grouping tasks into larger tasks in order to improve performance:
Let A = {x | -1< x< 1} = B. The function f(x)=x/2 from A to B is:
Which of the following is FALSE ?
The grammar with production rules S → aSb |SS|λ generates language L given by:
The statements s1 and s2 are given as:

s1: Context sensitive languages are closed under intersection, concatenation, substitution and inverse homomorphism.
s2: Context free languages are closed under complementation, substitution and homomorphism.

Which of the following is correct statement?
Regular expression for the language L = { w ∈ {0, 1}* | w has no pair of consecutive zeros} is
Which of the following is true while converting CFG to LL(1) grammar ?
Assume the statements S1 and S2 given as:

S1: Given a context free grammar G, there exists an algorithm for determining whether L(G) is infinite.
S2: There exists an algorithm to determine whether two context free grammars generate the same language.

Which of the following is true?
The number of states in a minimal deterministic finite automaton corresponding to the language L = { an | n≥4 } is

View All Questions on: Theory of Computation(TOC)

Start The Conversation:

Get it on Google Play

GATE CSE Resources

Questions from Previous year GATE question papers

UGC NET Computer science Resources

UGC NET Previous year questions and practice sets

GATE CSE Online Test

Attempt a small test to analyze your preparation level. This GATE exam includes questions from previous year GATE papers.

UGC NET practice Test

Practice test for UGC NET Computer Science Paper. The questions asked in this NET practice paper are from various previous year papers.