Sunday, April 18, 2010

automata tutorial

In theoretical computer science, automata theory is the study of abstract machines and the problems which they are able to solve. These abstract machines are called automata. A discrete automaton is a mathematical model for a finite state machine (FSM). A FSM is a machine that takes a symbol as input and "jumps" or transitions, from one state to another according to a transition function (which can be expressed as a table). For example in "Mealy" variety of FSMs, this transition function tells the automaton which state to go to next given a current state and a current symbol.

Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages they are able to recognize. Automata play a major role in compiler design and parsing.
An automaton is supposed to run on some given sequence or string of inputs in discrete time steps. At each time step automaton gets one input that is picked up from a set of symbols or letters, which is called Alphabet. Automaton takes input of a finite sequence of symbols, which is called a word. An automaton contains a finite set of states. During each time instance of some run, automaton has to be in one of its states. At each time step when automaton reads a symbol, it jumps or transits to next state depending on its current state and the read symbol. This function over current state and input symbol is called transition function. The automaton reads input word one symbol after another in the sequence and transits from state to state according to the transition function, until the word is read completely. Once the input word is read, the automaton is said to have been stopped and the state at which automaton has stopped is called final state. Depending on the final state, it's said that the automaton either accepts or rejects an input word. There is a subset of states of the automaton, which is defined as a set of accepting states. If the final state is an accept state, then the automaton accepts the word. Otherwise, the word is rejected. The set of all the words accepted by an automaton is called the language recognized by the automaton.
more on computer science
seminar topic
newidea2.com

No comments:

Post a Comment