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

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