1
$\begingroup$

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:
enter image description here Which accepts for example aa or ababa but can't do for 4 DIGIT language.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Try first when the alphabet is smaller. $\endgroup$ – Yuval Filmus Dec 2 '18 at 18:24
  • $\begingroup$ @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. $\endgroup$ – Konstantinos Dec 2 '18 at 18:37
  • $\begingroup$ You can also try solving it for a general alphabet - might be easier than a special case. $\endgroup$ – Yuval Filmus Dec 2 '18 at 18:39
  • $\begingroup$ i managed to achieve this for 2 digit language.. but still i want 4 digit $\endgroup$ – Konstantinos Dec 2 '18 at 19:45
2
$\begingroup$

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.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ is this a description for general fsm or for a DFA because i struggle to convert this to a DFA in my mind. $\endgroup$ – Konstantinos Dec 2 '18 at 20:05
  • $\begingroup$ @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. $\endgroup$ – Draconis Dec 2 '18 at 20:15
  • $\begingroup$ Is there a way to determine my problem how many states it will need? @Draconis $\endgroup$ – Konstantinos Dec 2 '18 at 20:28
  • $\begingroup$ @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$. $\endgroup$ – Draconis Dec 3 '18 at 5:17
  • $\begingroup$ Okay thank you actually that helps more than you think. The answer now is complete @Draconis $\endgroup$ – Konstantinos Dec 3 '18 at 14:01

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.