Theory of Computation for GATE: An 8-Week Topic-by-Topic Plan

Theory of Computation moves from drawable machines to questions about what no machine can decide. One reading does not create exam-ready recall. This eight-week plan assigns 10 hours weekly to concepts, constructions, practice, review, tests, and recovery.

Start with the dependency map, not a random chapter

Study the subject in four layers:

1. Strings, languages, DFA, NFA, regular expressions, and regular-language properties

2. Grammars, context-free languages, and pushdown automata

3. Turing machines, decidability, and computability

4. Complexity, P, NP, and reducibility

Each layer supplies the next; weak DFA state meanings make PDA constructions feel isolated. The structured Theory of Computation course follows this path through finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, decidability, computability, and complexity theory.

Before Week 1, spend 30 minutes on 12 questions, three each from regular languages, CFG/PDA, Turing machines/decidability, and complexity. Mark each correct, unsure, or wrong. Add practice; skip no chapter.

Use this exact 80-hour, eight-week schedule

A standard week has 2 hours learning on Monday and 2 on Wednesday; one solving hour on Tuesday, Thursday, Friday, and Saturday; a Saturday error-review hour; and a Sunday recovery hour or test.

Miss Wednesday? Move one hour to Sunday and convert one optional problem-solving hour into the second half of the missed 2-hour learning block. Preserve 10 hours by solving fewer new questions, not by doubling Thursday. Week 3 shifts one learning hour to solving; Week 8 uses the calendar below.

Weeks 1 to 3: make one regular-language example do four jobs

Let L = {w in {0,1}* | w ends in 01}. Build a DFA with start state q0 and accepting state q2:

1101 traces q0 -> q0 -> q0 -> q1 -> q2 and is accepted. 1110 traces q0 -> q0 -> q0 -> q0 -> q1 and is rejected. The equivalent regular expression is (0|1)*01.

Redraw it, trace both strings, write the expression, then change “ends in 01” to “contains 01”. Compare with Finite Automata: DFA vs NFA. Finish Week 3 with construction, trace, equivalence, minimisation, closure, and pumping-lemma questions.

Weeks 4 to 5: connect grammar derivations to stack behaviour

Use S -> 0S1 | epsilon, which generates L = {0^n1^n | n >= 0}. To derive 0011:

S => 0S1 => 00S11 => 0011

The last step replaces S with epsilon. 0101 is impossible because every generated 0 must precede every generated 1.

For the PDA, use bottom marker Z0 and stack symbol X. The two 0s change Z0 to XZ0, then XZ0 to XXZ0. The two 1s pop to XZ0, then Z0. Accept only with exhausted input and Z0 remaining; do not switch midway to empty-stack acceptance.

Write one derivation, draw one stack trace, then solve one classification question. Continue with Context-Free Grammars and Pushdown Automata.

Weeks 6 to 7: separate machine questions from decision questions

Let D be a DFA, M a Turing machine, w an input, and angle brackets an encoding.

Say the reduction in words: A <=p B transforms an A instance into a B instance. If B is in P, A is in P. If A is NP-hard and B is in NP, B is NP-complete. The direction B <=p A does not establish B as NP-hard.

Tag each question: design, trace, convert, prove or disprove closure, classify, or reduce. This trains you to recognise the operation being tested.

Use a solve-analyse-retry loop, not a question counter

Use 90 minutes: 10 for closed-book recall, 45 for 10 questions, 25 to classify and rework errors, and 10 to update a one-page revision sheet. KnowledgeGate has about 1,100 published Theory of Computation questions for fresh sets and retries.

Suppose you get 6 correct, 2 concept errors, 1 conversion error, and 1 careless trace error. That is 10 questions and 6/10 = 60% first-attempt accuracy. Start next time with those 4 failures plus 6 new questions. As a practical rule, move a topic to weekly revision only after two fresh 10-question sets each reach 8/10.

Log date, topic, question action, wrong assumption, corrected rule, and retry date. Example: Week 2 Friday | epsilon-NFA conversion | convert | omitted epsilon-closure of q0 | take epsilon-closure before and after each symbol move | Week 3 Tuesday.

Week 8: test, repair, and choose the next action

• Monday: 25 mixed questions for 60 minutes, then 30 minutes' analysis.

• Tuesday: rebuild the dependency map and four revision cards from memory for 60 minutes.

• Wednesday: 25 fresh questions for 60 minutes, then 30 minutes' analysis.

• Friday: redo errors for 60 minutes, then review for 30 minutes.

• Saturday: take a 120-minute self-timed subject test, then review for 60 minutes.

• Sunday: solve your weakest topic for 60 minutes, then review for 30 minutes.

This totals 1 hour learning, 6 solving, and 3 reviewing. With the GATE Test Series, use the test's displayed duration and adjust only Saturday's split within 10 hours.

Add no new chapter in final three days. Revise the dependency map, regular-language construction, grammar/PDA trace, decidability card, reduction directions, and your error log.

The short version

Follow dependencies, solve more than you read, analyse errors, and protect a recovery block. Use the GATE CS six-month plan for the wider timetable and the GATE preparation catalogue for supporting resources, then take a timed test and repair your weakest operation.