DFA

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?

Consider the following deterministic finite automaton (DFA) defined over the alphabet, $\Sigma = \{a, b\}$. Identify which of the following language(s) is/are accepted by the given...

Let Σ = {1,2,3,4}. For x ∈ Σ*, let prod(x) be the product of symbols in x modulo 7. We take prod(ε) = 1, where ε is the null string. For example, prod(124) = (1 × 2 × 4) mod 7 = 1....

Let $\Sigma=\{a, b, c\}$. For $x \in \Sigma^{\star}$, and $\alpha \in \Sigma$, let $\#_\alpha(x)$ denote the number of occurrences of a in $x$. Which one or more of the following o...

Let $\Sigma=\{1,2,3,4\}$ For $x \in \Sigma^*$, let prod $(x)$ be the product of symbols in $x$ modulo 7 . We take $\operatorname{prod}(\varepsilon)=1$, where $\varepsilon$ is the n...

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

Consider the 5-state DFA M accepting the language L(M) ⊂ (0+1)* shown below. For any string w ∈ (0+1)* let n₀(w) be the number of 0's in w and n₁(w) be the number of 1's in w. Whic...

Consider the language L over the alphabet {0, 1}, given below: $$L = \{ w \in {\{ 0,1\} ^ * }|w$$ does not contain three or more consecutive $$1's\} $$. The minimum number of state...

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

Consider the following language. L = {x $$ \in $$ {a, b}* | number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ___...

Let $\Sigma$ be the set of all bijections from $\{1, \ldots, 5\}$ to $\{1, \ldots, 5\}$, where id denotes the identity function, i.e. $\operatorname{id}(j)=j, \forall j$. Let $\cir...

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?

The minimum possible number of states of a deterministic finite automaton that accepts the regular language L = {w1aw2 | w1, w2 ∈ {a, b}*, |w1| = 2, |w2| ≥ 3} is

The number of states in the minimum sized $$DFA$$ that accepts the language defined by the regular expression $$${\left( {0 + 1} \right)^ * }\left( {0 + 1} \right){\left( {0 + 1} \...

Match the following: GROUP 1 GROUP 2 P. Lexical analysis 1. Graph coloring Q. Parsing 2. DFA minimization R. Register allocation 3. Post-order traversal S. Expression evaluation 4....

Let $$L$$ be the language represented by the regular expression $$\sum {^ * 0011\sum {^ * } } $$ where $$\sum { = \left\{ {0,1} \right\}} .$$ What is the minimum number of states i...

Which one of the following is TRUE?

Definition of the language $$L$$ with alphabet $$\left\{ a \right\}$$ is given as following. $$L = \left\{ {{a^{nk}}} \right.\left| {k > 0,\,n} \right.$$ is a positive integer cons...

Which one of the following is FALSE?

A minimum state deterministic finite automation accepting the language $$L = \left\{ {w\left| {w \in } \right.\,\,{{\left\{ {0,1} \right\}}^ * },\,\,} \right.$$ number of $$0'$$s a...

For $$s \in {\left( {0 + 1} \right)^ * },$$ let $$d(s)$$ denote the decimal value of $$s(e. g.d(101)=5)$$ Let $$L = \left\{ {s \in {{\left( {0 + 1} \right)}^ * }\left| {\,d\left( s...

Consider the regular language $$L = {\left( {111 + 11111} \right)^ * }.$$ The minimum number of states in any $$DFA$$ accepting this language is

Consider a $$DFA$$ over $$\sum { = \left\{ {a,\,\,b} \right\}} $$ accepting all strings which have number of $$a'$$s divisible by $$6$$ and number of $$b'$$s divisible by $$8$$. Wh...

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

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

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 automation accepting $$L$$ is

Which of the following sets can be recognized by a Deterministic Finite-state Automation?

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

Give minimal $$DFA$$ that performs as a Mod-$$3$$ $$1's$$ counter, i.e., outputs a $$1$$ each time the number of $$1's$$ in the input sequence is a sequence is a multiple of $$3.$$