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

83,737 total views, 9 views today

Related

GATE Overflow
Aptitude Overflow

Answered: GATE CSE 2017 Set 2 | Question: 31

The following solution is based on the idea shared by @Sachin Mittal sir. Given, $g_y(z) = (1 – \beta + \beta z)^N$ $= g_y(z) = ((1 – \beta) + \beta z)^N$ Using binomial expansion, $= g_y(z) = \sum_{k=0}^{N}{\binom{N}{k}(1 – \beta)^{N-k}(\beta z)^k}$ $= g_y(z) = \sum_{k=0}^{N}{\binom{N}{k}(1 – \beta)^{N-k}(\beta)^k(z)^k}$ Let $a = (1 – \beta)$ and $b = \beta$ $= g_y(z) = \sum_{k=0}^{N}{\binom{N}{k}a^{N-k}b^k(z)^k}$ comapring $g_x(z) = \sum_{j=0}^{N}p_jz^j$ to the above $eq^n$ we know that each of the terms in the above summation will give $P(Y = j) = p_j, where$ $0 \leq j \leq N$ and $\because E(x) = \sum_{k=0}^{N}k*p_k$ $= E(x) = \sum_{k=0}^{N}{\binom{N}{k}a^{N-k}b^{k}k}$ $= E(x) = Nb(a + b)^{N-1}$… [...]

The initial IP datagram will be fragmented into two IP datagrams at I1. No other fragmentation will occur. --------------------------------------------------------------------------------------------------------- Link A-R1: Length = 940; ID = x; DF = 0; MF = 0; Offset = 0 Link R1-R2: (1) Length = 500; ID = x; DF = 0; MF = 1; Offset = 0 (2) Length = 460; ID = x; DF = 0; MF = 0; Offset = 60 Link R2-B: (1) Length = 500; ID = x; DF = 0; MF = 1; Offset = 0 (2) Length = 460; ID = x; DF = 0; MF =… [...]

Answered: Tanenbaum- Q30(Network layer)

Here μ is 2 million and λ is 1.5 million, so ρ=λ/μ is 0.75, and from queueing theory, each packet experiences a delay four times what it would in an idle system. The time in an idle system is 500 nsec, here it is 2 μsec. With 10 routers along a path, the queueing plus service time 20 μsec. #Solutioninthemanual [...]

Answered: GATE CSE 2011 | Question: 38

Given M1, M2, M3, M4 first of all we take first three matrix and see which combination is giving minimum number of multiplication. combination #1: M1*(M2*M3) → Here for M2*M3 no. of multiplication is q*r*s and then we will multiply M1 with the resultant matrix of M2*M3 and no. of multiplication will be p*q*s , so total no. of multiplication in M1*(M2*M3) is q*r*s + p*q*s = 10000 + 5000 = 15000 combination #2: (M1*M2)*M3 → Here for M1*M2 no. of multiplication is p*q*r and then we multiply M3 with the resultant matrix of M1*M2 and no. of multiplication will be p*r*s, so total no. of multiplication… [...]

Answered: UGCNET-Dec2019-II: 18

B) Sutherland-Hodgeman algorithm .. The Cohen–Sutherland algorithm is a computer-graphics algorithm used for line clipping. The algorithm divides a two-dimensional space into 9 regions and then efficiently determines the lines and portions of lines that are visible in the central region of interest (the view-port). Sutherland–Hodgman Algorithm is to clip polygon edges. A convex polygon and a convex clipping area are given. Input is in the form of vertices of the polygon in clockwise order. The Liang-Barsky algorithm is a line clipping algorithm. This algorithm is more efficient than Cohen–Sutherland line clipping algorithm and can be extended to 3-Dimensional clipping.… [...]

Answered: Andrew S. Tanenbaum Edition 5th Exercise 4 Question 20 (Page No. 352)

The smallest Ethernet frame is 512 bits, so at 1 Gbps we get 1,953,125 or almost 2 million frames/sec. However, this only works when frame bursting is operating. Without frame bursting, short frames are padded to 4096 bits, in which case the maximum number is 244,140. For the largest frame (12,144 bits), there can be as many as 82,345 frames/sec. [...]

Answered: CAT2019-2: 80

Given that , $a_{1} – a_{2}+a_{3}- a_{4}+ \dots + (-1)^{n-1} a_{n}=n \quad \longrightarrow (1)$ Now, put the various of $n$ and observe. $ n=1 \Rightarrow a_{1} = 1$ $ n=2 \Rightarrow a_{1} - a_{2} =2 \Rightarrow a_{2}=-1$ $ n=3 \Rightarrow a_{1} -a_{2} +a_{3} =3 \Rightarrow a_{3} =1$ $ n=4 \Rightarrow a_{1} -a_{2} +a_{3} -a_{4} =4 \Rightarrow a_{4} = -1$ $ n=5 \Rightarrow a_{1} – a_{2} +a_{3} - a_{4} +a_{5} =5 \Rightarrow a_{5} =1$ $ n=6 \Rightarrow a_{1}-a_{2} +a_{3}-a_{4} +a_{5} -a_{6} =6 \Rightarrow a_{6} = -1$ We observe that , when $n=\text{odd} \Rightarrow a_{\text{odd}} =1$ $ n=\text{even} \Rightarrow a_{\text{even}} = -1$ Now,… [...]

