How can I build a finite automaton that accepts only the language of all words in which b is the second letter?

This is my solution so far but I'm not sure if it's correct.

  • 3
    $\begingroup$ This should be pretty straightforward, what have tried so far? $\endgroup$ Feb 6, 2013 at 7:01
  • $\begingroup$ make it skip one letter and then check the letter is $B$. $\endgroup$
    – Ran G.
    Feb 6, 2013 at 7:10
  • $\begingroup$ Everyone has to ask their first question; your solution is not quite correct, though I'm slightly confused. What happens to the string 'ba' in your FA? $\endgroup$
    – Merbs
    Feb 9, 2013 at 6:46

1 Answer 1


A finite automaton (FA) is simply a machine with limited memory. The FA reads in an input string and does one of two things: accept or reject. In many ways, FAs are realistic abstractions of computers and brains and good depictions of simple machines like vending machines and elevators. You can read more about finite-state machines on Wikipedia, though the page on deterministic finite automaton may be more useful for solving your problem. If you own it, you should also read Sipser's Introduction to the Theory of Computation; it's relatively approachable.

I don't want to simply solve your problem, so let's look instead at a related problem:

The language of all words with at least one $a$
Informally, we read each element from the input string and accept if we see an $a$.

Semi-formally, we're going to have two states: (1) have not yet read an $a$ (2) have read an $a$. Then we transition from state (1) to state (2) when we read an $a$. If we read anything other than an $a$, we stay put. If the input string ends and we're left in state (1), then we reject (the word is not in the language because it doesn't contain an $a$); if we're left in state (2), then we accept (it does contain an $a$).

finite automata that recognizes the language at least one a

Formally, we need to define a 5-tuple (i.e. 5 different elements)

  1. A finite set of states $(Q)$. We can name them whatever we want, so if we want to be boring, we can simply call them $q_0$ and $q_1$. If we want to be relevant to just this problem, we can call them $q_\bar{a}$ (the state for which we have not read an $a$) and $q_a$ (the state for which we have). On our picture, the states are the circles, and we label them with their names.
  2. A finite set of input symbols $(\Sigma)$, which we call the alphabet. Here, let's say that the input string has just $a$, $b$ and $c$, so $\Sigma=\{a,b,c\}$.
  3. A transition function $(\delta)$, which takes every element in the set of states $Q$ and dictates what state is transitioned into for each element in the alphabet $\Sigma$ (in notation, $Q\times \Sigma \rightarrow Q$). That is, we make a state transition table, with the states in the first column and the alphabet in the first row, and then fill in what state is transitioned to for each combination of state and input symbol. $$\begin{vmatrix} & a & b & c \\ q_\bar{a} & q_a & q_\bar{a} & q_\bar{a} \\ q_a & q_a & q_a & q_a \\ \end{vmatrix}$$ You can see that the arrows and letters on the picture represent this transition function.
  4. A start state $(q_0\in Q)$. This is where our machine starts its reading of the input string. If the string is empty, it's also where it ends. For this problem, the start state is $q_\bar{a}$. On the picture, we depict this via an arrow coming from no other state.

  5. A set of accept states $(F\subset Q)$. Here, our only accept state is $q_a$, so the set of states is $F=\{q_a\}$. We represent this via a concentric circle on each accepting state.

Try solving your problem again, and when you do solve it, post it as a solution

  • 2
    $\begingroup$ +1 for the effort of explaining the basics with an example, without the direct answer $\endgroup$
    – Paresh
    Feb 6, 2013 at 15:26
  • 2
    $\begingroup$ Nice. One suggestion. This question will be barely visible because of its downvotes, so why don't you create a reference questions (maybe "How to come up with a finite automaton for a given language?") and (re)post your answer there? Besides being more visible, more clearly searchable and linkable that would have the advantages that other answers with the same goal could be added. $\endgroup$
    – Raphael
    Feb 8, 2013 at 8:17
  • 2
    $\begingroup$ @Raphael, sounds fun; I'll work on a better answer on Sunday. $\endgroup$
    – Merbs
    Feb 9, 2013 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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