# 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

## 1 Answer

I would write out a description of this machine rather than drawing it.

• 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.
• is this a description for general fsm or for a DFA because i struggle to convert this to a DFA in my mind. – Konstantinos Dec 2 '18 at 20:05
• @Konstantinos This is a description for a DFA that accepts your language. I wouldn't recommend drawing it out by hand because the number of states grows exponentially with the size of your alphabet, as you've probably discovered. I don't think a DFA can recognize this language in less than exponential space. – Draconis Dec 2 '18 at 20:15
• Is there a way to determine my problem how many states it will need? @Draconis – Konstantinos Dec 2 '18 at 20:28
• @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
• Okay thank you actually that helps more than you think. The answer now is complete @Draconis – Konstantinos Dec 3 '18 at 14:01