Question
a.
1/m^2
b.
2^m
c.
1/m
d.
log m
Posted under Formal Languages and Automata Theory
Engage with the Community - Add Your Comment
Confused About the Answer? Ask for Details Here.
Know the Explanation? Add it Here.
Q. If n is the length of Input string and m is the number of nodes, the running time of DFA is x that of NFA.Find x?
Similar Questions
Discover Related MCQs
Q. Which of the following option is correct?
View solution
Q. The number of tuples in an extended Non Deterministic Finite Automaton:
View solution
Q. What is wrong in the given definition?
Def: ({q0, q1, q2}, {0,1}, δ, q3, {q3})
View solution
Q. If δ is the transition function for a given NFA, then we define the δ’ for the DFA accepting the same language would be:
Note: S is a subset of Q and a is a symbol.
View solution
Q. What is the relation between DFA and NFA on the basis of computational power?
View solution
Q. If a string S is accepted by a finite state automaton, S=s1s2s3……sn where siϵ∑ and there exists a sequence of states r0, r1, r2…… rn such that δ(r(i), si+1) =ri+1 for each 0, 1, …n-1, then r(n) is:
View solution
Q. Subset Construction method refers to:
View solution
Q. Given Language:
Ln= {xϵ {0,1} * | |x|≥n, nth symbol from the right in x is 1}
How many state are required to execute L3 using NFA?
View solution
Q. If L is a regular language, Lc and Lr both will be:
View solution
Q. In NFA, this very state is like dead-end non final state:
View solution
Q. We can represent one language in more one FSMs, true or false?
View solution
Q. The production of form non-terminal -> ε is called:
View solution
Q. Which of the following is a regular language?
View solution
Q. Which of the following recognizes the same formal language as of DFA and NFA?
View solution
Q. Under which of the following operation, NFA is not closed?
View solution
Q. It is less complex to prove the closure properties over regular languages using
View solution
Q. Which of the following is an application of Finite Automaton?
View solution
Q. John is asked to make an automaton which accepts a given string for all the occurrence of ‘1001’ in it. How many number of transitions would John use such that, the string processing application works?
View solution
Q. Which of the following do we use to form an NFA from a regular expression?
View solution
Q. Which among the following can be an example of application of finite state machine(FSM)?
View solution
Suggested Topics
Are you eager to expand your knowledge beyond Formal Languages and Automata Theory? We've curated a selection of related categories that you might find intriguing.
Click on the categories below to discover a wealth of MCQs and enrich your understanding of Computer Science. Happy exploring!