Theory of Computation Preparation Resources for GATE CSE

June 21, 2015 by Arjun Suresh 17 Comments

Theory of Computation Syllabus

http://www.gatecse.in/gate-cse-2016-syllabus/#Theory_of_Computation

Regular expressions and finite automata.
Context-free grammars and push-down automata.
Regular and context-free languages, pumping lemma.
Turing machines and undecidability.

” No changes ”

Book

Peter Linz

Video

You won’t get better video for TOC than Shai Simonson’s.

GO Classroom:

Course Link

Recommended Tests:

GATE Overflow Test Series – GATE CSE 2022

Web Links

Previous Year Questions

GATE Overflow Questions

Important Questions

Important Questions in Theory of Computation

GATE CSE Discussions

GATE CSE Syllabus

Best Books for GATE CSE

87,705 total views, 24 views today

Related

GATE Overflow
Aptitude Overflow

NPTEL Assignment Question

Anjali has enrolled for a part-time Masters programme where she has to complete 8 courses, numbered 1, 2, . . . , 8. Each course takes a full semester to complete. She can take as many or as few courses as she wants in each semester. Some courses are prerequisites for other courses. If course A is a prerequisite for course B, she can take course B the semester after she finishes course A, or any time after that, but not before. Given the following information about prerequisites, compute the minimum number of semesters she needs to complete these courses… [...]

NPTEL Assignment Question

An undirected graph G has 300 edges. The degree of a vertex v, deg(v), is the number of edges connected to v. Suppose V = {v1,v2,...,v30}. What is the value of deg(v1)+ deg(v2) + · · · + deg(v30)? 300 600 900 None of these [...]

NPTEL Assignment Question

NPTEL Assignment Question

NPTEL Assignment Question

NPTEL Assignment Question

NPTEL Assignment Question

NPTEL Assignment Question

NPTEL Assignment Question

Suppose there are k sorted lists (decreasing order) with n/k elements in each list. What is the time complexity to merge them into one single sorted list. Hint: Maintain a heap of k elements. Think which k elements to choose. A. O(nlogk) B. O(n) C. O(nk) D. O(nlogn) [...]

Answered: CAT2020-1: 54

Given that, area of rectangular metal sheet $ = 135 \; \text{sq inches}.$ Now, we can draw the diagram. Diagram Let the length and breadth of the rectangle be $l$ and $b$ respectively. Let the radius of a circle be $r \; \text{inches}.$ $lb = 135$ Let the painted area be $3x.$ Then left unpainted area will be $2x.$ So, $3x + 2x = 135$ $\Rightarrow 5x = 135$ $ \Rightarrow \boxed{x = 27}$ The painted area (area of circle) $ = 3 \times 27 = 81 \; \text {sq inches}.$ The left unpainted area $ = 2 \times 27… [...]

Answered: CAT2020-1: 53

Let the volumes of $ A, B,$ and $C$ be $3x, 4x$ and $7x.$ Weights of the same volume of the metals $ A, B,$ and $C$ are in the ratio $5:2:6.$ So, the ratio of the weights in the overall alloy. $A:B:C = (3x \times5) : (4x \times 2) : (7x \times 6)$ $ \Rightarrow A:B:C = 15 : 8 : 42 $ $\therefore$ The weight of metal $C = 130 \times \frac{42}{65} = 84 \; \text{kg}.$ Short Method$:$ $\qquad \qquad A \quad B \quad C$ Volume$: \quad3 : 4 : 6$ Weight$: \quad 5 : 2 : 6 \; (1… [...]

Answered: CAT2020-1: 52

Given that, Veeru$:$ Principle $(P_{1}) = \text{Rs} \; 10000$ Rate $(R_{1}) = 5 \%$ Joy$:$ Principle $(P_{2}) = \text{Rs} \; 8000$ Rate $(R_{2}) = 10 \%$ Let the time after Joy’s investment, when the balances become equal be $n$ years. i.e., principal plus accumulated interest $ P_{1} + \left[ \dfrac{P_{1} \times R_{1} \times (n+2)}{100} \right] = P_{2} + \left[ \dfrac{P_{2} \times R_{2} \times (n)}{100} \right] $ $ \Rightarrow 10000 + \left[ \dfrac {10000 \times 5 \times (n+2)}{100} \right] = 8000 + \left[ \dfrac{ 8000 \times 10 \times (n)}{100} \right] $ $ \Rightarrow 2000 + 500 (n+2) = 800n $ $ \Rightarrow 2000 + 500n + 1000 = 800n… [...]

Answered: CAT2020-1: 51

Given that, the product of $3- \text{digit}$ numbers is more than $2$ but less than $7.$ Let the $3- \text{digit}$ number be $xyz.$ Then, $ 2< x \times y \times z < 7 $ $ \Rightarrow x \times y \times z = 3 (or) 4 (or) 5 (or) 6 $ Case$1:$ When $x \times y \times z = 3$ Three possibilities. Case$2:$ When $x \times y \times z = 4$ Six possibilities. Case$3:$ When $x \times y \times z = 5$ Three possibilities. Case$4:$ When $x \times y \times z = 6$… [...]

Answered: CAT2020-3: 75

Let us assume that the total marks is $100x$ Then Bishnu marks =$52x$ Asha marks = $64x$ Now according to the question, if $y$ is the mark obtained by Ramesh, $52x=y-23 \longrightarrow (1)$ $64x=y+34 \longrightarrow (2)$ Equation $(2)-(1)$ $\Rightarrow 12x=57 $ $\Rightarrow x= \frac{57}{12}$ $\therefore 84x=\frac{57*84}{12}=399$ Note: $84x$ means scored obtain by Gita that is $84 \%$ So option $B$ is correct. [...]

Answered: CAT2020-3: 52

Let us assume Tom age is $x$ then: Dick’s age= $3x$ Harry’s age=$2.3x=6x$ Now according to the given question, Dick’s age is 1 year less than the average age of all three, $\therefore 3x=\left (\frac{3x+6x+x}{3} \right )-1$ $\Rightarrow 3x=\left (\frac{10x}{3} \right )-1$ $\Rightarrow 1=\frac{10x}{3}-3x$ $\Rightarrow 1=\frac{10x-9x}{3}$ $\Rightarrow 1=\frac{x}{3}$ $\Rightarrow x=3$ So Tom age is $3$ year, Harry’s age is $=6x=6*3=18$ year. $\therefore$ Harry’s age is $18$ year. [...]

%d bloggers like this: