The Gateway to Computer Science Excellence

+44 votes

Best answer

+57

NFA for L = (0+1)*0011(0+1)* [ all strings that contain 0011 as substring]

Convert NFA to DFA

DFA for L = (0+1)*0011(0+1)* [ all strings that contain 0011 as substring]

DFA for $\bar{L}$ (complement of L) that doesn't contain 0011 as subtring

Note : No need to do this in such question DFA that contain substring having n length will have n+1 states and same with complement

+2

hi praveen, how did u convert the above NFA to DFA? i am getting more numbers of states in DFA... :(

+6

few of them get minimized, look carefully at final states in table you get after NFA to DFA conversion I am sure final states will get minimized to one final state

0

i am getting 6 states and 2 final states in DFA how do you convert it into dfa of 5 states. PLZ explain

0

Yes, in DFA, we must have transition for each symbol on each state, $Q \times \Sigma \rightarrow Q $.

0

@Praveen Saini sir Isn't it true that for an NFA with $n$ states we have its equivalent minimized DFA having $2^n$ states? Then shouldn't this NFA's DFA contain $2^5$ states?

+1

@ Praveen Saini sir,

By using this method for complement of a language:

To construct the DFA D that accepts the complement of L, simply convert each accepting state in A into a non-accepting state in D and convert each non-accepting state in A into an accept state in D.

if DFA D is minimized then is it always guranteed that reversal of dfa D' will be also always minimized?

0

Hi Praveen,

If we minimize the Regular Expression (0+1)*0011(0+1)* it becomes (0+1)*0011 (R*R*=R*) and proceed. Is it necessary that we show transition on last state of NFA?

If we minimize the Regular Expression (0+1)*0011(0+1)* it becomes (0+1)*0011 (R*R*=R*) and proceed. Is it necessary that we show transition on last state of NFA?

0

@ Karthik Selvam, language containing 0011 as a substring is different from language ending with 0011.

0

@Praveen Saini sir,

Note : No need to do this in such question DFA that contain substring having n length will have n+1 states and same with complement

Can I take it as a formula, which I can apply for all ???

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,696 answers

199,344 comments

107,372 users