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,,,,,,, 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:
    0 1
    (0 0 0)
    (0 1 1)
    (1 0 1)
    (1 1 0)

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
Differentiate between Prepurchase and Purchase Consummation of consumer mercantile model. The prepurchase interaction for consumers comprises three activities: Product/ser

Determine about the Intranet server The success or usage of the Intranet server is measured by the number of operations it handles per Unit time. The selection of a good server

Write a program, using functions, that calculates the area and perimeter of a rectangle whose dimensions (Length & width) are given by a user.

Question 1: (a) What is the difference between IT (Information Technology) and ICT(Information Communication Technology) (b) Explain why information systems are so im

What format should my database be saved in to allow different versions of Microsoft Access to open the database? Ans) MS Access is not backwards compatible. To share tables amon

a. Explain Intermediate Representation? What are the desirable properties of Intermediate Representation? b. Explain Grammar of a language. Identify the dissimilar classes of gr

Vector-Memory Instructions : When vector operations with memory M are executed then these are vector-memory instructions. These instructions are denoted with the many function mapp

Traffic Capacity is given by? Traffic Capacity = Switching capacity × Theoretical maximum load.

Data, information and knowledge - Information System The nature of information can most easily be defined in the context of its relationship to data and knowledge. Bohn (1994)