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

78,639 total views, 2 views today

Related

GATE Overflow
Aptitude Overflow

Answered: GATE CSE 2021 Set 2 | Question: 4

As per the question, We should know that in normalised it is not possible to have exponents all 0’s So A and B options get eliminated from here. But Mantissa All 1’s is possible so. The answer should be C Answer:- C [...]

Answered: GATE CSE 2021 Set 2 | Question: 3

So By Compiling everyone noticed that there is an error saying undeclared identifier. This error comes under Semantic Error. So the answer Should be Semantic Error Answer :- C [...]

Answered: GATE CSE 2021 Set 2 | Question: 54

Frame Transmission Time : $T_{fr}= L/B$ = 1000/$10^{6}$ =1ms System generates 1000 frames in 1 second. Now, G is defined as average no of frames generated by the system in one frame transmission time. in 1 second → 1000 frames $\therefore$ in 1 ms → 1 frame Therefore, G= 1 average no of successful transmissions, $S=G*e^{-2G}$ = $1*e^{-2}=$$0.13534$ i.e. 13.534% 13.5% of the frames get successfully transmitted. $\therefore$ Throughput = $\frac{13.534}{100}$$*1000$= 135.34 $\approx 135$ [...]

Answered: GATE CSE 2021 Set 2 | Question: 2

So by following the basics we know A min-heap contains smaller element as there parent. Now as soon as we go down our values start increasing. By observation, we can say that the last level must contain our maximum value. But we have to compare the last level of values. So how many elements we have to compare. SO as we know in heap n/2 elements are there which will be in leaves so we have to compare n/2 elements so COmplexity will be O(N) Answer: C [...]

Answered: GATE CSE 2021 Set 2 | Question: 1

According to the Questions The First statement says there should be at least one edge that must be there in every minimum spanning tree But we Should keep one thing in mind that the edges can be same in weight so in that case if we have a cycle of same weight in our graph we can get more than one minimum spanning tree with different edges of same weight. So that's why 1st statement is false. Now in this statement it is obvious that if all the edges are different than we will definitely get only one minimum spanning tree. Answer… [...]

Answered: Counting of number of Triangles

Total possible triangles = $\binom{16}{3}$ = 560 Now we know that if all points are collinear then the triangle is not possible. So we will simply deduct the cases wherein we are selecting 3 points which are collinear, How many groups of 4 collinear points do we have? 4 horizontal lines + 4 vertical lines + 2 diagonals = 10 So $10*\binom{4}{3}=40$ invalid counts How many groups of 3 collinear points do we have? Only 4. So $4*\binom{3}{3}=4$ invalid counts Therefore the total number of triangles = 560 – (40+4) = 516 [...]

Answered: NIELIT 2019 Feb Scientist C - Section A: 19

Since, Seetha is $7^{th}$ from the left and Leena is $9^{th}$ from the right, when Seetha replace Leena, the position of Seetha from the right = $9.$ As per question, Seetha’s position from the left after interchanging $=11.$ Hence, the no. of girls in the row $$\begin{align}&=\text{(Seetha’s position from the left + Seetha’s position from the right)-1}\\&=(9+11) -1\\&= 20-1\\&= 19\end{align}$$ So, answer is None of the above. [...]

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 [...]

%d bloggers like this: