Finite automaton for the language of words whose second letter is b

Problem Detail: 

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.

Asked By : Myles Canady

Answered By : Merbs

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$).

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9537