# Nondeterministic automaton accepting only words whose first letter is identical to their next to last letter

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. • 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$ ? Dec 17 '18 at 23:50
• @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.
– orlp
Dec 18 '18 at 6:13
• 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.) Dec 18 '18 at 11:04
• @HendrikJan That one wasn't too hard :P i.imgur.com/dr6HUX1.png
– orlp
Dec 18 '18 at 12:58