6
$\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?

Improve this question
$\endgroup$
2
  • 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'
    Commented Aug 29, 2013 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
    Commented Aug 29, 2013 at 8:00

4 Answers 4

Reset to default
7
$\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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What exactly does "remember" mean in a DFA? $\endgroup$
    – asheeshr
    Commented Aug 29, 2013 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
    Commented Aug 29, 2013 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
    Commented Dec 28, 2013 at 11:41
  • 1
    $\begingroup$ The Turing machine can simulate the DFA. It should terminate within $n$ steps or so. $\endgroup$
    – Yuval Filmus
    Commented Dec 28, 2013 at 21:06
6
$\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.

Improve this answer
$\endgroup$
6
$\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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Aug 29, 2013 at 18:29
  • 1
    $\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
    Commented Aug 30, 2013 at 0:11
  • $\begingroup$ @yuval-filmus The original question was "design a DFA..." $\endgroup$
    – J.-E. Pin
    Commented Aug 30, 2013 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
    Commented Jul 5, 2017 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)$
Improve this answer
$\endgroup$

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