Scribd
Upload
317 views2 pages

UCS701 Theory of Computation MST

This document contains a exam paper for the Theory of Computation course. It includes 7 questions testing various concepts related to formal languages and automata theory. The questions cover topics like regular expressions, finite automata construction, regular grammars, pumping lemma, and complement/intersection of regular languages. Students are instructed to attempt any 5 of the questions, which involve tasks like converting between representations, constructing automata, proving language properties, and minimizing deterministic finite automata.

Uploaded by

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

UCS701 Theory of Computation MST

This document contains a exam paper for the Theory of Computation course. It includes 7 questions testing various concepts related to formal languages and automata theory. The questions cover topics like regular expressions, finite automata construction, regular grammars, pumping lemma, and complement/intersection of regular languages. Students are instructed to attempt any 5 of the questions, which involve tasks like converting between representations, constructing automata, proving language properties, and minimizing deterministic finite automata.

Uploaded by

KSHITIJ CHAUDHARY
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, 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

B E- COE, CSE (VI Semester ) MST Course Code: UCS701


Course Name: Theory of Computation
April 5, 2022 11:00
Time: 2 Hours, M. Marks: 35 Name Of Faculty: Sunita Garhwal,
Chinmaya Panigrahy, Avadh Kishor,
Gaurav Pareek, Shashank Sheshar,
Nitigya Sambyal

Note: Attempt any five questions with proper justification. Assume missing data, if any,
suitably. All questions carry equal weightage.

Q.1(a) Using Thompson’s construction, convert the regular expression r=(1+01)*


into non-deterministic finite automaton. (3)
Q1(b) Design a non-deterministic finite automaton for the language that will (4)
accept all string ending with abb over {a, b}. Convert the NFA into DFA
using subset construction. You are not supposed to apply Thompson’ s
construction.
Q2(a) Construct a Moore machine that will count the number of occurrences of (4)
011 in a binary string. Convert it into equivalent Mealy machine.
Q2(b) Write down regular grammar for the language over ∑={0,1 } that consists
of all strings of even length and every odd position contains 1.
(3)
Q3 (a) Given language L=(ab+ba+c) . Write down all strings of length 3 in L
* *
(2)

Q3(b) Prove that regular languages are closed under intersection. (3)

Q3(c) Write down regular grammar for L=a(aa|bb)* (2)

Q4(a) Consider the language L=¿ {an b cm |n , m≥ 0 }. (3)


If language is regular then design regular expression and Deterministic
finite automata for language L.
If language is non-regular then prove it using Pumping Lemma.
Q4(b) Construct the minimal deterministic finite automaton and write regular (4)
grammar for the language L=(111+11111)*

Q5(a) Construct a deterministic finite automaton over ∑={a ,b } that will accept all (4)
strings such that number of a’s is divisible by two and number of b’s is
divisible by three.
Q5(b) Minimize the following DFA (Consider A as initial and C as final state) (3)

Q6(a) Write down regular expression corresponding to following finite (4)


automaton using Arden’s Theorem.

Q6(b) (3)
Using Pumping Lemma, prove that L={(ab)nak | n>k, k≥0} is not a regular
language.

Q7 Consider the finite state machine M.

Q7(a) Write down regular expression corresponding to the finite state machine. (2)
Q7(b) Construct a finite state machine that will represent L ' where L represent (2)
the language represented by the language and L ' represents the
complement of L .
Q7(C) Write down regular expression for the language L ' . (3)

***********End of Paper***************

You might also like