Alphabet is {a,b}, the third element from the start must be "b" (e.g: aab..., abb...) and the third-last element must also be "b" (e.g: ...baa, ...bbb). I can do them separately but at the same time I don't know where to start. Help please.


Hint. If $A$ is the alphabet, a regular expression for your language is $AAbA^*bAA \cup AAbAA \cup AbbA \cup bAb$.

| cite | improve this answer | |
  • $\begingroup$ @G.Bach I wrote both my answer and in my answer to your comment in a hurry, but now that I have more time, I would like to thank you for pointing out my mistake in this elegant way. $\endgroup$ – J.-E. Pin May 27 '16 at 16:06
  • $\begingroup$ Thank you! That's right, since the automaton is nondeterministic, I can just concatenate the three of them (bxb, xbbx and xxbxx), it works now. $\endgroup$ – Marx Guimarães May 28 '16 at 17:25

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.