I am trying to solve a practice problem from my textbook which is to draw an FA from this language: L(ab* a*) U L((ab)*ba)

I need help to draw the second part L((ab)*ba). I know the shortest string is ba, then it is abba, ababba, abababba, etc.

I started off with this to show the shortest string: FA

However, now I need to add the (ab)* part in the front of this which I am unsure how to approach this.

Any help would be great, and sorry if this seems obvious to some of you... I just don't see it right now!

EDIT: If it were (a*)ba I know how I would approach it, but the (ab)* is confusing me.

  • 1
    $\begingroup$ en.wikipedia.org/wiki/Thompson%27s_construction $\endgroup$ – D.W. May 22 '16 at 0:25
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jun 4 '16 at 15:38
  • 1
    $\begingroup$ There are standard constructions for this, which can be found in any textbook or set of lecture notes on the subject. I suggest you look at the construction and ask again if you have a more specific question. $\endgroup$ – David Richerby Jun 5 '16 at 18:40

$L = (ab)^*ba$

Divide $L$ into two part for easy construct the FA as

  1. $(ab)^*$
  2. $ba$

Draw 1 and 2, end all undesired path to a dead state.

enter image description here

| cite | improve this answer | |
  • $\begingroup$ Almost, but you need to reverse the direction of the two leftmost arrows. $\endgroup$ – Rick Decker Jun 5 '16 at 16:21
  • $\begingroup$ Sorry, mistake while drawing. [FA diagram updated with correct answer] $\endgroup$ – Alwyn Mathew Jun 5 '16 at 20:06

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.