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

77,647 total views, 25 views today

Related

GATE Overflow
Aptitude Overflow

Answered: GATE2015-2-25

Just think in terms of set-associative cache mapping used in cache organization. Number of pages = (Total Virtual address space) / (Page size) =(2^40) / (2^13) = (2)^27 No. of bits required to uniquely identify a page is 27 Assume page as a block for simplicity Like in the cache we take each main memory block and map it to a block in the cache Number of blocks = 2^27, Number of bits to uniquely identify a block =27 So here we are using 4… [...]

Answered: GATE2017-2-54

0 is the right answer [...]

Answered: # CN TCP connection establishment doubt about MSS

see the flow control means that Sender’s rate should be equal to reciever’s rate. This implies that Sender’s rate= min(sender’s window size, reciever window size). So here sender choses to send with 600B [...]

Answered: fast retransmit and fast recovery mechanism

according to me its 17,23 i.e. option C [...]

Answered: Computer network tcp congestion control

the congestion window size at the end of 14th RTT is 11 MSS [...]

Answered: CMI2020-A: 1

If we do by option Elimination, then I think D is the correct answer as 101 as a contiiguous sub word will require at least 4 states. All the other 3 options are possible within 3 states. q0___1____q1_____0____q2____1____q3 you can complete the min DFA, but I am sure, D is the correct answer. [...]

Answered: NIELIT 2017 DEC Scientific Assistant A - Section A: 6

All of the girls agree that the first three numbers are 995. Three of them agree that the fourth number is 9. Three agree that the fifth number is 2. Three agree that the sixth number is 6; three others agree that the seventh number is also 6. "Option A" is the best choice because it is made up of the numbers that most of the girls agree they saw. [...]

Answered: NIELIT 2016 MAR Scientist D: 8

Answered: NIELIT 2016 MAR Scientist D: 8

Correct Answer: (D) Explanation: This game introduces the idea of reciprocal causation. For example, the constraint that says “If A, then B, and if B, then A” should be transcribed in one of the following two ways, based on the configurations of the other variables in the diagram: You will run into reciprocal causation in the final constraint of this logic game. Here are the final diagrams that you should create: Notice how the reciprocal causation constraints are diagrammed. Be aware of the implications of these constraints. For instance, if $B$ is not sent (diagram B), then $A$ cannot… [...]

Answered: NIELIT 2016 MAR Scientist D: 7

Answered: NIELIT 2016 MAR Scientist D: 7

Correct Answer: (D) Explanation: This game introduces the idea of reciprocal causation. For example, the constraint that says “If A, then B, and if B, then A” should be transcribed in one of the following two ways, based on the configurations of the other variables in the diagram: You will run into reciprocal causation in the final constraint of this logic game. Here are the final diagrams that you should create: Notice how the reciprocal causation constraints are diagrammed. Be aware of the implications of these constraints. For instance, if $B$ is not sent (diagram B), then $A$ cannot… [...]

Answered: NIELIT 2016 MAR Scientist D: 6

Answered: NIELIT 2016 MAR Scientist D: 6

Correct Answer: (A) Explanation: This game introduces the idea of reciprocal causation. For example, the constraint that says “If $A$, then $B$, and if $B$, then $A$” should be transcribed in one of the following two ways, based on the configurations of the other variables in the diagram: You will run into reciprocal causation in the final constraint of this logic game. Here are the final diagrams that you should create: Notice how the reciprocal causation constraints are diagrammed. Be aware of the implications of these constraints. For instance, if $B$ is not sent (diagram B), then $A$ cannot be sent… [...]

Answered: NIELIT 2016 MAR Scientist D: 33

The answer is (C). three [...]

Answered: NIELIT 2016 MAR Scientist D: 32

The answer is (B). $K$ and $L$ [...]

%d bloggers like this: