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

How can the maximum field width for a data item be specified within a scanf function? When the program is executed, three integer quantities will be entered from the standard i

Question: a) Write a small program using floating-point operations in Reverse Polish Notation to evaluate the following: Volume of Sphere = (4/3)πr 3 Consider that the u

How does the Xml Serializer work?  What ACL permissions does a process using it require?   Xml Serializer needs write permission to the system's TEMP directory.

Q. Fundamental types of flash memory? Code Storage Flash which is made by Intel, AMD, Atmel. It stores programming algorithms and it is largely found in cell phones. Data

Q. Illustrate the Cache Memory Operation? It comprises a copy of a part of main memory contents. When a program is running and CPU tries to read a word of memory (instruction o

Q. What is multiplexer? Explain 4 X 1 Multiplexer.    Q. Explain the working of a Binary Half-Adder. Construct a Full-Adder from Half- Adder. Also draw the circuit diagram of full

Give LOAD-STORE optimization based on expression trees for the expression (A+B)/(C-D). LOAD-STORE optimization based on expression trees for the expression (A+B)/(C-D) is given

interrupt method in keypad operation coding using PIC16

Q. What is Shadow Mask? Shadow Mask is a metal sheet that has fine perforations (holes) in it and is situated a short distance before phosphor coated screen. The Phosphor dots