Bissoy.com
Doctors Medicines MCQs Q&A

Let L be the language represented by the regular expression Σ∗0011Σ∗ where Σ={0, 1}. What is the minimum number of states in a DFA that recognizes L̅ (complement of L)?

Let L be the language represented by the regular expression Σ∗0011Σ∗ where Σ={0, 1}. What is the minimum number of states in a DFA that recognizes L̅ (complement of L)? Correct Answer 5

Number of states in DFAs accepting L and L̅ is always equal.

DFA accepting (0+1) * 0011 (0+1)* is:

[ alt="z,042" src="//storage.googleapis.com/tb-img/production/17/05/z%2C042.JPG">

Hence DFA accepting L̅ will be

[ alt="z,044" src="//storage.googleapis.com/tb-img/production/17/05/z%2C044.JPG">

It has 5 states.

Related Questions

Which of the following statements about Regular Expression is/are incorrect? A. The union of two regular expressions is also a regular expression B. The concatenation of two regular expressions is also a regular expression C. The iteration of a regular expression is also a regular expression
Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable? I. Given a regular expression R and a string w, is w ∈ L(R)? II. Given a context-free grammar G, is L(G) = ϕ? III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑? IV. Given a Turing machine M and a string w, is w ∈ L(M)?  
Let P be a regular language and Q be a context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q*and Q be |pnqn | n ϵ N}). Then which of the following is ALWAYS regular?
Let L ⊆ {0,1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states? 
In a certain number system there are only two notations to represent numbers: @ and %. 0 is represented by @ and 1 by %. The subsequent numbers are represented in the following manner: 2 is represented as %@, 3 is represented as %%, 4 is represented as %@@, 5 is represented as %@% and so on. Based on this coded language, answer the following questions: What number is represented by %%@%@%%?
With reference to Automaton to Regular Expression Conversion, for each of the n rounds, where n is the number of states of DFA, we can _________ the size of the regular expression constructed.
Let the given DFA consist of x states. Find x-y such that y is the number of states on minimization of DFA?
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.
A word is represented by only set of numbers as given in any one of the alternatives. The sets of numbers given in the alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are number alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are numbered from 0 to 4 and that of Matrix-II are numbered from 5 to 9. A letter from these matrices can be represented first by its row and next by its column, for example ‘A’ can be represented by 10, 75 etc and ‘B’ can be represented by 44, 79 etc. Similarly, you have to identify the set for the word ‘FOLDER’.  Matrix I    Matrix II   0 1 2 3 4   5 6 7 8 9 0 H L F M I 5 E I C J G 1 A U W S E 6 P R U S K 2 R Y C Z O 7 A W O D B 3 K T X V J 8 O T V Q L 4 D Q G P B 9 H N D M F
A word is represented by only set of numbers as given in any one of the alternatives. The sets of numbers given in the alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are number alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are numbered from 0 to 4 and that of Matrix-II are numbered from 5 to 9. A letter from these matrices can be represented first by its row and next by its column, for example ‘T’ can be represented by 02, 98 etc and ‘E’ can be represented by 12, 59, 97 etc. Similarly, you have to identify the set for the word ‘FAMILY’.  Matrix I    Matrix II   0 1 2 3 4   5 6 7 8 9 0 I M T K G 5 O C M R E 1 O R E Z X 6 J S F W Y 2 A G W U N 7 P I V N G 3 Q S L A H 8 L U B K W 4 J F V P B 9 H Q E T D