Why Study Automata Theory || Formal Languages Automat Theory

Why Study Automata Theory?

There are several reasons why the study of automata and complexity is an important part of the core of Computer Science.

Introduction to Finite Automata

Finite automata are a useful model for many important kinds of hardware and software.

·         Software for designing and checking the behavior of digital circuits.

·         The lexical analyzer of a typical compiler, that is, the compiler component that breaks the input text into logical units, such as identifiers, keywords and punctuations.

·         Software for scanning large bodies of text, such as collections of Web pages, to find occurrences of words, phrases or other patterns.

·         Software for verifying systems of all types that have a finite number of distinct states, such as communications protocols of protocols for secure exchange of information.

While we shall soon meet a precise definition of automata of various types, let us begin our informal introduction with a sketch of what a finite automaton is and does. There are many systems or components, such as those enumerated above, that may be viewed as being at all times in one of a finite number of “states”. The purpose of a state is to remember the relevant portion of the system’s history. Since there are only a finite number of states, the entire history generally cannot be remembered, so the system must be designed carefully, to remember what is important and forget what is not.

        The advantage of having only a finite number of states is that we can implement the system with a fixed set of resources.

        For ex, we could implement it in hardware as a circuit or as a simple form of program that can make decisions looking only at a limited amount of data or using the position in the code itself to make the decision.

Ex:1 : Perhaps the simplest non-trivial finite automation is an on/off switch. The device remembers whether it is in the “on” state or the “off” state, and it allows the user to press a button whose effect is different, depending on the state of the switch. That is, if the switch is in the off state, then pressing the button changes it to the on state, and vice versa.

A finite automation model for the switch is shown in fig, as for all finite automata the states are represented by circles, in this example we have named the states on and off. Arcs b/w states are labeled by “inputs” which represent external influences on the system.

        Here both arcs are labeled by the input push, which represents a user pushing the button the intent of the two arcs is that whichever state the system is in, when the push input is received it goes to the other state.

        One of the states is designated the “start state” the state in which the system is placed initially. In our ex, the start state is off and we conventionally indicate the start state by the word start and an arrow leading to the state.

        It is often necessary to indicate one or more states as “final” or “accepting” states. Entering one of these states after a sequence of inputs indicates that the input sequence is good in some way.