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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Try first when the alphabet is smaller. $\endgroup$
    – Yuval Filmus
    Dec 2, 2018 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, 2018 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, 2018 at 18:39
  • $\begingroup$ i managed to achieve this for 2 digit language.. but still i want 4 digit $\endgroup$
    – Konstantinos
    Dec 2, 2018 at 19:45

1 Answer 1

Reset to default
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.
Improve this answer
$\endgroup$
5
  • $\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, 2018 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, 2018 at 20:15
  • $\begingroup$ Is there a way to determine my problem how many states it will need? @Draconis $\endgroup$
    – Konstantinos
    Dec 2, 2018 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, 2018 at 5:17
  • $\begingroup$ Okay thank you actually that helps more than you think. The answer now is complete @Draconis $\endgroup$
    – Konstantinos
    Dec 3, 2018 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.