Is that Option 2.

Power of acceptance doesn't change but the time might vary

Power of acceptance doesn't change but the time might vary

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

Time taken by one tape TM to simulate n moves of k-tape TM is

1) O(n)

2) O(n^k)

3) O(n^2)

4) None of the above

1) O(n)

2) O(n^k)

3) O(n^2)

4) None of the above

0 votes

Best answer

Option A. Its O(n)

Let's take a Language (L) = {a^nb^n}

a | a | a | a | aa | a | a | a | a | ------n |

b | b | b | b | b | b | b | b | b | ------n |

In Standard Turing Machine we do comparison for 1st 'a' to 1st 'b' via R/W header points to the tape, then we have to cross through n cells,

So for 'n' comparison for (a,b), require n*n cells = O(n^2).

But when we use Multi 2-Tape Turing Machine we require to R/W header points to the tape,

So first we copy a^nb^n from 1-tape to 2-tape through scanning the cells, it takes O(n) time to copy the input .

Now we easily compare with an appropriate header in both Tape 1 and Tape 2. in O(n) time .

So total time takes = Copy time + Comparsion time = O(n) +O(n) = O(n).

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.6k
- Others 1.8k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,339 questions

55,765 answers

192,354 comments

90,815 users