Answered: CAT2019-2: 79

Given that, $2^{6x}+2^{3x+2}-21 =0$ $ \Rightarrow \left ( {2^{3x}} \right)^2 +2^{3x}+2^2-21 =0 \longrightarrow (1)$ Let $2^{3x}$ be $K.$ Now, From equation (1,)we get $ \Rightarrow K^2 +4K-21 =0$ $ \Rightarrow k^2 +7k -3k-21 =0$ $ \Rightarrow K(k+7)-3(K+7)=0$ $ \Rightarrow (K+7)(K-3)=0$ $ \Rightarrow \boxed {K=-7,3}$ $ \Rightarrow K \neq {-7}$ because $2^{3x}$ not be $-7$ for any value of $x$ So, $ \boxed {k =3}$ $ \Rightarrow 2^{3x}=3$ Taking $\log_{2}$on the both sides. $ \Rightarrow\log_{2}2^{3x} =\log_{2}3$ $ \Rightarrow 3x \log_{2}2 = \log_{2}3$ $ \Rightarrow 3x = \log_{2}3$ $ \Rightarrow \boxed{ x = \frac {\log_{2}3}{3}}$ Correct Answer $: C$ [...]

Answered: CAT2019-2: 93

$\boxed {H^{2}=P^{2}+B^{2}}$ $ (20)^{2}=x^{2}+x^{2}$ $ \Rightarrow 400=2x^{2}$ $ \Rightarrow 200 = x^{2}$ $ \Rightarrow \sqrt{200}= x$ $ \Rightarrow x =10 \sqrt {2} $ $ \triangle{ APB } = \triangle {APC} $ $ \Rightarrow \frac{1}{2} AC \times BA = \frac {1}{2} BC \times AP$ $\boxed {\frac{AC\times BA}{BC} = AP}$ $ \Rightarrow \frac {10 \sqrt{2} \times 10 \sqrt {2}}{20}=AP$ $ \Rightarrow \frac{100 \times 2}{20}=AP$ $AP=10cm$ Correct Answer $:A$ [...]

Answered: CAT2019-2: 96

Given that, $ (2n+1) + (2n+3) + (2n+5)+ \dots + (2n+47) = 5280$ Here, the first term $a = 2n+1$ And, common difference $d = (2n+3) – (2n+1)$ $\Rightarrow d = 2n+3-2n-1 = 2 $ Let $’x’$ be the number of terms. The last term $l=a+(x-1)d$ $ \Rightarrow 2n+47 =2n+1+(x-1)2$ $ \Rightarrow 47=1+2x-2$ $ \Rightarrow 2x =48$ $ \Rightarrow \boxed {x=24}$ Now, the sum of A.P. $= \frac {x}{2} \left [ {a+l} \right]$ $ \Rightarrow 5280 = \frac {24}{2} \left [{2n+1+2n+47 } \right] $ $ \Rightarrow 12(4n +48) = 5280 $ $ \Rightarrow 12 \times 4 (n+12) =5280$ $ \Rightarrow… [...]

Answered: CAT2019-2: 100

Given that, Amal $ \Rightarrow P=12000, R=8\%$, at $1$ year compound interest. $\qquad \Rightarrow P=10000, R=6\%$, at semi-annually compound interest. When interest is calculated semi-annually then, the rate will be half and time will be doubled. $R=3\%, T=2$ years. Amal first $CI:$ $ \boxed {\text{Amount } = P \left ( 1+\frac{R}{100} \right)^T}$ $ \Rightarrow A=12000 \left (1+ \frac{8}{100} \right)^{1}$ $ \Rightarrow A=12000 \times \frac{108}{100}$ $ \Rightarrow A=12960$ $\because CI = A-P $ $\quad = 12960-12000$ $ \therefore \boxed{CI=960}$ Amal second $CI:$ $ \Rightarrow A=10000 \left (1+ \frac{3}{100} \right)^2$ $\Rightarrow A= 10000 \times \frac{103}{100} \times \frac{103}{100}$ $ \Rightarrow A=10609$ $\because CP=A-P$ $… [...]

Answered: CAT2019-2: 99

Given that, $15,{\color{Red}{19}},23,27,31,35,{\color{Red}{39}},\dots, 415 \quad \longrightarrow (1)$ $14,{\color{Red}{19}},24,29,34,{\color{Red}{39}}, \dots ,464 \quad \longrightarrow (2)$ Let $’n’$ be a number of common terms in the two sequences. Common difference in sequence $1 = 4,$ and in sequence $2 = 5.$ $\therefore$ The LCM of $(4,5)=20\quad $ (Common difference of new sequnce) Now, the sequence will be, $19,39,59,79,99,\dots , l \left(\leqslant 415\right) \quad \longrightarrow (3)$ We know that, last term $l=a+(n-1)d ,$ where $a = $ first term, $d = $ common difference, $n = $ number of terms. Now, $l \leqslant 415$ $\Rightarrow 19+(n-1)20 \leqslant 415\quad [\because a =19,d = 20]$ $\Rightarrow 19+20n-20 \leqslant 415$ $\Rightarrow… [...]

%d bloggers like this: