Finite state automaton, Computer Engineering

Once a finite state automaton (FSA) is designed, its transition diagram can be translated in a straightforward manner into program code. However, this translation process is considerably tedious if the FSA is large and troublesome if the design is modified. The reason is that the transition information and mechanism are combined in the translation.

To do it differently, we can design a general data structure such as a table or a list to hold the transition information, and to implement in program code only a general transition mechanism. Using this approach, the resulted program is not only smaller, but it can also be modified easily to simulate a different FSA by just changing the transition information and the general data structure holds. We shall refer to such a program as a universal finite state automaton.

Your job for this assignment is to implement such a universal finite state automaton. To convince you that it is very easy to do so, I have suggested an algorithm below; however, you are free to modify it. Note that your program has to be designed to handle the FSA where the input transition function is partial, which means there is a default dead-end, or trap state.

1173_Finite State Automaton.png

You must represent each FSA in the input file with the following format, and put all input machines in one file:

(1) The number of states, say N.
For ease of implementation, number states from 0 to N-1, with 0 representing the initial state, and N the dead-end state.

(2) The set of final states.
You need a boolean array FINAL [0..N-1].

(3) The alphabet.
Symbols in the alphabet should be numbered internally so that the value returned by the function NextSymbol is an integer.

(4) A sequence of transitions of the form (p,a,q).
The triple (p,a,q) means that in state p, looking at input symbol a, the FSA will change its state to q. For this project, store this information in a table, say next_state, so that the value returned by the function NextState is next_state [state, symbol].

Test your program with the following 5 finite state automata using the given test strings.

(1) A FSA which recognizes the set of strings over {0,1} that do not have three consecutive 1's.  Strings: ?, 1, 000, 111000, 000111, 011010, 1010101110, 10101, 00110110110, 111

(2) A FSA which recognizes email addresses. A valid email address is defined as follows: userName@serverName.domainName, where the user name consists of at least one symbol with any combination of letters, digits, hyphens, underscores, or periods. The server name is any string of at least one symbol with any combination of letters, digits, hyphens, and underscores. The domain name must have 2 to 4 letters. Strings: a.b.c@d.w3c, jsmith, jsmith@olympus, jsmith@olympus.gov, _jsmith-example.olympus@states.us, jsmith.edu, john@mail.office, ComputerScienceDepartment@csupomona.edu, jsmith@LA.cnn.com, SMITH@bookStore.Peru

(3) A FSA for a vending machine that provides only candy bars, each costs 25 cents. The initial state indicates that nothing has happened yet. If you insert a nickel, the machine will change to a state indicating that the total amount received so far is 5 cents. If you then insert another nickel, it will change to a state indicating that the total amount received is now 10 cents. If you then press a button to select a candy bar, the machine will ignore this input, since the proper amount has not yet been paid. When the total amount reaches at least 25 cents, however, the machine will now respond if you select a candy bar. It will deliver the candy bar and return to its starting state, which is also an accepting state. ∑ = {n, d, q, s}, where n stands for nickel, d for dime, q for quarter, and s for the select button. Strings: s, sds, nnns, ddd, ddds, qqsqs, sdsnsnsns, sdqsd, ndnqdqndqn, ssnqdss

(4) A FSA which recognizes the set of strings over {a,b} where the number of a's is even and the number of b's has remainder one when divided by three. Strings: ?, aa, baa, aba, aabb, babababab, aabbaabb, aaababbaa, abbbbaa, bbbbbbb

(5) A FSA which recognizes the set of all signed or unsigned decimal numbers without superfluous leading or trailing zeros. For instance, 0.0, -0.5, +120.01, and 123000.0 are in the language, but 0.00, 00.5, and 0123.4 are not. Each decimal number has the form of A.B, where A and B are strings of digits and they cannot be empty at the same time. Strings: +1.23, -.123, 123., -0.0, 01234.5, -789, ., 56.30, +120.0001, 123000.0
Sample input of a FSA:
    2
    1
    0 1
    (0 0 0)
    (0 1 1)
    (1 0 1)
    (1 1 0)
    1000
    10001
    ........

Corresponding output:
Finite State Automaton #1.
(1) number of states: 2
(2) final states: 1
(3) alphabet: 0, 1
(4) transitions:
0   0   0
0   1   1
1   0   1
1   1   0
(5) strings:
1000        Accept
10001        Reject
        ........

Submit on Bb and turn in the printout of (1) program code with proper comments including your name and clear instructions to compile, link, and run your program, (2) input file containing the description of the above five machines and corresponding test strings, and (3) output of executions.

Posted Date: 2/27/2013 6:02:12 AM | Location : United States







Related Discussions:- Finite state automaton, Assignment Help, Ask Question on Finite state automaton, Get Answer, Expert's Help, Finite state automaton Discussions

Write discussion on Finite state automaton
Your posts are moderated
Related Questions
Q. Major characteristics of a computer family? Let us summarise the major characteristics of a computer family. These are as below: Figure: Characteristics of computer


Make a nested struct to store a person's name, address, and phone numbers.  The struct should have 3 fields for the name, address, and phone. The address fields and phone fields wi

Q. How can one decide this decimal position? Decimal position can be signified by a position between flip-flops (storage cells in computer). However how can one decide this dec

Whenever a developer is signing into the code project you will have three options they are disable the macro, enable the macro and explicitly trusting the publisher. You can trust

Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two points can b

Differentiate Traditional Commerce verses Electronics Commerce. Identity: Into traditional commerce customers can simply authenticate the identity of a merchant simply throug

how we get a perfect tutorial for face recognition using java

Develop a regular expression for Real number with optional fraction and Identifier. (i) A regular expression for real number with optional fraction is [+ | -] (d) +. (d)* (i

And-Elimination rule: In generally English says that "if you know that lots of things are all true, so you know like any one of them is also true". Because you can specify a c