I'm designing a Turing machine that decides a language denoted by a regular expression. Let's say this expression is $a^*bbc^*$. Does this machine accept the string $bb$ since $a^*$ and $c^*$ can have zero instances or more?

  • $\begingroup$ Yes, $a^*bbc^*$ matches $bb$. $\endgroup$ – Yuval Filmus Oct 24 '14 at 6:25
  • 3
    $\begingroup$ The meaning of * is covered in your textbook and in any online reference such as wikipedia. You're expected to do at least basic research before asking here. $\endgroup$ – David Richerby Oct 24 '14 at 8:37

Yes, the word $bb$ in the language generated by the regular expression $a^*bbc^*$, because, as you say, $a^*$ and $c^*$ generate also the empty word. So if you are building a Turing machine that accepts this language, it should also accept the string $bb$.

| cite | improve this 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.