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 two statements:

A. L = {w|na(w) = nb(w)} is deterministic context free language, but not linear.
B. L = {an bn} U {an b2n} is linear, but not deterministic context free language.

Which of the following options is correct?
There are exactly ................ different finite automata with three states x, y and z over the alphabet {a, b} where x is always the start state.
Regular expression for the complement of language L = {a^n b^m I n ≥ 4, m ≤ 3} is
Which one of the following statement is false?
Given the following statements :

S1: SLR uses follow information to guide reductions.In case of LR and LALR parsers, the look-aheads are associated with the  Items and they make use of the left context available to the parser.
S2: LR grammar is a larger sub-class of context free grammar as compared to that SLR and LALR grammars. 

Which of the following is true ? 
Given a Turing Machine

M = ({q0,q1,q2,q3}, {a,b}, {a,b,B}, δ, B, {q3})

Where δ is a transition function defined as

δ(q0,a) = (q1,a,R)
δ(q1,b) = (q2,b,R)
δ(q2,a) = (q2,a,R)
δ(q2,b) = (q3,b,R)

The language L(M) accepted by the Turing Machine is given as:
The grammar ‘G1’

S ---> OSO| ISI | 0|1|∈

and the grammar  ‘G2’ is
S ---> as |asb| X,
X -----> Xa | a.

Which is the correct statement ?
Minimal deterministic finite automaton for the language L = {0n | n ≥ 0 , n ≠ 4} will have
The equivalent production rules corresponding to the production rules

S → Sα1 | Sα2 | β1 | β2 
We can show that the clique problem is NP-hard by proving that

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.