0
$\begingroup$

I am studying for a test in computer science, and am encountering difficulties with regular expression. Here is example of a question I don't understand.

I managed to solve the following question:

Give a regular expression for the language of all words over $\{a,b\}$ which contains one of $aa,bb$ as a subword.

My solution: $$(a ∪ b)^*(aa ∪ bb)^*(a ∪ b)^*.$$

I am having trouble with the following question:

Give a regular expression for the language of all words over $\{0,1\}$ which contains $010$ as a subword.

$\endgroup$
  • $\begingroup$ L1 does not look right. All the words in L1 are such that "aa" or "bb" occurs as a substring, but not all words that satisfy the above property are in L1. $\endgroup$ – Steven Nov 8 '19 at 22:00
  • $\begingroup$ cs.stackexchange.com/q/1331/755 $\endgroup$ – D.W. Nov 8 '19 at 23:48
  • $\begingroup$ What do you mean by "subword"? $\endgroup$ – Yuval Filmus Nov 10 '19 at 11:27
1
$\begingroup$

In the first one, L1 = (a+b)*(aa+bb)(a+b)* not (a+b)(aa+bb)(a+b)* because in the second one, it is possible only to have one character of a or b and then we have to find the occurrence we need. Your L1 denies any word that does start with (aa+bb). It also forces all the words to start with a or b.

By the way, I use + for | and ∪.

So for the second one, it is in the same manner:

L1 = (0+1)*(010)(0+1)*

010 might occurs in the beginning, the middle or the end of the word.

$\endgroup$

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.