Language

Problem Solving as Language Recognition



Subjects to be Learned

Contents

In the previous section the concept of language was introduced and its properties have been briefly studied. You might be wondering why we study language. The main reason for studying language is that solving problems can be viewed as a language recognition problem as explained below, that is, the problem of checking whether or not a string belongs to a language. Thus instead of studying what kind of problems can be solved by what kind of computational devices and how, we can study languages and devices to recognize them which are simpler to deal with uncluttered with variations in actual devices, programming languages etc.

Below an example is given to illustrate how solving a problem can be viewed as recognizing a language.

Consider the following problem:
Is the longest of the distances between two nodes(i.e. the diameter) of a given graph less than a given integer k ? Here the distance is the smallest number of edges (or hops) between the nodes.

Some of the instances of this problem are as shown below:







Instance 1 asks whether or not the diameter of the given graph with one edge and two nodes is less than 1. Instance 2 asks whether or not the diameter of the given graph with four edges and four nodes is less than 2. Simiarlyt for Instance 3.

These problem instances can be represented by a string as follows:

Instance 1: 1,2;(1,2);1
Instance 2: 1,2,3,4;(1,2)(1,3)(1,4)(3,4);2
Instance 3: 1,2,3,4;(1,2)(1,3)(1,4)(2,3)(2,4)(3,4);3

Here the set of nodes, the set of edges and k are separated by ; in that order in the strings.

The solutions to these instances are:

Instance 1: No
Instance 2: No
Instance 3: Yes

There are infinitely many 'Yes' instances and 'No' instances for this problem. The set of 'Yes' instances is a language and so is the set of 'No' instances as well as the set of all instances and many others for this problem.
We can thus see that solving the problem for a given instance is equivalent to checking
whether or not the string representing the given instance belongs to the language of 'Yes' instances
of the problem. That is, the problem solving is the same as the language recognition. A problem can be solved if and only if the language of its 'Yes' instances is recognizable or decidable by a Turing machine. It is not solvable if the language is merely accecptable but not recognizable, or even worse if it is not even acceptable.






Test Your Understanding of Relationship between Problem Solving and Langauge

Indicate which of the following statements are correct and which are not.
Click Yes or No , then Submit.
There are two sets of questions.




Next -- General Induction

Back to Study Schedule

Back to Table of Contents