Introduction

A language is a system of signs used to communicate information to others. However, the language of computation is a combination of both english and mathematics. Fundamentally, a computer is a symbol manipulator, in the sense, that it takes sequences of symbols as inputs and manipulates them as per the program specifications. These symbols are precise and unambiguous, unlike the language of humans. The first step in communicating a problem to a machine is the design of a proper language of computation and this is the fundamental object of computability.

While discussing about languages, it is important to note two cases:

1. a. During the evaluation of an input expression (e.g.: calculator), the language of arithmetic expression handles both the input and the output communication.

2. b. In the case of web form, the language simply describes all the legitimate inputs to the field and the output is simply a binary value-Yes or No.

Thus, the problems belonging to case (a), have both input and an output language, while, those belonging to case (b), have only an input language. It is of interest to note that, from the perspective of theory of computation, any type of problem can be expressed in terms of a language recognition.

Since a language is a medium of communication, it should be given some meaning (i.e. its semantics). But much of the manipulation of symbols, strings and language could be done effectively without understanding their semantics and this is the subject of this section. In other words, the mathematical study of the theory of computation begins with the understanding of the mathematics of symbols and strings.