0

How would I go about designing a deterministic finite automata to recognize the language

L = {λ, ab, abab, ababab, . . . }

consisting of strings that start with ‘a’, end with ‘b’, and alternate in between? Any help or push in the right direction is appreciated.

Amanda
  • 49
  • I recommend CS.stackexchange.com for CS questions. This is a fairly remedial regex / FSA question, do you know anything at all about the subject? http://en.wikipedia.org/wiki/Kleene_star – DanielV Oct 14 '14 at 10:44

2 Answers2

1

You asked “How would I go about designing…”. You should imagine that someone has given you a very long string of symbols and asked you to verify this property. The string is so long—perhaps thousands or millions of symbols—so that you cannot simply see it at a glance, as you can with short strings like ababab. Then ask yourself what you could do to decide if the string has the required property.

Usually your idea will look something like this: “First I'll do (something), and then if I see an a I will do (something else), but if it's a b I will look at the next symbol, and then if it's an a I will do (some other thing).” The decision points where you say “I look at the next symbol and if it's a I'll do (this) but if it's b I'll do (that)” are exactly the states of a finite automaton:

enter image description here

Here's an example which isn't the one from your question: Say I would like to check to see if a string contains two consecutive as. How can I do this? I should scan the string starting with the first character. If I see an a, I will look to see if the next character is also a; if it is, the string has two consecutive as, so I will accept. If I see something else while looking for an a, I will continue scanning the string. And once I have seen two as, nothing else I see in the string will cause me to reject it:

enter image description here

MJD
  • 65,394
  • 39
  • 298
  • 580
0

$q_0$- initial state

$q_1$-starts with 'a'

$q_2$-starts with 'ab', accepting state

$q_3$-starts with 'b'/'aa'

Now, note that if a word starts with 'ab' then it's legal iff the remainder of the word is legal, and once we found that a word is ruined somewhere then there is no redemption for this words. Also, note that you can merge $q_0$, $q_2$

Now use those to obtain the complete automata.

Another and more advanced option is to build a regular expression that defines the language and use the algorithm that builds an dfa out of reg-exp

Snufsan
  • 2,125