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

80,925 total views, 43 views today

Related

GATE Overflow
Aptitude Overflow

Answered: CMI-2019-DataScience-A: 15

A, B, C are true [...]

Answered: CMI-2019-DataScience-A: 5

$p(x) =(5x^2+6x+1)(x+1)(2x+3)=(5x+1)(x+1)^2(2x+3) $ And $q(x) =(5x^2-9x-2)(2x^2+5x+3) \\= (5x^2-10x+x-2)(2x^2+2x+3x+3)= (5x+1)(x-2)(2x+3)(x+1) $ $\therefore$ Common divisors are A.$\{ 2x+3, x+1, 5x+1\}$ [...]

Answered: CMI-2018-DataScience-A: 13

Assume there are $a,b$ and $c$ numbers of songs in the first, second and third playlist respectively.. Therefore $a+b+c=n$. The number we can choose one song from each playlist is $abc$. We have to find the maximum value of $abc$ corresponding to the condition $a+b+c=n$. Let $L=abc-\lambda(a+b+c)$ Therefore $\frac{\partial L}{\partial a}=bc-\lambda, \frac{\partial L}{\partial b}=ac-\lambda, \frac{\partial L}{\partial c}=ab-\lambda$ For $\frac{\partial L}{\partial a}=\frac{\partial L}{\partial b}=\frac{\partial L}{\partial c}=0$ we get $ab=bc=cd=\lambda$ and $a=b=c$ Therefore $a^2b^2c^2=\lambda^3 \Rightarrow a^6=\lambda^3\Rightarrow a=\sqrt{\lambda}=b=c$ By the given condition $a+b+c=n\Rightarrow 3\sqrt{\lambda}=n\Rightarrow \sqrt{\lambda}=\frac{n}{3}$ Therefore the maximum value of $abc$ is $({\sqrt{\lambda}})^3=\frac{n^3}{27}$ Therefore the number of ways of choosing three songs consisting of one song… [...]

Answered: UGCNET-June2014-II: 21

The given graph is Bipartite, 3-Regular graph on 8 vertices. Also the given graph in the question is Hypercube graph on 8 vertices i.e. the given graph is $Q_3.$ Option C is $Q_3$, So option C is correct answer. We can note that Graph in Option A,B,D have at least one vertex of degree 4, but in the given graph every vertex has degree 3, So, given graph is Not isomorphic to graph in option A,B,D. [...]

Answered: CMI2016-B-7ai

$M(101)$, Here $n=101$ which is grater then $100$ comes under $n>100$ which return $n-10$. so value of $M(101) =101-10= 91$ correct answer is $91$. [...]

Answered: CMI-2018-DataScience-A: 16

By A.M-G.M inequality we know that $\frac{a_1+a_2+\dots +a_n}{n}\geq \sqrt[n]{a_1 a_2 \dots a_n}$ Therefore we have $\frac{a+b+c+d}{4}> \sqrt[4]{abcd}$ and $\frac{u+v+w+x}{4}> \sqrt[4]{uvwx}$. [ Note: since a,b,c,d are not all equal therefore equality does not hold in this case] Multiplying these inequalities $(a+b+c+d)(u+v+w+x)>16\sqrt[4]{abcduvwx}=16$ Therefore we got option A is true [...]

Answered: TIme Compound Interest question no. 18

Let’s divide the problem in terms of cash inflows and outflows. Profit earned=Inflows-Outflows Initial Inflow=25,00,000 After 1st year:- Inflow=20%of25,00,000=5,00,000 Outflow=5,00,000(As he paid off this amount of loan at the end of 1st year) Net gain=Inflow-Outflow=0 Loan amount at the end of 1st year= 25,00,000(1.12)=28,00,000 Amount after repayment of 5,00,000=23,00,000 As CI is calculated annually, the new amount will be calculated on the outstanding amount after the end of 1st year. Amount to be paid off at the end of 2nd year=23,00,000(1.12)=2576000 After 2nd year:- Inflow=20% of 25,00,000-5,00,000 Outflow=2576000 Overall gain=Initial Inflow+Inflow in 2 yrs – outflow at the end… [...]

Answered: Logical Sequence of words

4.Infancy [...]

Answered: CAT2019-1: 37

D cannot be 7. G,K,J can be (4,7,3) in this case D=6 or (8,3,7) where D can be 6 again, (7,4,6) where D can be 3. Please refer to my points 5&6 in the below link for detailed reasoning of what values of G,K,J can be. https://aptitude.gateoverflow.in/5476/cat2019-1-35?show=7805#a7805 [...]

Answered: CAT2019-1: 36

B=9 B is the second target for decoding, B+1=1, this is only possible if 9+1=10 and another 1 carried in from previous digit addition is included making it 9+1+1=11. So, B=9. Please refer to my answer in the below link for a detailed approach. https://aptitude.gateoverflow.in/5476/cat2019-1-35?show=7805#a7805 [...]

Answered: CAT2019-1: 35

A=1 I’ll try to reason out how I decoded all the encodings in this question and will paste the reference link in the subsequent questions. B(9) H(5) A(1) A(1) G F(0) + A(1) H(5) J F(0) K F(0) A(1) A(1) F(0) G C(2) A(1) F(0) A good place to start is to figure out A & F. It’s given that F+F=F, this is only possible when F=0. A is an overflow digit of 5 digit addition for 2 numbers, this implies that A can only be 1. Max possible result of 2 digit addition including Carry-In from the previous… [...]

Answered: NIELIT 2019 Feb Scientist D - Section D: 21

Option (C) Let x litres of hydrogen peroxide solution should be added, then 0.03x + (0.3)(6) = 0.12(x + 6) x = 9.25 $\approx$ 9 litres. [...]

%d bloggers like this: