Having difficulty grasping the concept of how a language and a regular expression are related. For example:

(In all cases, the alphabet is $\{0,1\}$)

The language $L = \{100,10,011\}$ ------> Regular expression.

So far, I have:

$(0+1)$ since you can have either $0$ or $1$ in the first part...but...I'm not sure what would follow after that...I've tried making a DFA for it but I feel like I'm overcomplicating it. Any help would be great since I'm fairly confused. Thanks!


1 Answer 1


If the language is finite like you have given in the question then regular expression is simple just write all string separated by $+$(union). So $$r = 100 + 10 + 011$$ further you have something common in first two string so $$r= 10(0+\epsilon) + 011$$

I feel like I'm overcomplicating it.

For that You need to learn three operators $*$ , $+$ and $.$ properly & understand the language given then It will be easy for you to make a regular expression without making a D.F.A..

  • $\begingroup$ So, can you concatenate as many strings as you want? For example: r = (blah + blah + blah +......) $\endgroup$ Commented Feb 17, 2017 at 5:57
  • $\begingroup$ If the language is finite then we can. $\endgroup$
    – Deep Joshi
    Commented Feb 17, 2017 at 5:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.