GBGS SCHEME

USN BCS503

Fifth Semester B.E./B.T'ech. Degree Examination, Dec.2024/Jan.2025

Theory of Computation
Time: 3 hrs. Max. Marks: 100

Note: 1. Answer any FIVEfull questions, choosing ONE fullquestion from each module
2. M: Marks, L: Bloom's level, C: Course outcomes.
Module - MLC
Q.1 Define the following with example 3 L1 CO1
i) Language ii) String ii) Power of an alphabet.
b. Define DFA. Draw a DFA to accepts. 10 L3 CO1
1) The set of all strings that contain a substring aba.
ii) To accept the stings of a's and b's that contain not more than there b's.
iii) L= {wefa. b} :No 2 consecutive characters are same in w}.
Convert the following NFA to DFA. 7 L2 CO1

PP, q} {p}
{r} {r}
{s}
S {s} {s}

OR
Q.2 2. Define the following with example : 3 L1 CO1
i) Alphabet
ii) Reversal of string
iii) Concatenation of Languages.
b Design a DFA for the Language : L3 Coi
L= {w E {0, 1}*:w is a string divisible by 5}.

Define NFA. Obtain an[ NFA which accepts strings consisting of 0 or 10 L2 CO1
more a's , followed by 0 or more b's followed by 0 or more C's. Also
convert it to DFA.

Module -2
Q.3 a Define Regular expression. Write the regular expression for the following 10| L2 CO2
languages :
i) Strings of a's and b's starting with a and ending with b.
ii) Set of strings that consists of alternating 0's and I's.
ii) L = fa bm , (n + m) is even}.
iv) L= (w:/w/mod 3 =0, where we{a, b}*}.

1of 3
 BCSS03

b. Minimize the following finite automatausing Table filling algorithm 10 L2CO2

8a b
A A
B AC
D
A

GE
GF G
HG D
OR
Q.4 a. Construct [ - NFAfor the following Regular express ion: L1 C02
i) (0+ 1)0 1(1 +0) ü) 1(0 + 1) 0 ii) (0 +)011
b. Obtain the Regular expression that denotes the language accepted by6 L3 CO2
Fig. 4(b).

Fig. Q4(b)
o

Using Kleene's theorem.

State the Pumping Lemma for the Regular Languages. And also prove that L1 CO2
the following languages are note regular.
i) L= {0" 1"n s m} ii) L= {0" 1" 2"|n, m> 1}.
Module -3
Q.5 a. Design CFG for the following languages : 10 L3 CO3
i) L= fa"b,n> }
ii) L={a'b ,j=j+k, i>0, k>0}
iii) L= {w//w/ mod 3 > 0 where w e(a) *}
iv) L= {a" b" / m n}
v) Palinderomes over 0 and 1.

b Consider the grammar G with productions. 10 L2 CO3

S’ AbB/A/B A ’ aA/[ : B ’ a B/b B/.
Obtain LMD,RMD and parse tree for the string aaabab..
Is the given grammar ambiguous?
OR
Q.6 a. Define the following with example : L1 CO3
i) Context free grammar ii) Left most Derivation
ii) Parse tree iv) Ambiguous grammar.

b. Design PDA for the language : 10 L3 CO3

L= fa' b c/i+k=j,i>0,k>0} and show the moves made by the PDA
for the string aabbbc.

2 of3
BH
CO2
BCS 03
BCSS03

C. Convert the following CFG's to PDA 6L2 Co

S aA ; A a ABC /bB/a B ’b:Cc. Wer
7 tra.
Module -4
Q.7 Define CNF.Convert the following CFG to CNF 10 L2 C04
E’E+ T/T
T-T*F/F
F ’ (E)/1
| - la /Ib/a/b.
cpt
b. Show that L = (0" 1"2n/n>1 is no context free. 4 L2 C04
Ver.
Prove that the family of context free languages is closed under union and LIC04
concatenation. ich
OR Fin.
Q.8 a. Define Greibach Normal Form. Convert the following CFG to GNF. 6 L2 C04 he
S ’ AB A -’ aA bB/b B ’b. DW

b Consider the following CFG: 10 L3 CO4

S- ABC / BaB
A aA /BaC/ aaa
B - bBb /a/ D
C ’CA /AC d
D’
le
re
i) What are useless symbols? ior
ii) Eliminate &- productions, Unit productions and useless symbols from Ex
the grammar. fo.
Prove that the following languages are not context free. 4 L2 C03
i) L=(ai / i is prime} i) L= {a"' /n2 1}.
Module -5
Q.9 Define aturing machine and explain with neat diagram, the working of a 6 LI CO4
basic turing machine.
b. Design a Turing machine to accept the language, L = {a' b" c In 1}. 14 L4 C04
Draw the transition diagram and show the moves for the string aabbcc.
OR
).10 a. Design a Turing machine to accept palindrome over {a, b} and draw the 12 L4 COS
transition diagram.
b Write a short notes on 8 L1 COS
i) Recursively Enumerable Language.
i) Multitape Turing Machine.

