I was asked this question and could not come to the correct answer:

Let $L$ be the language of all words over $\{a,b\}$ where the first letter is identical to the letter that is next to last. (Pay attention – every word with length 2 is in the language.)

Sketch a nondeterministic automaton that accepts this language.

Any help would be appreciated.


Hint: you want to make states $x/y/z$ which mean that $x$ is the first symbol of the word, $y$ is the second to last symbol seen, and $z$ is the last symbol seen.

I will show you half of the final machine, the one for words starting with $a$. Note that "!a" here means any symbol not equal to a, or no symbol at all.


  • $\begingroup$ Since the automaton for this question is allowed to be undeterministic, perhaps an intuitive appraoch would be to make a straightforward automaton for $a\Sigma^* a \Sigma$ ? $\endgroup$ Dec 17 '18 at 23:50
  • $\begingroup$ @HendrikJan Not quite, that would fail $aa$ or $ab$. But I'm sure you can get something more compact using non-determinism, I just usually prefer DFAs if I can see a solution with them as I find them easier to reason about. $\endgroup$
    – orlp
    Dec 18 '18 at 6:13
  • $\begingroup$ Completely agree! For many problems determinism is the approach that leads to a solution that makes it clear what the automaton is "remembering", and proofs will be easier. However, when asked for an automaton for "strings with subword $aabab$" it is good to have the nondeterministic variant available, unless you want to implement KnuthMorrisPrat. It is not about compactness in this case (it will only save a single state.) $\endgroup$ Dec 18 '18 at 11:04
  • $\begingroup$ @HendrikJan That one wasn't too hard :P i.imgur.com/dr6HUX1.png $\endgroup$
    – orlp
    Dec 18 '18 at 12:58

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.