0
$\begingroup$

folks. My question is about explaining the each step of regular expressions. The task is to find the regular expression that contains 101 as a substring. I already know that the regular expression for this is

$$ (0 + 1)^*101(0 + 1)^*. $$

The question is that how we should show each step for explaining the regular expressions.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ The regular expression 101 also contains 101 as a substring. I suspect you are looking for a regular expression whose language consists of all strings containing 101 as a substring. $\endgroup$ – Yuval Filmus Apr 11 '17 at 6:17
  • $\begingroup$ Sorry, but what you mean by that? I already explained what I should do. $\endgroup$ – Nijat Mursali Apr 11 '17 at 6:38
  • $\begingroup$ But you didn't explain it correctly. Also, what is your question to us? Be specific. Where do you get stuck? $\endgroup$ – reinierpost Apr 11 '17 at 19:45
  • $\begingroup$ That was from my homework, actually. As far as know to show that regular expression accepts strings, we have to show some sample strings that are in that regular expression. What instructor wants from us is to mention how we came to the final result of that regular expression. That's the thing I really didn't understand. $\endgroup$ – Nijat Mursali Apr 12 '17 at 17:23
1
$\begingroup$

You have to show two things:

  1. Every word in the language of your regular expression contains 101 as a substring.

  2. Every word containing 101 as a substring belongs to the language of your regular expression.

You can prove both of these using the definition of the language of a regular expression. It is a bit tiring but otherwise requires little creativity.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ However, it's not possible to show all words that contain that substring because it's infinitely many. I'm trying to find the method for finding. Thanks for your answer. $\endgroup$ – Nijat Mursali Apr 11 '17 at 6:43
  • $\begingroup$ You can use general properties of how regular expressions describe languages. For example, for any two regular expressions $X$ and $Y$, $L(XY) = L(X)L(Y)$. You can use this in your proof. $\endgroup$ – reinierpost Apr 11 '17 at 19:47
  • $\begingroup$ @reinierpost This is not a property. It's the definition of the language corresponding to a regular expression. $\endgroup$ – Yuval Filmus Apr 11 '17 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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