3of 3
HE
 HCS503
ModelQuestion Paper-1with effect from 2022-23 (CBCS Scheme)

Fifth Semester B.E. Degree Examination

THEORY OF COMPUTATION
Max. Marks: 100
TIME: 03 Hours

Note: o1. Answer any FIVE full questions, choosing at least ONE question from cach MODULE.
02. Draw transition diagrams wherever nccessary.
*Bloom's COs
Module -1 Taxonomy Marks
Level
L3 CO1
Q01, Obtain a DFA to accept strings of a's and b's having odd number
of a's and even number of b's.
L3 COI
b Draw a DFAto accept decimal strings divisible by 3. COI 9
L2
Dgfine the following terms with example:
Aiplhabet i) Power of Alphabet ii) Languages
OR
Obtain an (- NFAwhich accepts strings consisting of zero or morc a's L3 CO1
Q.02
followed by zero or more b's followed by zero or morc c's. M
L2 CoI 6
BDefine Deterministic Finite Automata. Explain the two preferred
notations for describing the Transition Function with an example. CO1
ctObtain aDFA for the following NFA using lazy evaluation method. L3

start 0,1 0,1

42) 4ccept

Module-2
). 03 a)| List applications of RE. What are the notations used in UNIX Operation L2 C02
system? List few Regular expressions with its UNIX notations.
b Obtain an E-NFA forthe Regular Expression (a+b)* bb (a+b)" L3 CO2 9
L3 CO2
Find the minimized DFA of the following.

B A
B

OR
).04a/ Define Pumping Lemma. Prove that below 1anguage is not a regular L2 CO2 5

I,anguagC. L-{a' b|i>j)

bDevclop Regular expressions for thc following Languagcs on E = { a, b} L3 CO2 6
i) Accept strings of a'sand b's whose fifth symbol from the right end is
a

ii)Accept strings of a's and b's containing not more than 3 a's.
1Find Regular language acccptcd by the following FA by L3 CO2
eliminating states?

Page 01 of 02
 (4)

Module-3 L3 CO3
Techniques for reducing
grammar? Explain the
Q. 05 What is ambiguous suitable examples. CO3
ambiguity in the gramnur with
L3
ambiguous by taking the string aab.
b Show that the following grammar is CO3
S’ aS aSbSc L3
for the following Languagcs.
Design the Context Free Grammar threg a's
strings with no more than
i) To accept the set of all
when - (a, b}. number ofa's and b's
ii) To accept the set of' strings with any
with at lcast one a.
OR L3 CO3
corresponding PDA
). 06 For the below Grammar obtain the B’ bA |b, C’a
S’ aABC, A’ aB|a, L3 CO3

b LetG bethe Grammar

S ’ aB|bA
A ’aaS|bAA
B’ b| bS aBB
For the string aabbabab, find
Derivation ii) Rightmost Derivation
i) Derivation Trec ii) Leftmost CO3
Define CFG. Design CFG for the following Languages:
of set of all non-palindromes over E ={a,b)
i) Consisting
i) L={0"1"*1 | n20}
of w}
iii) L= { wew : wcfa,b}*, w* is the reverse
Module-4 6
L2
examples:
Q. 07 a) Define the following with suitable (i) Chomsky Normal Forms
(i) Inherently ambiguous Language
(ii) Greibach Normal Form L3 CO4 6
productions from the
Remove all the c-productions and Unit
grammar:
S> aA |aBB A’ aAA| B’ bB|bbC C ’B L3 CO4
Define GNF.Convert the following grammar into GNF.
S’ AB1l |0 A’ 00A | B B’ 1A1
OR 6
L3 CO4
Q. 08 a Write the LMD, RMD and Parse tree for the string: +*-xyxy
using the grammar E ’ +EE| *EE| -EE | x| y
L3 CO4
h Obtain the following grammar in CNF:
S’ ASB | A ’ aAS a B’ SbS|A |bb
L3 CO4
C Definc CNF. Convert the following grammar into CNF,
S’ OA |IB A’ 0AA|1S1 B’ 1BB|0S |0
Module-5 6
L2 COS
Q. 09 Define Turing Machine. With a ncat Block diagram, explain the
the working of basic Turing Machine. CO5
a Turing Machine to accept all set of palindrome over
L3
b Design
fa,b}*. Draw the transition table and also transition diagram.
Show the sequence of IDs for the string: "'ababa" L2 COS 8
C Write a short note on:
a) Multitape Turing Machine
b) Nondeterministic Turing Machinc
OR
6
Briefly explain The Techniques for Turing Machine construction. Also L2 COS
0. 10
write applications of"Turing Machine. L3 COS
|b Design a Turing Machine to accept the Language:

