Q. Given Language: L= {ab U aba}*
If X is the minimum number of states for a DFA and Y is the number of states to construct the NFA,

|X-Y|=?

View solution

Q. An automaton that presents output based on previous state or current input:

View solution

Q. If NFA of 6 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is ?

View solution

Q. NFA, in its name has ’non-deterministic’ because of :

View solution

Q. Which of the following is correct proposition?
Statement 1: Non determinism is a generalization of Determinism.

Statement 2: Every DFA is automatically an NFA

View solution

Q. Given Language L= {xϵ {a, b}*|x contains aba as its substring}
Find the difference of transitions made in constructing a DFA and an equivalent NFA?

View solution

Q. The construction time for DFA from an equivalent NFA (m number of node)is:

View solution

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?

View solution

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