Finite Automata
Q12.
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?Q13.
Which one of the following regular expressions correctly represents the language of the finite automaton given below?Q14.
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 _______.Q15.
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 ___________.Q16.
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)?Q17.
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 isQ18.
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?Q19.
An FSM(finite state machine) can be considered to be a turing machine of finite tape length