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