Anna University CS8501-Theory of Computation For Computer Science and Engineering November/December 2019

Anna University Old Question Paper 

Question Paper Code: 90159

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2019

Fifth Semester 

Computer Science and Engineering      

CS8501-Theory of Computation

(Regulation 2017)

Time: Three Hours

Maximum: 100 Marks

Attachments and PDF Link:  NA

Scanned Copies:

Anna University CS6503 - Theory of Computation For Computer Science and Engineering November/December 2019

 Anna University Old Question Paper 

Question Paper Code: 91403

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2019

Fifth / Eighth Semester 

Computer Science and Engineering  (Common to Information Technology)

CS6503 - Theory of Computation

(Regulation 2013)

Time: Three Hours

Maximum: 100 Marks

Attachments and PDF Link:  NA

Scanned Copies:

      

Anna University CS 2303/CS 53/CS 1303/10144 CS 504 – Theory of Computation For Computer Science and Engineering November/December 2020

Anna University Old Question Paper 

Question Paper Code: X 60383

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2020

Fifth Semester 

Computer Science and Engineering    

CS 2303/CS 53/CS 1303/10144 CS 504 – Theory of Computation

(Regulation 2008/2010)

Time: Three Hours

Maximum: 100 Marks

Attachments and PDF Link: Click Here to download Anna University CS 2303/CS 53/CS 1303/10144 CS 504 – Theory of Computation For Computer Science and Engineering November/December 2020

Scanned Copies:

Alagappa University M.Sc.,(CS &IT)- Elective – THEORY OF COMPUTATION APRIL 2019 Question Paper

Alagappa University Old Question Paper / Previous Years Question Paper

M.Sc. DEGREE EXAMINATION, APRIL 2019

Sub. Code 7MCI2E3

Second Semester    

Computer Science and Information Technology

Elective – THEORY OF COMPUTATION

(CBCS – 2017 onwards)

Time : 3 Hours Maximum : 75 Marks

Attachment Type: PDF and Images

PDF Download: Click Here to Download Alagappa University M.Sc.,(CS &IT)- Elective – THEORY OF COMPUTATION APRIL 2019 Question Paper

Question Paper Scanned Images Download: 

B.Tech Information Technology Theory of computation 2017 Question paper Deemed university

1. Draw Chomsky Hierarchy with grammar, language and automata used.
2. Give description of automata theory.
3. Prove by Mathematical induction 1 + 3 + 5 + 7 + ... + 2n-1 = n2
4. Determine string acceptability of 01100 using transition function for below automata. Draw Transition table.
5. Define alphabet, string, language, grammar. Define Pigeon hole principle.

Section B
(Long Answer Type) 2 questions of 20 marks each (any 1)20
1. Prove by Mathematical induction 12+22+32+42+………+n2 = n(n+1)(2n+1)/6
2. Construct a DFA equivalent to the NFA given below: 

Annamalai University THEORY OF COMPUTATION End Semester Examination November/December 2010 Question paper

University: Annamalai  University

Course: THEORY OF COMPUTATION

Subject : THEORY OF COMPUTATION

Year of  Question Paper : 2010

Reg. No. ________                                                                                                                                                      

Karunya University

(Karunya Institute of Technology and Sciences)

(Declared as Deemed to be University under Sec.3 of the UGC Act, 1956)

End Semester Examination – November/December 2010   

Subject Title:THEORY OF COMPUTATION                                                                       
Time: 3 hours

Subject Code:09CS301                                                                                                          
Maximum Marks: 100           

                                                                                                                                                                                                                                               

Answer ALL questions (5 x 20 = 100 Marks)

1.         Compulsory:

Find a deterministic acceptor equivalent to

where is given as follows (see Table).

States/∑	a	b
àq0	q0, q1	q­2
q1	q0	q­1­
	--	q0, q1

2.    a.  Give a regular expression for representing the set L of strings in which every 0 is    immediately followed by at least two 1’s.                                                                                                                (10)

b.    Prove that the regular expression  also describes the same set of strings.                                                                                                                                                                                               (10)

(OR)

3.         Construct an FA equivalent to the regular expression

                                  (0 + 1)*(00 + 11)( 0  + 1)^*

4.         If G is the grammar S à SbS|a, show that G is ambiguous.

(OR)

5.         Show that L = {a^p|p is a prime} is not a context-free language.

6.         Consider the following productions:

                   

For the string aaabbabbba, find the

a.       Leftmost derivation,

b.      Rightmost derivation, and

c.       Parse tree.

(OR)

7.         Show that the grammar S à a|abSb|aAb, A à bS|aAAb is ambiguous. 

8.    Let where P consists of S à aAB, S à bBA, A à bS, A à bS,

A àa, BàaS, B à b.

For the grammar mentioned above, construct a deterministic pda accepting L(G) and a leftmost derivation of abbab.

(OR)

9.         Design a Turing machine M to recognize the language {1ⁿ2ⁿ3ⁿ | n ≥ 1}..