I am new to theoretical cs and am working through it slowly. I have completed a simple question and was wondering if my answer is correct or not. Thank you kindly for any feedback.

The question is: Given the alphabet $\{a, b\}$ Construct a regular expression that defines the language $M$ containing all words beginning with exactly one $a$ or exactly one $b$. Words in $M$ are at least of length $1$. Words in $M$ can begin and end with the same letter substring or begin and end with different letter substrings.

My answer is: $( a( b( a + b)^*)^*) + (b ( a (a + b)^*)^*)$

Thank you.

  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Aug 21 '20 at 1:06
  • $\begingroup$ cs.stackexchange.com/q/11315/755 $\endgroup$ – D.W. Aug 21 '20 at 1:06
  • $\begingroup$ (working through [CS] slowly Exactly what Donald Knuth set out to do.) $\endgroup$ – greybeard Aug 21 '20 at 4:34
  • $\begingroup$ (There have been discussions What to do when the answer is already part of the question.) $\endgroup$ – greybeard Aug 21 '20 at 4:39
  • $\begingroup$ Yeah thanks I came here as last resort namely because I don't really have teachers or class mates as such. I just do the work and submit it. Thanks anyway I'll keep at it. $\endgroup$ – Matthew Lategan Aug 21 '20 at 8:57

Setting $A = a + b$, you could write $M$ as $A + abA^* + baA^*$ or as $A + (ab +ba)A^*$. This avoids the nested star of your answer.


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.