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
What is a word line? In a memory cell, all the cells of a row are linked to a common line called as word line

In order to calculate the performance of the program, the normal form of analysis of the program is to simply measure the total amount of CPU time needed to implement the various p

Define ROM? It is a non-volatile memory. It includes only reading of stored data.

Translate the following sentences into predicate logic, using Russell's theory of definite descriptions to represent the article the. a. The wizzard of Oz fell. b. Everyone a

Q. Which Colour technologies used in Monitors and Printer? Monitor screens and Printers use different colour technologies.  The monitor uses RGB and the Printer CMYK. So, how d

Discuss the advantages of store program control (SPC) automation in telephone switching. Advantages of SPC: (i) Simple to control (ii) Simple to maintain (iii) Fine-

Q. Dynamic Configuration of parallel virtual machine? int pvm_addhosts( char **hosts, int nhost, int *infos ) Add hosts to virtual machine. hosts is an arra

solution for oadovan string inc language

Coding advantages of casex or casez By using casex or casez has the following coding advantages: -  It reduces number of lines, especially if the number of bits had been m

Define the term- Verification It is a way of preventing errors when data is copied from one medium to another (for instance from paper to disk/CD or from memory to DVD, etc.).