Create your own FSA

Have a go..

If you would like to experiment with Finite State Automata you can download Educational Software "Exorciser". Exorciser has facilities for doing advanced exercises in formal languages; but here we'll use just the simplest ones.

Exorciser can be downloaded here.

When you run it, select "Constructing Finite Automata" (the first menu item); click the "Beginners" link when you want a new exercise. The challenge in each FSA exercise is the part after the | in the braces (i.e. curly brackets). For example, in the diagram below you are being asked to draw an FSA that accepts an input string w if "w has length at least 3". You should draw and test your answer, although initially you may find it helpful to just click on "Solve exercise" to get a solution, and then follow strings around the solution to see how it works.

To draw an FSA in the Exorciser system, right-click anywhere on the empty space and you'll get a menu of options for adding and deleting states, choosing the alphabet, and so on. To make a transition, drag from the outside circle of one state to another (or out and back to the state for a loop). You can right-click on states and transitions to change them. The notation "a|b" means that a transition will be taken on "a" or "b" (it's equivalent to two parallel transitions).

If your FSA doesn't solve their challenge, you'll get a hint in the form of a string that your FSA deals with incorrectly, so you can gradually fix it until it works. If you're stuck, click "Solve exercise". You can also track input as you type it: right-click to choose that option. See the SwissEduc website for more instructions.

Examples to try

Using Exorciser or JFLAP (or just draw it by hand if you prefer), construct an FSA that takes inputs made of the letters "a" and "b", and accepts the input if it meets one of the following requirements. You should build a separate FSA for each of these challenges.

strings that start with the letter "a" (e.g. "aa", "abaaa", and "abbbb").
strings that end with the letter "a" (e.g. "aa", "abaaa", and "bbbba").
strings that have an even number of the letter "a" (e.g. "aa", "abaaa", "bbbb"; and don’t forget the empty string ϵ).
strings that have an odd number of the letter "a" (e.g. "a", "baaa", "bbbab", but not ϵ).
strings where the number of "a"s in the input is a multiple of three (e.g. "aabaaaa", "bababab").
strings where every time an "a" appears in the input, it is followed by a "b" (e.g. "abb", "bbababbbabab", "bab").
strings that end with "ab"
strings that start with "ab" and end with "ba", and only have "b" in the middle (e.g. "abba", "abbbbba", but not "aba")

For the FSAs that you construct, check that they accept valid input, but also make sure they reject invalid input.

Hint

Here are some more sequences of characters that you can construct FSAs to detect. The input alphabet is more than just "a" and "b", but you don't need to put in a transition for every possible character in every state, because an FSA can automatically reject an input if it uses a character that you haven't given a transition for. Try doing two or three of these:

a valid three-letter month name (Jan, Feb, Mar, etc.)
a valid month number (1, 2, ... 12)
a valid weekday name (Monday, Tuesday, ...)

Hint

A classic example of an FSA is an old-school vending machine that only takes a few kinds of coins. Suppose you have a machine that only takes 5 and 10 cent pieces, and you need to insert 30 cents to get it to work. The alphabet of the machine is the 5 and 10 cent coin, which we call F and T for short. For example, TTT would be putting in 3 ten cent coins, which would be accepted. TFFT would also be accepted, but TFFF wouldn't. Can you design an FSA that accepts the input when 30 cents or more is put into the machine? You can make up your own version for different denominations of coins and required total.

Hint

If you've worked with binary numbers, see if you can figure out what this FSA does. Try each binary number as input: 0, 1, 10, 11, 100, 101, 110, etc.

Can you work out what it means if the FSA finishes in state q1? State q2?

Page updated

Google Sites

Report abuse