Finite State Machines
For a finite state machine, a configuration is simply the current state of the machine, together with the remaining input. The first configuration must be the initial state of and the complete input. A transition from a configuration to a configuration is allowed if for some input symbol and if has a transition from to on input . The final configuration must have the empty string as its remaining input; whether has accepted or rejected the input depends on whether the final state is an accepting state.
Read more about this topic: Computation History
Famous quotes containing the words finite, state and/or machines:
“All finite things reveal infinitude:”
—Theodore Roethke (1908–1963)
“Wooing, wedding, and repenting, is as a Scotch jig, a measure, and a cinquepace; the first suit is hot and hasty, like a Scotch jig, and full as fantastical; the wedding, mannerly-modest, as a measure, full of state and ancientry; and then comes repentance and, with his bad legs, falls into the cinquepace faster and faster, till he sink into his grave.”
—William Shakespeare (1564–1616)
“The machines that are first invented to perform any particular movement are always the most complex, and succeeding artists generally discover that, with fewer wheels, with fewer principles of motion, than had originally been employed, the same effects may be more easily produced. The first systems, in the same manner, are always the most complex.”
—Adam Smith (1723–1790)