A finite state machine (FSM) is either deterministic or non-deterministic. A deterministic FSM (DFSM) is a FSM with at most one transition for each symbol and state. A non-deterministic FSM (NDFSM) is a FSM whose transition function maps input symbols and states to a (possibly empty) set of next states. The transition function also may map the null symbol (no input symbol needed) and states to next states.

Consider the DFSM M = {I, O, S, d, l, S0) defined by:
- Input set I = {1, 0}
- Output set O = {}
- State set S = {A, B, C, D}
- State transition function d
- Output function l

Suppose that the initial state of the machine M is B and the input sequence is 0110, the machine will proceed through states A, B, C and A. If the input is either 110 or 111, and initial state is B, then the machine will visit the states A, C and D. Similarly, for the same initial state, with the input sequence 010100 the machine will proceed to states B, A, B, A, B, A and A.

2) Describe the functionality of the above DFSM using transition tables. Consider that the system starts always from state B. What happens if the system will start from another state - say A?

3) Follow the transitions made by this FSM and try to describe its functionality in your own words based on your interpretation of the sequence of events and states obtained after each transition.

4) Try to classify the system as being Mealy or Moore.

5) Construct a DFSM that reads a text and finds the first occurrence of the substring "0101f". More precisely, assume the alphabet is {0, 1, f}, and construct a DFSM that accepts the language {x0101f: x in {0, 1, f}}. Be careful; consider the behaviour of your machine on the string 010101f. Also, note that the problem asks for a deterministic machine. Explain how your machine works.

Solution Summary

This solution is provided in 719 words in an attached .doc file. It uses sequence diagrams and state transition diagrams and tables to answer the questions about the finite state machine.

Determine whether each of these strings is recognized by the given deterministic finite-state automaton (which is displayed in an attached .doc file):
(a) 010
(b) 1101
(c) 1111110
(d) 010101010

Hi,
I'm looking for a FSA (FiniteState Acceptor) for all binary strings containing an odd number of 0's. A state diagram is the easiest for me to understand. A valid regular expression to describe the language (I've verified this) is 1*0(1+01*0)*
Thanks!

Cognitive scientists believe there is an infinite potential variety of human behavior. However, they also believe that this infinite behavior is produced by a finite devise, such as the Turing machine. How can these two views be reconciled?

(a)For each of the following languages over the unary alphabet {a}, construct a finite automaton accepting it.
i. {a^2}
ii. {a^2, a^3, a^4}
(b) Let A be any finite nonempty subset of {a, a^2, a^3, a^4,...}. Is there always a finite automaton that accepts A?

See attache file for full description. The particle is in a finite square well and we are required to show that if the potential approaches infinity we regain the energy levels of infinite well. Find the condition for solution and show that there is always an even solution and there is no odd solution unless.
V > h^2*Pi/8ma^

Particle in a box
For the particle in a box, is the function Ψ(x)=Cx(L-x) a possible state of the system? (C is constant) Justify answer.
(the parameter l in the wavefunction is the length of the box)
V(x)=∞ V(x)=∞

Key Characteristics: Please give an English text description - in your own words - highlighting key characteristics of the topic.
1. Alphabet (or vocabulary):
2. Language:
3. Type 0 grammar:
4. Derivation (or parse) tree:
5. Backus-Naur form:
6. Language recognized by an automaton:
7. Regular expression:
8. Regular se

Proposition 10.2.1: (the addition principle)
Suppose that X and Y are disjoint finite sets. Then X U Y is finite and |X UY| = |X| + |Y|.
Corollary 10.2.2:
For a positive integer n, suppose that X1, X2....,Xn is a collection of n pairwise disjoint finite sets (i.e. i does not = j => Xi Xj = empty set)
Then X1 U X2

Give a non-deterministic finitestate automaton that recognizes the language L subset {0,1}* that consists of all words w such that some appearance of two 0's in w is separated by an even number of 1's. (For example: the words 0010010110, 001101 are in the language but the words 0101110, 001001 are not.)
(As a note, this i