Question

Determine the computational complexity of the following language:

0ⁿ1ⁿ

^"Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, (how difficult they are to solve) and relating these classes to each other. A computational problem is a task solved by a computer. Some computational problems are impractical as the known algorithm takes too much time and memory to complete."

Answer 1

Computational complexity can be calculated by finding the time required to solve instances of a problem as a function of their sizes, using a Turing machine as the computer model.

In this question we have to find the computational complexity of processing language :

{0^n1^n | n>= 0}

DESIGNING A TURING MACHINE FOR THIS LANGUAGE :

The algorithm of the Turing Machine is as follows :

1. Change 0 to X

2.Move RIGHT to First "1" : If None : Reject ( to check for the where number of zereos are more than number of ones )

3.Change 1 to Y

4.Move to LEFT to Leftmost 0

5. Repeat the above steps until no more 0 are found

6. Make sure no 1 remains ( to check for the case where number of ones are more than number of zeroes )

Thus to compute complexity we find how many moves it takes for the single tape turing machine to process the Natural Language.

As can be seen from the algorithm , for every 0 , the machine moves n moves ahead to find the matching one and then they move back n steps to the next zero . This process is repeated for all n zereos.

This implies n*(2n) moves are required.

This can be simplified to n*n when analyzing complexity.

Thus , the computational complexity using Single Tape T.M. would be of the order O(n^2) .