Finite Automata
Q11.
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?Q12.
Suppose we want to design a synchronous circuit that processes a string of 0's and 1's. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1's by a 0. Consider the following example. \begin{array}{ll} \text{Input sequence:} & 00100011000011100 \\ \text{Output sequence:} & 00000001000001100 \end{array} A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input. The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables s, t, b and y respectively. Assume the initial state of the Mealy machine is 0. What are the Boolean expressions corresponding to t and y in terms of s and b?Q13.
Which one of the following regular expressions correctly represents the language of the finite automaton given below?Q14.
Let L be the language represented by the regular expression \Sigma ^{*}0011\Sigma ^{*} where \Sigma={0,1}. What is the minimum number of states in a DFA that recognizes \bar{L} (complement of L)?Q15.
Consider the following two statements: I. If all states of an NFA are accepting states then the language accepted by the NFA is \sum ^{*} . II. There exists a regular language A such that for all languages B, A\capB is regular. Which one of the following is CORRECT?Q16.
An FSM(finite state machine) can be considered to be a turing machine of finite tape lengthQ17.
The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)* (0+1)(0+1)* is _______.Q18.
Consider the language L given by the regular expression (a+b )* b (a+b ) over the alphabet {a, b}. The smallest number of states needed in a deterministic finite-state automation (DFA) accepting L is ___________.Q19.
Consider the following Deterministic Finite Automaton M.Let S denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of strings in S that are accepted by M isQ20.
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___________