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|
Confused About the Answer? Ask for Details Here
Know Explanation? Add it Here

Similar Questions:

Let Σ = {a, b} and language L = {aa, bb}. Then, the complement of L is
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?
Which of the regular expressions corresponds to this grammar ?

S → AB / AS, A → a / aA, B → b
Match the following :

(i) Regular Grammar                           (a) Pushdown automaton
(ii) Context free Grammar                   (b) Linear bounded automaton
(iii) Unrestricted Grammar                  (c) Deterministic finite automaton
(iv) Context Sensitive Grammar        (d) Turing machine
     
(i)   (ii)   (iii)  (iv)
Which of the following definitions generates the same Language as L, where
L = {WWR | W ∈ {a, b}*} 
From the given data below:

a b b a a b b a a b

which one of the following is not a word in the dictionary created by LZ-coding (the initial words are a, b)?
Assume, L is regular language. Let statements S1 and S2 be defined as :

S1 : SQRT(L) = { x| for some y with |y| = |x|^2, xy ∈L}
S2 : LOG(L) = { x| for some y with |y| = 2^|x|, xy ∈ L}

Which of the following is true ?
The language accepted by a Push down Automata:
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 ?
Match the following :

List - I                                                             List - II
(a) {a^n b^n|n > 0} is a deterministic                  (i) but not recursive language
context free language        
(b) The complement of {a^n b^n a^n|n > 0}         (ii) but not context free language
is a context free language
(c) {a^n b^n a^n} is context sensitive language (iii) but can not be accepted by a deterministic pushdown automation
(d) L is a recursive language                         (iv) but not regular

Codes :
     (a)   (b)   (c)   (d)

View All Questions on: Theory of Computation(TOC)

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.