5
$\begingroup$

This is a homework question, so I am only looking for hints.

I got a question in an assignment which states :

Design a DFA that accepts strings having 1 as the 4th character from the end, on the alphabet {0,1}

I have been at this for a few hours now, and I think that designing such a DFA is not possible. However, I am not sure how to move forward in this direction to write up a somewhat formal proof.

So, what should I try to do to prove or disprove my hypothesis?

$\endgroup$
  • 5
    $\begingroup$ Hint: if you have a hard time coming up with a DFA, try building an NFA. Then you can apply a generic determinization algorithm and find a DFA if you like. $\endgroup$ – Gilles 'SO- stop being evil' Aug 29 '13 at 6:50
  • 1
    $\begingroup$ Hint: you only need to remember the last 4 characters, hence you can label the states with a word in $\{0,1\}^4$. $\endgroup$ – Tpecatte Aug 29 '13 at 8:00
6
$\begingroup$

Hint: Your language can be described by the regular expression $\{0,1\}^*1\{0,1\}^3$.

Another hint: Your DFA can remember the last $4$ characters (and maintain that information). You will also need states to handle the case in which less than $4$ characters have been seen so far.

$\endgroup$
  • $\begingroup$ What exactly does "remember" mean in a DFA? $\endgroup$ – asheeshr Aug 29 '13 at 8:14
  • $\begingroup$ @AsheeshR, the current state represent all the information remembered. Thus knowing how many different information is remembered gives you a lower bound on the number of states. $\endgroup$ – AProgrammer Aug 29 '13 at 8:30
  • $\begingroup$ Out of context, but how can a turing machine recognize that language with less than $n+k+2$ steps? $\endgroup$ – TheNotMe Dec 28 '13 at 11:41
  • $\begingroup$ The Turing machine can simulate the DFA. It should terminate within $n$ steps or so. $\endgroup$ – Yuval Filmus Dec 28 '13 at 21:06
5
$\begingroup$

Another hint: Try first to solve the same problem for the first character from the end, then the second character from the end. It is easier and you may get some intuition from there.

$\endgroup$
5
$\begingroup$

I first made the NFA and then converted it to a DFA. I ended up with a total of 16 states. I thought that I had probably done something wrong as I ended up with a very large number of states, so I then followed what J.-E. Pin suggested.

I first created a NFA that checks for the last character satisfying a condition and converted it to a DFA. I then repeated this for the second last and third last characters.

What I noticed was that, the number of states in the resulting DFA was $2^n$, where $n$ is the number of states in the equivalent NFA (excluding the initial state) or the position of the character to be checked from the end.

So, if I understand this correctly, the DFA is checking all the possible strings on the input alphabet for the last $n$ characters.


So, to answer my own questions :

I have been at this for a few hours now, and I think that designing such a DFA is not possible.

It is.

So, what should I try to do to prove or disprove my hypothesis?

Make a NFA and convert it to a DFA.

$\endgroup$
  • $\begingroup$ You don't have to convert your NFA to a DFA if all you want to know is that a DFA exists. $\endgroup$ – Yuval Filmus Aug 29 '13 at 18:29
  • $\begingroup$ 16 states is the correct answer. And your $2^n$ guess is also correct, but this is more difficult to prove in general. $\endgroup$ – J.-E. Pin Aug 30 '13 at 0:11
  • $\begingroup$ @yuval-filmus The original question was "design a DFA..." $\endgroup$ – J.-E. Pin Aug 30 '13 at 0:12
  • $\begingroup$ The book Automata, Computability and Complexity from Elaine Rich, Theorem 5.2 defines: "For every DSFM for a language L there is an NDFSM for L" and theorem 5.2 "if there is an NDFSM for L, there is a DSFM for L". Rich also provides an algorithm ndsfmtodsfm(M: ndsfm) here: slideplayer.com/slide/3257864 $\endgroup$ – Juan Zamora Jul 5 '17 at 1:39
3
$\begingroup$

As mentioned before, you don't need a NFA, you can quite easily design a DFA as follows. The DFA is the tuple $(Q,I,F,\delta)$ with :

  • $Q = \{0,1,*\}^4$ : a state "remember" the 4 last character read, the $*$ is for cases with less than 4 characters read.
  • $I = (*,*,*,*)$
  • $F = \{ (a,b,c,d) : a = 1 \}$
  • $\delta((a,b,c,d), e) = (b,c,d,e)$
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.