1
$\begingroup$

I'm having some trouble writing a DFA for the language $$\{w =b_1\dots b_k \in\{0, 1\}^* \mid b \ge 2 \text{ and } b_2=b_k\}\,.$$

What I thought for this is writing a DFA where there are 4 states, that accepts at the states (00) and (11), where the 1st element in the state is the 2nd element in the string, and the 2nd element in the DFA is the last element in the string. After trying to draw out examples this clearly doesn't work. I'm quite lost, any advice?

$\endgroup$
4
$\begingroup$

You are on the right track.

When constructing a DFA, you have to consider what information you need to store to decide in the end whether the string is accepted or not. The information you need is indeed: the second symbol of the string and the symbol which was read last. So you need four states to store all combinations of these two flags, and the accepting states are the ones where the second symbol and the last symbol are equal. The only thing you still need to do, is glue these states together.

First, there is a third kind of information: the length of the string. If you have read less than two symbols, you are not in one of four states mentioned earlier. So there are six states:

A: no symbols have been read (this is the initial state)
B: one symbol has been read
C: at least two symbols have been read, the second symbol is a 0 and the last a 0 
   (this is an accepting state) 
D: at least two symbols have been read, the second symbol is a 1 and the last a 0 
E: at least two symbols have been read, the second symbol is a 0 and the last a 1 
F: at least two symbols have been read, the second symbol is a 1 and the last a 1
   (this is a in accepting state) 

To finish the automaton, you have to consider what happens to the state if you read in a 0 or a 1. This will then give you the transition function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy