The Gateway to Computer Science Excellence
0 votes

Given L = { 0*1 + 0 + 1* + 10*1}

where + symbol is UNION and NOT positive closure.

Please draw the Minimal DFA for this.

in Theory of Computation by Loyal (8.4k points) | 112 views


Starting  state is also final state.


Hi Bhai, nice to see you after so much time. I hope you're doing good.

Anyways, in the DFA you made, did you take all the languages individually and then made DFA for each of them and then club the DFAs because of the UNION?

or pehle baar mein he poora ek DFA bna diya aapne?



Thanks bhai. Yes, b/c of epsilon initial = final state, right?



Is there a simple way to draw DFA for this. I couldn't able to make it correct.


@abhishekmehta4u , Thanks bhai. edited.

@iarnav bhai, I have not made it by taking union of individual DFAs but I think right procedure is to make DFAs for individual component of this regular expression and then union of them and then minimize it.

First, I have written language as L={0,1,11,111,1111,...1*.........,01,001,0001,.....0*1,......101,1001,10001,.....10*1}

Then I observed the pattern of the strings, here 1* is one type of strings , 0*1 is another type of strings and by appending initially 1 in it then I got another type of strings 10*1 and one single 0....

Now I thought how to make DFA for it. So, I have to accept one string 0 first. So I made it by 2 states. Now, for 1* , I made it by accepting 11 first then by making loop of 1 on it. if I accept 1 initially and then make loop of 1 on it then there will be a problem for 10*1...Now I accepted 001 first and make a loop of 0 in middle. So I accepted 00*1 first. If I accept 01 first then there will be a problem for 0*1. So, I accepted 01 later. Since, I have already accepted 0*1 then I had no problem to append initially 1 by some state transition.

It takes some time to think and needs practice but take less time by making individual DFAs and then union of them. I also made it after 2-3 wrong attempts and I missed epsilon in language and made wrong DFA.  




Thank you for such a detailed explanation.

May you please check my DFA, isme kya galti hai?

bhai, it will accept strings like 00,000,110,1100,1110,11001 which are not in the language.
Oh, right. Thank you! :)

@ankitgupta.1729.   Bhai sorry to bother, but kya given language mein epsilon generate ho Raha hai? 

Yes bro,
Language contain 1* = null, 1,11...
haan bhai.. 1* epsilon,1,11,111,..dega to sabhi ka union  karne ke baad epsilon language me hoga..
Thanks both of you, very much appreciated. 🙏

2 Answers

0 votes

HI is this dfa fine>??

by (17 points)
$\varepsilon$  should also be accepted..
0 votes
by (205 points)

01 is rejected in your dfa.

6 states is what i am getting.correct me if i am wrong.

D is dead state A is starting state ,states with(*) are final states.

  0 1
->A* B* E*
B* B* C*
C* D D
E* B* F*
F* D



00 is not generate by the regular expression,but the table you've given is accepting it.
Thanks for pointing out the error. I think if we just add a transition of 1 from B to F , it will work fine.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,280 answers
104,840 users