Page 02 of 02
 sCSS03
L=fa'b' n > . Draw the transition diagram and show the moves made
by TM or the string: "aaaabbbb.
COS
Design a Turing Machine to accept strings formed on {0,1* and
ending wvith 000. Write transition diagram and sequence of IDs for
W= 101000

"Bloom's Taxonomy Level: Indicate as LI, L2, L3, L4, ete. It is also desirable to indicate the COs and
POs to be
attained by every bit of questions.

Page 03 of 02
 BCSAI3
Model Question Paper with effect from 2024-25 (CBCS Seheme)
USN

Fifth Semester B.E. Degree Examination

Tbeory of Computation
TIME: 03 Hours Mas. Marks: s9
Note: 01. Answer any FIVE full questions, choosing at least ONE question frorn cach MODULE
Module 1 Marks
Q.01 Design DFA to accept strings of a's and b's where language L3
L={|W|mod5=|W|mod4}
Design DFAtoAccept stings of 0'sand l's L*{ starting with 01 or
starting with 10)
b Define NFA. L3
Convert the following NFA to its equivalent DFA.
0,1

1 0,1
42

OR
Q.02 L3 10

Find E-Closure of all the states

Convert following NFA to DFA
Define Alphabets Strings and Languages. L2 10
b Construct aDFA to accept strings of0's and l's starting with at least
two 0's and ending with at least two l's.
Module-2
Define Regular Expressions. L3
Q. 03
Obtain RE to accept strings of a's and b's whose second symbol from
the right end is a
Obtain RE to accept words with two or more letters but beginning and
ending with the same letter where (a, b} are inputs.
iv. Obtain NFA which accepts strings ofa's and b's starting with the
string ab
V. Obtain NFA for the Regular Expression (atb)*aa{atb)*

bMinimize the following DFA using Table filling Algorithm. L3 10

A B A
B A
C D
*D D A
E D
F G E
Page 01 ef 62
 BCSS03

G G

H G D
OR 10
L2
Q04 a State and prove pumping lemma Theorem not regular
Show that,L= {WW* | WE{a,b) *}} is
L3 10
b Show that regular languages are closed under
1. Union,concatenation and Kleens star
Intersection and Difference
Module-3
10
shown and get the L3
0. 05 a i. Obtain the unambiguous grammar for the grammar
derivation for the expression (a+b)*(a-b).
E’ E+E| E-E
E’ E*E| E/E
E’ (E)|I
I’ ab<c
Consider the following grammar
S’ AbB
A ’aA |¬
B> aB | bB |¬ "aaabab
Give LMD and RMD and Parse tree for the string

L3 10
{WCW*|We(a+b)*}
b a) Design a PDAfor accepting a palindrome L(M) =
where W* is reverse of W and show ID for the string aab"
OR
L2 10
0.06 a Construct CFG for the following languages
i) L={0n1m | n>-0,m>=0}
ii) L= {ww* | WE {a,b) *}}
of"101"}
iii) L= { ww¬ {0,1 }* with atleast one occurance
number of a's and b's }
iv)L= {strings of a's and b's with equal strings 0's and 1's haing a
V) Obtain a grammar to generate a language of
substring 000 L3 10
b|Define with example
Grammar
Derivation
iii. Leftmost and Rightmost derivation
IV. Ambiguous grammar
V. Parse tree
Module-4
L3 10
). 07 a S ’al aA|B
A ’ aBB&
B ’ Aa | b
Convert the above grammar to CNF L3 10
b S’ Sa Sbl aA|B
A ’Abl aBB|ab
B’ Balbb
Eliminate left recursion.

Page 01 of 02
 BCS401

