Theory of Computation (3160704) MCQs

MCQs of Regular Languages and Finite Automata

Showing 31 to 40 out of 65 Questions
1 2 3 4 5 6
31.
The transitional function of a NFA is
(a) Q X Σ→Q
(b) Q X Σ→2Q
(c) Q X Σ→2n
(d) Q X Σ→Qn
Answer:

Option (b)

32.
δ*(q,ya) is equivalent to:
(a) δ((q,y),a)
(b) δ(q,ya)
(c) δ(δ*(q,y),a)
(d) independent from δ notation
Answer:

Option (c)

33.
String X is accepted by finite automata if :
(a) δ*(q,x) ∈ A
(b) δ(q,x) ∈ A 
(c) δ(Q0,x) ∈ A
(d) δ*(Q0,x) ∈ A
Answer:

Option (d)

34.
Φ in minimal finite automata need _____________ no. of final states
(a) 1
(b) 2
(c) 3
(d) None
Answer:

Option (d)

35.
What is the relation between DFA and NFA on the basis of computational power?
(a) DFA > NFA
(b) NFA > DFA
(c) Equal
(d) Can’t be said
Answer:

Option (c)

36.
Subset Construction method used for:
(a) Conversion of NFA to DFA
(b) DFA minimization
(c) Eliminating Null references
(d) ε-NFA to NFA
Answer:

Option (a)

37.
Which method is useful to convert from regular expression to NFA?
(a) Subset Construction Method
(b) Power Set Construction Method
(c) Thompson's Rule
(d) Scott Construction Method
Answer:

Option (c)

38.
Every NFA accepts a:
(a) String
(b) Regular language
(c) Function
(d) Context-free language
Answer:

Option (b)

39.
An NFA’s transition function returns
(a) A state
(b) A Boolean value
(c) An edge
(d) A set of states
Answer:

Option (d)

40.
The relation between NFA-accepted languages and DFA accepted languages is
(a) >
(b) <
(c) =
(d) <=
Answer:

Option (c)

Showing 31 to 40 out of 65 Questions
1 2 3 4 5 6