# Creating a DFA where the string should start with b and the length is 3

I'm new to automata and in my first exercise I have to construct a DFA that starts with 'b' and length=3. Two symbols (a,b).

To my understanding, there are 4 possibilities {baa,bab,bba,bbb}

I have attached a picture showing where I got stuck. Any help is appreciated, also please tell me if the part I've already done has errors.

https://postimg.cc/7JPNyRVq

New contributor
Laz is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Why are you stuck? You are on the right track. Add to more states after $q_1$, namely $q_3$ and $q_4$, and draw $a,b$ transtions in sequence. Make $q_4$ the final state, Commented Jul 31 at 8:09
• So from q1, one transition would be to q3 with 'a' and self loof of a,b on q3; and another to q4 with 'b' with a self loof of a,b on q4?
– Laz
Commented Jul 31 at 15:40
• cs.stackexchange.com/q/1331/755
– D.W.
Commented Jul 31 at 17:30

Hint 1: Every state in a DFA "remembers something", for example, in your attempt, the state $$q_1$$ remembers two things: (1) that we've just read $$b$$, and (2) that we've read a word of length 1 so far. Now if you want to accept all words whose length is exactly 3 and start with $$b$$, then:

1- What would you do from the state $$q_1$$ upon reading a letter?

2- What would you do from a state, to be added, that remembers that we have read a word that starts with $$b$$ and whose length is 3?

Hint 2 (more general): All words over $$\Sigma = \{a, b \}$$ of length $$\leq k$$ for some constant $$k$$, can be presented as a finite full binary tree whose depth is at most $$k$$, where the root corresponds to the empty word, and if a word node $$n$$ corresponds to a word $$w$$, then its left child and right child correspond to the words $$wa$$ and $$wb$$, respectively. Think how you can define a DFA for your language on top of that tree. In fact, this hint can be used to show that every finite language is regular.

• So what I have now is basically that I'm starting with b and it can be either a or b after the initial b?
– Laz
Commented Jul 31 at 15:42
• @Laz Exactly, after the initial $b$, you don't care which letter is read, yet you care about the number of letters left to be read. Commented Jul 31 at 15:47
• Am I correct now or is this totally wrong? ![IMG-20240731-212817.jpg](postimg.cc/Ln6rkq9n)
– Laz
Commented Jul 31 at 15:59
• Which states are accepting? Your DFA treats words of length 3, 4, 5, ... all the same. You need to accept only those of length 3. Try running your answer on different inputs and see what happens. Commented Jul 31 at 16:02

How about creating an NFA with Thompson's construction, and getting the equivalent DFA with powerset construction? Here's how it goes:

First, a regular expression describing a language consisting strings with length of 3 and starting with $$b$$ would be $$b(a|b)(a|b)$$. Use Thompson's construction to get

In this case, the automaton is already deterministic, so therefore, powerset construction is not needed, and you got the automaton you want.

• Applying two complex algorithms for a simple example -- this is too much if the goal is to give the asker a hint and help understand the basics of how to design an automaton, rather than putting the automaton on the table. Commented Jul 31 at 15:59
• I'm not sure as to whether I can do it this way. We've been taught basic DFA, and NFA, and the question included "construct the DFA".
– Laz
Commented Jul 31 at 16:02