OR
L3 10
Q 08 a
A BC
B CAa
B AB| b
Convert the above grammar to GNF L3 10
b Show that CFLis not closed under union, Concatenation, star and
omplimentation
Module-5
Explain The Church-Turing machine with ncat a d1agram L2 10
0. 09 a
i. Expain Multiple TM witha ncat diagram
bDetinc Turing Machine (TM). Design a TM lor language L-{O" 1|n>=0} L3 10
Showthat the string 001| is accepted
OR
Q 10a Definc Turing Machinc (TM) Design a TM for language L-{1" 2" 3" n>=l} L4 12
Show that the string 1222333 is accepted
bDemonstrate the model ofLincar bound automata(LBA) with ncat dagram L3 08

Page 02 of 02
 Model Question Paper-1 with effect BCSS03
USN from 2022-23 (CBCS Scheme)

Fifth Semester B.E. Degree

THEORY OF COMPUTATION Examination
TIME: 03 Hours
Max, Marks: 100
Note:
01. Answer any FIVE full questions,
02. Draw transition diagrams choosing at least ONE question from each
wherever necessary. MODULE.

Module -1 *Bloom's COs

Taxonomy Marks
Q.01 Obtain a DFA to accept strings of a's and Level
of a's and even number ofb's. b's having odd number L3 COI
b Draw a DFA to accept decimal strings
divisible by 3.
Define the following terms with example: L3 COI 6
l
i) Alphabet ii) Power of Alphabet L2 COI
ii) Languages
OR
Q.02 a
Obtain an ¬- NFA which accepts strings
followed by zero or moreb's followed by consisting of zero or more a's
zero or more c's.
L3 CO1 5
b Define Deterministic Finite Automata. Explain the
notations for describing the Transition Function with an two preferred L2 COI 6
C Obtain a DFA for the following NFA using lazy evaluation example.
method. L3 COI
0 1
start 0,1 0,1
92) accept
Module-2
Q. 03 List applications of RE. What are the notations used in UNIX Operation L2 CO2
system? List few Regular expressions with its UNIX notations.
bObtain an ¬-NFA for the Regular Expression (a+b)* bb (a+b)* L3 CO2 6
Find the minimized DFA of the following. L3 CO2 9

’ A
B A
C B
*D A
D
F G E

H GD
G
OR
Q.04 Define Pumping Lemma. Prove that below language is not a regular L2 C02
Language. L={a b|i>jL
Develop Regular expressions for the following Languages on E=a, b) L3 CO2 6
i)Accept strings ofa's and b's whose fifth symbol from the right end is
ii) Accept strings of a's and b's containing not morethan 3 a's.
Find Regular language accepted by the following FA by L3 CO2 9

eliminating states?

Page 01 of 02
 BCSS03

42)

Module-3
a What is ambiguous grammar? Explain the Techniques for reducing L3 CO3
Q. 05
ambiguity in the grammar with suitable examples.
L3 CO3 6
Show that the following grammar is ambiguous by taking the string aab.
S ’ aS | aSbS ¬ 9
L3 CO3
C Design the Context Free Grammar for the following Languages.
i) To accept the set of all strings with no more than three a's
when E= {a, b}.
ii) To accept the set of strings with any number of a's and b's
with at least one a.
OR
L3 CO3
Q. 06 For the below Grammar obtain the corresponding PDA
S’ aABC, A ’> aB |a, B’ bA |b, C’a
L3 CO3 6
b Let G be the Grammar
S’ aB | bA
A ’alaS | bAA
B ’b|bS | aBB
For the string aabbabab, find
i)Derivation Tree i) Leftmost Derivation ii) Rightmost Derivation L3 CO3
Define CFG. Design CFG for the following Languages:
i) Consisting of set of allnon-palindromes over L={a,b}
ii) L={0°1**! |n0}
ii)L = {wew : wefa,b}*, w is the reverse of w}
Module-4
L2 CO4 6
Q.07 a Define the following with suitable examples:
() Inherently ambiguous Language (ii) Chomsky Normal Forms
(iil)Greibach Normal Form 6
b Remove all the ¬-productions and Unit productions from the L3 CO4
grammar:
S’ aAlaBB A ’ aAA ¬ B’ bB | bbC C ’B
Define GNF. Convert the following grammar into GNF. L3 CO4 8

S> ABI |0 A’ 00A |B B’ IAI

