Introduction of theory of computation notes: Examples of automata machines, Finite Automata as a language acceptor and translator, Moore machines and mealy machines, composite machine, Conversion from Mealy to Moore and vice versa.

Introduction of theory of Computation

We shall study different types of theoretical machines that are mathematical models for actual physical processes.  By considering the possible inputs on which these machines can work, we can analyze their various strengths and weaknesses.  We then arrive at what we may believe to be the most powerful machine possible.  When we do so, we would be surprised to find the computational tasks that this machine cannot perform.  This will be our ultimate result that no matter what machine we build, there will always be questions that are simple to state but even the most powerful machine possibly cannot answer.  Along the way, we hope you would understand the concept of computability, which is the foundation of further research in this field.   

A Brief introduction to the theory of Computation

Computer Science is the systematized body of knowledge concerning computation. It has two major components. First, the fundamental ideas and models underlying Computing, and second engineering techniques for the design of computing system, both hardware and software, i.e , application of theory to design.

Theoretical computer science (TCS) mainly deals with the study of fundamental ideas and models underlying computing, which can be used as tools in the design of computing systems.

“Theoretical computer science (TCS): Machine in TCS, it will be the logical mechanism by which we can process the given input data and will produce the output data.”

In the TCS, we analyze physical machine such as Juice Machine. If single glass Juice Price is Rs 10. We need 2 coins of Rs 5 for juice. If you do not want to juice please reset the button. Fig 1 shows the diagram of Juice Machine.

Fig : Example of Juice Machine

From this diagram it is very clear to show that the given input data and will produce output data. Fig 2 shows the state diagram of Juice Machine.

Input = I (10, 5, J = Juice, R = Reset)

Output= O (NJ= No Juice, 5, 10)

Fig : State Diagram of Juice Machine

Type of Theory of computer science (TCS)

Theory of computer science (TCS) can be partitioned into two sub-disciplines:

1. Theory of Computation
2. Theory of Programming     

Theory of Computation

The theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm.

“It aims at understanding the nature of computation and specifically the inherent possibilities and limitation of efficient computation”.

Theory of Computation can be sub-divided to numerous overlapping areas. Two main cluster of areas are complexity theory and algorithms, where the distinction is on whether the focus is on the computational resources (as in complexity theory) or on task to be solved (as in algorithm). Indeed, complexity theory is sub-divided according to the model and resources computation (i.e. time complexity, space complexity, circuit complexity etc.), whereas algorithms are sub-divided according to respective tasks (e.g., graph theory, linear programming, computational geometry etc.). In addition, there are areas of the theory of computation that are not to be forced into above clusters. The field is divided into three major branches: automata theory, computability theory and computational complexity theory. Example includes Cryptography, Distributed Computing and Computational Learning Theory.         

Theory of Programming

It is concerned with the actual task of implementing computations (i.e. writing computer programs).

Computer theory applications

Theory of computation provides us with many good applications. Finite state machines are used in string searching algorithms, compiler design, control unit design in computer architecture, and many other modeling applications. Context free grammars and their restricted forms are the basis of compilers and parsing. NP-Complete theory helps us distinguish the tractable from the intractable. We do not focus on these applications. They are deep enough to require a separate course, and hopefully you have already seen some of them.

Three Basic Concepts

Three fundamental ideas are the major themes language, grammars and automata. We are familiar with the notation of natural languages which are such as English and French. In English, we distinguish the three different entities: letters, word and sentences. There is a certain parallelism between the fact that groups of letters make up words and fact that groups of words make up sentences. Not all collection letters make up words and not all collection words form a sentence. Certain groups of sentence make up coherent paragraphs, certain groups of sentence make up coherent stories and so on.

This situation also exists with computer languages certain character strings are recognized words (IF, DO, END…). Certain strings of words are recognizable commands. Certain set of commands became a Program (with or without data) that can be compiled, which means translated into machine commands.

We shall study, for the sake of simplicity, two types of sentence in English with a view to formalizing the construction of these sentences. We will first begin with techniques of symbol manipulations. Human communicate through symbols. These symbols need not necessarily be having any pictorial notation on paper (eg: verbal communication). To present the sound, the character and their combination are used, so that communication will take a symbolic form on paper. A symbol is the basic entity which is not defined. But once we accept the symbols. Using symbols we can generate the strings which are defined as sequence of symbols.

Theory of Computation Notes

आशा करता हूँ, कि यह आर्टिकल आपको पसंद आया होगा तो सोच क्या रहे हैं अभी इसी वक्त इसे अपने दोस्तों के साथ सोशल मीडिया पर Share करें।

Thanking You………………धन्यवाद………………..शुक्रिया………………..मेहरबानी…………………..

Read More: InfoKhajana.com covered the following topics in these notes.

• R Language
• Digital Marketing
• Theory Of Computation:: Introduction of Theory of Computation
• Theory Of Computation:: Basic Terminologies of Theory of Computation
• Theory Of Computation:: Languages
• Theory Of Computation:: Kleene Closure
• Theory Of Computation:: Machine

References –
cs.stanford.edu
Wikipedia