Theory of Computation

June 21, 2015 by Arjun Suresh 14 Comments

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.

Web Links

Previous Year Questions

http://gateoverflow.in/questions/automata-theory

Important Questions

http://gateoverflow.in/blog/21/important-questions-in-theory-of-computation

Recommended Tests

GATE CSE Discussions

2016 – Decidability

74,592 total views, 15 views today

Related

GATE Overflow
Aptitude Overflow

Answered: GATE2006-IT-34

B is correct. Incorrect as ((a+b)*b) can generate strings like aaaab which is not possible with given grammar. Correct. Also incorrect not always we will have a’s and b’s of same length, hence false a*b* can generate strings where a’s is greater than b false again. [...]

Answered: GATE2003-51

C ) Is the Answer. A- Incorrect we get two parse trees for string – aabb ..there may be many as well. B- take x – ab, y – abab, xy= ababab. This will also belong to L(G). D – Incorrect Given as context free..we will require storage to accept strings produced by this language. Ps.. please correct if my reasoning is not valid. [...]

Answered: What is difference between Flooding and Broadcasting ?

In flooding the switch sends the frame to all because it doesn't know how to reach the destination. In broadcasting the host that created the frame itself addressed the frame to everyone. [...]

Answered: Made Easy Subject Test 2019: Computer Networks - Congestion Control

at start of 36kb it is 2600 only [...]

Answered: Madeeasy test series

1400+20 1400+20 1180+20 so total offset will be 175 +175=350 [...]

Answered: GATE2014-1-13

Think of edges as courses. If an edge is there between two courses as C1->C2, then C1 is prerequisite for C2. [...]

Answered: NIELIT 2019 Feb Scientist D - Section A: 11

If we take four letters from the word CONSIDERATION i.e OSRT then we can form only one word – SORT then C is the correct option. [...]

Answered: NIELIT 2019 Feb Scientist D - Section A: 8

we will reverse the digits of every number and the middle number after reversing will be – 394 So correct answer is (D) [...]

Answered: NIELIT 2017 OCT Scientific Assistant A - Section A: 54

Answer (B) 18 cost price of 45 limbs =50 RS Selling price of limbs =40 RS(20 % loss on Cost price) women purchase 45 limbs of RS 50 means 9 limbs of RS 10 Without profit she sell 18 limbs of 20RS with 20 % profit she sell 18 limbs of 24 Rs [...]

Answered: NIELIT 2017 DEC Scientist B - Section A: 43

Option D. scientists will never fully understand how DNA functions. [...]

Answered: NIELIT 2017 DEC Scientist B - Section A: 22

Option C. human labour has dignity and value. [...]

Answered: NIELIT 2017 DEC Scientist B - Section A: 24

Option A. Poo Zat Poo, Tim $\Rightarrow$ Eat Good Mangoes …...(1) Sim Poo Kit $\Rightarrow$ Purchase Good sweets ……..(2) From (1) and (2) we can clearly say that Poo $\Rightarrow$ Good [...]

%d bloggers like this: