# DFA that accepts strings with last character being repeated at least 1 time before

I'm trying to design a DFA in a 4 digit language, for example L(a,b,c,d) or L(1,2,3,4) that accepts strings with the last character being already repeated before.

Everyway im trying, i get so many transitions im literally lost in them...

So, for example, abbdb is accepted (because b is showed again at least 1 time) but abc is rejected since c (last char) never shows up more than 1 time.

I managed to make it work for a language with 2 DIGIT:
For example: Which accepts for example aa or ababa but can't do for 4 DIGIT language.

• Try first when the alphabet is smaller. – Yuval Filmus Dec 2 '18 at 18:24
• @YuvalFilmus yes i already have tried to do that too and i can't achieve anything. u can look at the edited post an example with 2 digits. – Konstantinos Dec 2 '18 at 18:37
• You can also try solving it for a general alphabet - might be easier than a special case. – Yuval Filmus Dec 2 '18 at 18:39
• i managed to achieve this for 2 digit language.. but still i want 4 digit – Konstantinos Dec 2 '18 at 19:45

• States ($$Q$$): the states of this machine are five-tuples $$(\alpha, \beta, \gamma, \delta, \sigma)$$: alpha, beta, gamma, and delta are in $$\{0,1\}$$ and record whether or not the corresponding symbol has been seen before, while sigma is in $$\Sigma \cup \textrm{Nothing}$$ and indicates the last symbol read.
• Alphabet ($$\Sigma$$): the alphabet, as you specified, is $$\{a,b,c,d\}$$.
• Start ($$q_0$$): the starting state is $$(0,0,0,0,\textrm{Nothing})$$. In other words, we've seen no symbols yet, and the previous symbol read was nothing.
• Final States ($$F$$): a state is final if the last symbol read was seen before. For example, the state $$(1,\#,\#,\#,a)$$ is final, regardless of what those $$\#$$s in the middle are.
• Transition function ($$\delta$$): this is the trickiest part. If we're in a state $$(\alpha, \beta, \gamma, \delta, \sigma)$$ and see the symbol $$s$$, we want to go to the state where $$s$$ has been seen, and where $$s$$ is the last symbol read. If we see $$a$$, for example, we go to state $$(1, \beta, \gamma, \delta, a)$$: we mark that $$a$$ has been seen, don't change $$\beta$$, $$\gamma$$, or $$\delta$$, and record $$a$$ as the most recently read symbol.
• @Konstantinos In my DFA it takes $(n+1)2^n$ states; this number can be reduced somewhat by merging some of the final states, but it remains exponential in $n$. – Draconis Dec 3 '18 at 5:17