Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
3  
This should be pretty straightforward, what have tried so far? –  Luke Mathieson Feb 6 '13 at 7:01
    
make it skip one letter and then check the letter is $B$. –  Ran G. Feb 6 '13 at 7:10
    
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? –  Merbs Feb 9 '13 at 6:46
add comment

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

share|improve this answer
1  
+1 for the effort of explaining the basics with an example, without the direct answer –  Paresh Feb 6 '13 at 15:26
1  
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. –  Raphael Feb 8 '13 at 8:17
1  
@Raphael, sounds fun; I'll work on a better answer on Sunday. –  Merbs Feb 9 '13 at 6:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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