Scribd
Upload
68 views2 pages

Theory of Computation Exam Paper

This document outlines the end-semester examination for the Theory of Computation course at Thapar Institute of Engineering and Technology, detailing the exam date, time, and instructors. It includes a list of questions covering topics such as context-free grammar, deterministic finite automata, Turing machines, and regular expressions, with specific marks allocated to each question. Students are instructed to attempt any five questions and to assume missing data suitably.

Uploaded by

Anant Singla
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
68 views2 pages

Theory of Computation Exam Paper

This document outlines the end-semester examination for the Theory of Computation course at Thapar Institute of Engineering and Technology, detailing the exam date, time, and instructors. It includes a list of questions covering topics such as context-free grammar, deterministic finite automata, Turing machines, and regular expressions, with specific marks allocated to each question. Students are instructed to attempt any five questions and to assume missing data suitably.

Uploaded by

Anant Singla
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Roll Number: ______________________

Thapar Institute of Engineering and Technology, Patiala


Department of Computer Science and Engineering
END-Semester Examination
BE COE & CSE (Third Year) UCS701: Theory of Computation
th
18 May 2024, 2:00 PM Time: 3Hours, Max Marks:40

Instructors: Sunita Garhwal, Nidhi Kalra, Shashank Sheshar, Aditi Sharma, Rohit Ahuja.
Note: Attempt any 5 questions. Attempt all questions (subparts) in sequence at one place. Assume
missing data, if, any, suitably.

Q Questions Marks CO BL
No.
Q1. a) Given the Context-free grammar G: 5 CO2 L3

S  AB
A  AA | AB | a
B  CC
C b
Apply CYK algorithm to determine whether the string
w  aaabb  L(G ) or not? 3 CO1 L3
b) Construct deterministic finite automata for the language:
L = {an | n ≠ 2, n ≠ 6, over Σ = {a}}.
Q2. a) Draw the flowchart for the language L={w a2m b3m wR | w∈ 5 CO2 L4
{a,b}* and wR is the reverse of w , m>0} accepted by the push-
down machine. Construct the transition diagram for the above
designed flowchart. 3 CO2 L4
b) Construct a Context-free grammar over ∑={a,b} for the
language: L={anbm | 0<=2n<=m<=3n}.
Q3. a) Consider the context-free grammar G: 5 CO2 L3

S→ aAa| bBb | ^
A→ C | a
B→ C | b
C→ CDE | ^
D→ A | B | ab
Convert the above grammar into Greibach Normal Form(GNF). L4
b) Prove that L= {aP | P is prime} is not a context-free language 3 CO3
using Pumping Lemma .
Q4. a) Write down the logic for the design of a Turing machine to find 4 CO3 L3
the successor of a positive integer over ∑={0,1}. Design the
Turing Machine for the above designed logic.(Input and Output
should be in binary format).
b) Write down the logic for the design of a Turing machine for the 4 CO3 L4
language L  {a n b 2 n | n  0} . Design the Turing Machine
for the above designed logic.

Q5. a) Design a Post Machine for a language L={a2n b3n c2n | 4 CO4 L3
n>=0}. 4
b) Check for the string w=aabbc , whether the following CO4 L4

[P. T. O.]
grammar is ambiguous or not:

S→ABC | ab
A→aA | B | ^
B→Sb |b| ^
C→cC |bS |^

Q6. a) Design a DFA for L={w|w∈{1,0,2}*, where fourth and third 4 CO1 L4
last symbol in w are 2 and 0 respectively}.
b) Write down regular expression corresponding to the
4 CO1 L4
following finite automaton using Arden’s Theorem.

Bloom's Level wise Marks Course Outcome wise Marks


Distribution Distribution
20
18
18
16
14
21 12 11 11
10
27 8
8
6
4
2
0
Level 3 Level 4 CO1 CO2 CO3 CO4

You might also like