Consider the DFA $A$ given below.
Which of the following are FALSE?
Note :
Correct Answer: $D$
@Praveen Saini Sir, in
Can we say that p$^{*}$q$^{*}$ $=$ p$^{*}$ + q$^{*}$?
@ayushsomani
NO, p*+q*(any number of p OR any number of q) is a subset of p*q*(any numer of p followed by any number of q)
One way to interpret this is as follows;
Given DFA accepts either of two languages:
1. Language with strings starting with 0.
2. Language with strings starting with 1 AND containing a 0.
Taking the union of two gives the "Languages having the strings containing a 0".
Complement of a regular language is also a regular language.
Option 2 can be checked to be true from the dfa given in q itself. No need to simplify.
For MIN-DFA
The language accepted by the string is: Contains at-least one $0$.Thus the reg exp: $1^*0(0+1)^*$
Hence Min-DFA:-
- Pic from : @Praveen Saini Sir.
Thus option 3 and 4 are false straightaway.
L(A) is regular and its complement is also regular (by closure property) and every regular is CFL also. So Complement of LA is context-free. The regular expression corresponding to the given FA is Hence we have regular expression: (11*0 +0) (0+1)* Since we have (0+1)* at the end so if we write 0*1* after this it will not have any effect, the reason is whenever string ends with the terminals other than 1*0* there we can assume 1*0* as epsilon. So it is equivalent to (11*0 +0) (0+1)*0*1* The given DFA can be minimised, since the non-final states are equivalent and can be merged and the min DFA will have two states which is given below: Hence statement 3 is false. Since DFA accept string “0” whose length is one, so the statement “A accepts all strings over {0, 1} of length at least 2” is false statement.
64.3k questions
77.9k answers
244k comments
80.0k users