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

86,487 total views, 17 views today

Related

GATE Overflow
Aptitude Overflow

Answered: Postal Book Course

C) L and L’ cannot be predicted. because compliment of NFA is doesn’t means compliment of langugae. for eg. L = {starting with “a” over {a,b}} it L’ = { ϵ, b, ba,bba,baaa,baab …...} let M is NFA for L then M’ is not an NFA for L’ it may be sometimes in other example. [...]

Answered: Cyclic group

It can or cannot be. Because the order of group should be divisible by the order of element. [...]

Applied Test Series

Suppose that we are considering an enhancement that runs 10 times faster than the original machine but is usable only 40% of the time. What is the overall speedup gained by incorporating the enhancement. [...]

Answered: GATE CSE 2002 | Question: 15

Answered: GATE CSE 2002 | Question: 15

Please change natural join to simplest relational algebraic operations. [...]

Applied Test Series

Suppose you want to transfer a file from Hyderabad to Bangalore. The size of file is 90,000 bytes. The file will be transferred in 1,500-byte data packets, for which 40 bytes are taken up with headers. The size of acknowledgement packets is 40 bytes including header. Every packet is acknowledged. The communication is bidirectional and the bandwidth is 100 Mbps (megabits/sec) in each direction. Hosts can send and receive at the same time. The latency from Hyderabad to Bangalore is 5 ms, as is the latency in the opposite direction. Assume that time to process a packet is very small,… [...]

Answered: GATE Civil 2021 Set 2 | GA Question: 9

Answered: GATE Civil 2021 Set 2 | GA Question: 9

Similarly, do for another side Therefore, Area of shaded area = $2 * (\frac{ r^{2}}{4}(\pi – 2)) = \frac{ r^{2}}{2}(\pi – 2)$ Now, total area = $r^{2}$ Therefore, Probability = $ \frac{ \frac{ r^{2}}{2}(\pi – 2)}{r^{2}}$ = $ \frac{ 1}{2}(\pi – 2)$ = $\frac{ \pi}{2} – 1$ So, Ans is $C$ [...]

Answered: CAT2018-2: 98

Given that, DIAGRAM In drum$1,$ $A$ and $B$ are in the ratio of $18 : 7.$ So, the quantity of $A = \frac{18}{25}$ The quantity of $B = \frac{7}{25}$ In final mixture, $A$ and $B$ are in the ratio of $13 : 7.$ So, the quantity of $A = \frac{13}{20}$ The quantity of $B = \frac{7}{20}$ In drum$2,$ let us assume the proportion of $B$ with respect to the overall mixture is $x.$ So, $ \frac{ \frac{7}{25} \times 3 + x \times 4}{7} = \frac{7}{20}$ $\Rightarrow \frac{21}{25} + 4x = \frac{49}{20}$ $\Rightarrow 20 (21 + 100x) = 25… [...]

Answered: CAT2018-2: 83

Given that, Total mixture $ = 175 \; \text{ml} + 700 \; \text{ml} $ $ = 875 \; \text{ml} $ Gopal takes out $10\%$ of the mixture and substitutes it by water of the same amount. We know that, A container contains $\text{x} \; \text{units}$ of the liquid from which $\text{y} \; \text{units}$ are taken out and replaced by water. Again from this mixture $\text{y} \; \text{units}$ are taken out and replaced by water. If this process is repeated $\text{‘n’}$ times. Then, The liquid left in the container after $\frac{ \text{n}^{th} \text{operation}}{ \text{Original quantity of the liquid in the container}}… [...]

Answered: CAT2018-1: 95

Let the cost price per kg of type $A,$ and $B$ be $\text{Rs.} x$ and $\text{Rs.} y$ respectively. When, $A$ and $B$ are mixed in the ratio of $3:2,$ then the profit is $10\%,$ So, selling price $:$ $ \left( \frac{3x+2y}{5} \right) \times \frac{110}{100} = 40 $ $ \Rightarrow \left( \frac{3x+2y}{5} \right) \times \frac{11}{10} = 40 \quad \longrightarrow (1) $ When, $A$ and $B$ are mixed in the ratio of $2:3,$ then the profit is $5\%.$ So, selling price $:$ $ \left( \frac{2x+3y}{5} \right) \times \frac{105}{100} = 40 $ $ \Rightarrow \left( \frac{2x+3y}{5} \right) \times \frac{21}{20} = 40 \quad \longrightarrow… [...]

Answered: CAT2018-1: 85

Let the cost price of peanuts per kg be $\text{Rs}. x.$ Then, the cost price of walnuts per kg be $\text{Rs}. 3x.$ A wholesaler sold $8 \; \text{kg}$ of peanuts at a profit of $10\%.$ So, the cost price of $8 \; \text{kg}$ peanuts $ = \text{Rs}. 8x.$ Therefore, selling price of $8 \; \text{kg}$ peanuts $ = 8x \times \frac{110}{100} = \text{Rs.} \frac{88x}{10} $ And, he also sold $16 \; \text{kg}$ walnuts at a profit of $20 \%.$ So, the cost price of $16 \; \text{kg}$ walnuts $ = 16 \times 3x = \text{Rs.} 48x $ Therefore, selling price… [...]

Answered: CAT2018-2: 88

Answered: CAT2018-2: 88

Given that, points $A$ and $B$ are $150 \; \text{km}$ apart. Each car travel at a speed of $100 \; \text{km/hr}$ for the first $50 \; \text{km}.$ $ \boxed{\text{Time} = \frac{\text{Distance}}{\text{Speed}}} $ So, $ t_{1} = \frac{50}{100} $ $ \Rightarrow \boxed{t_{1} = \frac{1}{2} \; \text{hour}} $ And, each car travel at a speed of $ 50 \; \text{kmph}$ for the $50 \; \text{km}.$ So, $ t_{2} = \frac{50}{50} $ $ \Rightarrow \boxed{t_{2} = 1 \; \text{hour}} $ And, each travel at a speed of $25 \; \text{kmph}$ for the last $50 \; \text{km}. $ So, $t_{3} = \frac{50}{25} $ $… [...]

Answered: CAT2018-2: 71

Answered: CAT2018-2: 71

Given that, $A$ and $B$ are two points such that $B$ is $350 \; \text{km}$ of $A.$ Let $`x\text{’}$ and $`y\text{’}$ be the speed $(\text{in km/hr})$ of cars starting from both $A$ and $B$ respectively. Let us assume $\text{car 2}$ traveled $ d\;\text{km}$ and meet $\text{car 1},$ after $1 \; \text{hour}.$ $\boxed{\text{Speed} = \frac{\text{Distance}}{\text{Time}}}$ So, $ S_{\text{car 1}} = \frac{350-d}{1} $ $\Rightarrow \boxed{x = 350 – d} \quad \longrightarrow (1) $ And, $ S_{\text{car 2}} = \frac{d}{1} $ $ \Rightarrow \boxed {y = d} $ From the equation $(1),$ we get $ x = 350 – d $ $ \Rightarrow x = 350 – y… [...]

%d bloggers like this: