Finite state automaton, Computer Engineering

Assignment Help:

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: [email protected], 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: [email protected], jsmith, jsmith@olympus, [email protected], [email protected], jsmith.edu, [email protected], [email protected], [email protected], [email protected]

(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.


Related Discussions:- Finite state automaton

Features of supply chain management, Features of Supply Chain Management ...

Features of Supply Chain Management Supply Chain Management Consultancy's scope is extensive, and typically contains:  1.  Sales order processing and customer service 2.

Explain ai applications, AI Applications Search is a important elemen...

AI Applications Search is a important element of an AI system, and search functions are executed on huge quantities of complicated structured data by means of unstructured in

What are the various layers of a file system, What are the various layers o...

What are the various layers of a file system? The file system is composed of lots of dissimilar levels. Each level in the design uses the characteristic of the lower levels to

Data packets - universal serial bus, Data packets: A data packet consi...

Data packets: A data packet consists of the PID which is followed a 16-bit CRC and by 0-1023 bytes of data payload (up to 1024 in high speed and at most 8 at low speed) The

Common tasks to accomplish - artificial intelligence, Common Tasks to Accom...

Common Tasks to Accomplish: Once you've worried about what and why you're doing "AI", what has inspired you and how you're going to approach the job, then you just start to th

What kinds of statements are present in an assembly language, What kinds of...

What kinds of statements are present in an assembly language program? Discuss. An assembly program contains subsequent three types of statements: 1. Imperative statements: The

Is there a macro recording interface in gimp, Not at this time. With GIMP b...

Not at this time. With GIMP based on GEGL, so that all changes are non-destructive, it will be much easier to execute this feature by just remembering all nodes in given range and

Transition table for sequential circuits, sovling questions on transition t...

sovling questions on transition table for sequential circuits

Subsequent step in karnaugh map, The subsequent step in Karnaugh map is to ...

The subsequent step in Karnaugh map is to map truth table in the map. Mapping is done by putting a 1 in respective square belonging to 1 value in truth table. This mapped map is us

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd