Finite Automata


Q21.

Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M)\cap L(N) is___________
GateOverflow

Q22.

The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0+1)*(10) is __________.
GateOverflow

Q23.

How many states are there in a minimum state deterministic finite automaton accepting the language L=\left\{w \mid w \in\{0,1\}^{*}\right., number of 0's is divisible by 2 and number of 1's is divisible by 5, respectively }?
GateOverflow

Q24.

The number of states required by a Finite State Machine,to simulate the behavior of a computer with a memory capable of storing 'm' words, each of length 'n' bits is?
GateOverflow

Q25.

Consider the finite automaton in the following figure. What is the set of reachable states for the input string 0011?
GateOverflow

Q26.

Which of the regular expressions given below represent the following DFA? I) 0*1(1+00*1)* II) 0*1*1+11*0*1 III) (0+1)*1
GateOverflow

Q27.

What are the final states of the DFA generated from the following NFA?
GateOverflow

Q28.

What is the complement of the language accepted by the NFA shown below? Assume \sum={a} and \varepsilon is the empty string.
GateOverflow

Q29.

Consider the DFA A given below. Which of the following are FALSE? 1. Complement of L(A) is context-free. 2. L(A) = L((11*0+0) (0+1)*0*1*) 3. For the language accepted by A, A is the minimal DFA. 4. A accepts all strings over {0, 1} of length at least 2.
GateOverflow

Q30.

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are
GateOverflow