OR
L3 CO4 6
Q. 08 Write the LMD, RMD and Parse tree for the string: +*-Xyxy
using the grammar E ’ +EE|*EE| -EE | X|y 6
Obtain the following grammar in CNF: L3 CO4
b
S’ ASB |¬ A ’ aAS | a B’ SbS | A |bb
Define CNF. Convert the following grammar into CNF. L3 CO4 8
S’ 0A | IB A’ 0AA | 1S|1 B’ IBB |0S |0
Module-5
L2 COS 6
Q. 09 Define Turing Machine. With a neat Block diagram, explain the
the working of basic Turing Machine. 6
Design a Turing Machine to accept all set of palindrome over
L3 COS

fa,b}*. Draw the transition table and also transition diagram.

Show the sequence of IDs for the string: "ababa"
L2 CO5
Write a short note on:
a) Multitape Turing Machine
b)Nondeterministic Turing Machine
OR
COS
Briefly explain The Techniques for Turing Machine construction. Also
L2
Q. 10
write applications of Turing Machine.
L3 COS 6
|b Design a Turing Machine to accept the Language:

Page 02 of 02
 BCS503
L={ab | n 2l}. Draw the transition diagram and show the moves made
by TM for the string: "aaaabbbb".
Design a Turing Machine to accept strings formed on {0,1}* and L3 COS
ending with 000. Write transition diagram and sequence of IDs for
w= 101000

*Bloom's Taxonomy Level: Indicate as LI, L2,L3, L4, etc. It is also desirable to indicate the cOs and POs to be
attained by every bit of questions.

Page 03 of 02
KryCeptis
CIE-Test 1
Date: 1610/224
Tiae:9J0-11:10
Sobjeet Theery of Camputati Mas Marksc S4
Sabject Cde: BCNa
faractionAer ans fult quosiens, selectig ONE questlon from eack part
Q.Na Question Marks RITCD
1 4
Give defintion far Determinitic Finite Autoata (LDEA) with an example

Lerulcating t For e iollowing latgges, construst he DFA,

L-wE (, b)": triga statting wih ab)
it LwE (0. 1)* strings cotaining substrig 0l}
E L set of al strag ef Segrls over
OR
b)
32-6
COr

Educkian
and Cive definition foe Non teminiwic Fnte Autostuats(NEA) witth an cxatngle
&Construct the NFAlor
LLc tb)*srng that starte with aand ends with b)
RL(wE (ab|w"a or bb}
COE

lL L(wE [ b) strings startitg with ab)

Owlity
Igariny Detiaelhe folowing tess with at esanple fur esch: (i) Alphabet () Sang
)) Langeage iv) Concatenation ofstuing
Castruct the DFA la tse langge tat aceept even umber uf 0'and even
anber ofi't Aha wie extended ransitions for bah accgting and rejecting
CO1

Prefsionale
ry
String
OR
List aut te diffeences bet wcen DEA anæ NFA
Canserut the NFA Tor the language L. IwE b) waba ox jweveriland
COI

Technlogy also urite exteaded transitions for both accopting and roecting string
Coevet the folawing NEALO DEA using subiet costruction method. 2xS10

inferavks
Bidng OR
.r)

Via :
 Cvete engNIADN

CO1

0-6-0-0
Cav he lollowutge-Aa DPA

lac ting
Key
CO

Educatin
end

Dene Reglar Exgre (RE) Ltthe nules to firma rgular espresion

Quatiry WTaroular expresin to descrie esch ofthe following langgages
L e , I wcnding wih string 011)
CO2

Imting Lwt0, 1een)

OR
Build Auoerata fhom a given regular expressions>
215-10 L3 CO2

Frmieans
bry Revised Boom's Taxanomy: L1 Rernember, 2.Understand, 3.Apply, L4 Analye, L5-Evaluata, LS-Crete
QUIZ-I vtun
ENSTRUCTION- Each question carries ae mark
Techsalg Lbbbabablab )
101K10-101

Isfartion 3
is denoted uang
The laiguage is the identity for COncateation of languages

abj #ah* is this trus or falbuet

(c) L. (6)None of these

Belding The lungage acceptad by FA is

la) Regula
Concatenatiun of Rih
(b) Contexi Free
sutputs: a)R
Langtsage.
b)
(C) Traasition
c)RO
(d) None of these

7ANFA ast inale tranuition to more tan one state on reading a input charcter. Stale TR¯E OH
Visle : FALSE

The RE t string consisting cf atieast one ais

(c)a (d) a'
9.Ths striog Wmatcha wth RE-( U6(aUb)
te)Wheven tb) W-odd () Waha (9Wabb
10KS-b1. LI (ab, shb) and li aba, n&) theo whhat islIULE9