finite automata

Consider a finite state machine (FSM) with one input X and one output f, represented by the given state transition table. The minimum number of states required to realize this FSM...

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?

Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?

Consider the following language. L = { w ∈ {0, 1}* | w ends with the substring 011} Which one of the following deterministic finite automata accepts L?

Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_...

Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_...

The lexical analysis for a modern computer language such as java needs the power of which one of the following machine model in a necessary and sufficient sense?

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...

If $$s$$ is a string over $${\left( {0 + 1} \right)^ * }$$ then let $${n_0}\left( s \right)$$ denote the number of $$0'$$ s in $$s$$ and $${n_1}\left( s \right)$$ the number of $$1...

Let $${N_f}$$ and $${N_p}$$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let $${D_f}$$ and...

Consider the following two statements; $${S_1}\,\,:\,\,\left\{ {{0^{2n}}\left| {n \ge 1} \right.} \right\}$$ is a regular language $${S_2}\,\,:\,\,\left\{ {{0^m}{1^n}{0^{m + n}}\le...

Consider the regular expression $$(0+1)(0+1).......n$$ times. The minimum state finite automation that recognizes the language represented by this regular expression contains:

Let $$L$$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite-state automaton accepting $$L$$ is

Which one of the following is not decidable?