NFA

A regular language L is accepted by a non-deterministic finite automaton (NFA) with n states. Which of the following statement(s) is/are FALSE?

Let M be the 5-state NFA with \epsilon-transitions shown in the diagram below. Which one of the following regular expressions represents the language accepted by M?

Let $$N$$ be an $$NFA$$ with $$n$$ states. Let $$k$$ be the number of states of a minimal $$DFA$$ which is equivalent to $$N.$$ Which one of the following is necessarily true?

Let δ denote the transition function and $\hat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below: Then $\hat{\delta}(q_2,...

Consider the following two statements : $$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,$$ If all states of an $$NFA$$ are accepting states then the language accepted by the $$\,\,\,\,\,\,\,\,\,...

Which of the following decision problems are undecidable? $$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$NFAs$$ $${N_1}$$ and $${N_2},$$ is $$L\left( {{N_1}} \right)...

Let $$w$$ be any string of length $$n$$ in $${\left\{ {0,1} \right\}^ * }$$. Let $$L$$ be the set of all substrings of $$w.$$ What is the minimum number of states in a non-determin...

Given an arbitrary non-deterministic finite automaton $$(NFA)$$ with $$N$$ states, the maximum number of states in an equivalent minimized $$DFA$$ is at least

In which of the cases stated below is the following statement true? “For every non-deterministic machine $${M_1}$$ there exists an equivalent deterministic machine $${M_2}$$ recogn...

State whether the following statement is TRUE / FALSE. A minimal $$DFA$$ that is equivalent to an $$NFDA$$ with $$n$$ modes has always 2 n states