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!

up vote 0 down vote accepted

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..

  • So, can you concatenate as many strings as you want? For example: r = (blah + blah + blah +......) – Phoenixdeath Feb 17 '17 at 5:57
  • If the language is finite then we can. – Deep Joshi Feb 17 '17 at 5:59
  • Oh, I see. Thanks for the help! – Phoenixdeath Feb 17 '17 at 6:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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