BCS503 Model Question Paper Solution Theory of Computation

BCS503 Model Question Paper Solution Theory of Computation

1. BCS503

Model Question Paper wih effet from 202428 (CBCS Scheme)
ath Semester IE, Degree Examination
They of Compatation
TIMES 08 Hours Mos, Marks: 10
Note. Answer any FIVE fl questions, hosing al east ONE question fom each MO!

Module ci Oey

15

{Design DE to accep strings of a's andl B's where lngiage
1 N mess] Vino

2 DEN TE ACT Mings oF O's and Vs Le {
in 1)

{Convert he following

siting with OL or

FA tits equivalen DPA.

04

dEl
ec

OR
QUE _— um
| a
LO
| Se
D ve m,
&
lene ini M es ates ee
Find E:Closure ofall the states
‘Convert folowing NFA to DEA
1. Dati Aphabes Stings nd Languages BY pw
bh i Construct a DEA to accept tengo sand ' starting with at east
A do D and ending witha est 0 1%.
5 “Module
[Efe] 7 Define Regular Expressions. om
ii. Ola RE to accept strings of a's and b's whose second symbol fon}
theright end isa
fii, Obain RE to accep words with wo oF more lees but beginning and
ending wit th smelter wher a,b) ae input.
¿2 Oliain NEA which accepts sings ofa and Ys starting with the
string ab
‘Obtain NEA forthe Regular Expression ai ata
k E Minimize the lowing DFA using Table ling Algo Gm
ap
Br tea
fac
Ce RES
DOM IN
Ejofr
Fee

Der

2. BESS03

a FIG i
| mu (on
AS a
JO TETE Sat pm Tere
GOTT VOTE a mr Er
Faucon Tr |
| TL nenes am Roch dd
[Ta |
NESSTST 3 Ova migas gar or grammar shown gti E | | 1
ein rhe ips sD)
EEE
ES bE [te
| So
| a
| & Caer towing rear
| 53 AbB
| AAA JE
59 aB {bu €
| Ge LD and RMD and Pan re forthe sing as =
| | 2
—t |
[Sap Dena PON ring: palm LON WOW] Waar) | [10
q

verse of Wand show ID for Ihe ring ad?

sings ofa andy with equ mane fa and
ta mao generate nage a sing OS ang à

Deinen "vih example
Grammar

pe
nd Rightmont derivación
Ange gr

Parse re
Module

Qua

SEEN

Sr
A

rele sho es BENT

S= sa Shan B
ES

lumina eR recurson.

Page ot of 02

3. BCS401

4. Q 1 a) ii] Design DFA to Accept stings of 0' and Ps

1 fig z @ ow
Q 1 b) Define NFA. ma, E 5, % F)

Convert the following NFA to its equivalent DFA.

84020

Skp! Story Sele À DPA
{ad —— À
Skp? Imp sumbs of DPA
zei
Se? Cannder stale À en input 0 A)
Sol 10) = Sy(A10)
= Sy 143,0)
=
SCAN) = SCA)
= 194,13 —B

5. Condo Std B en Impr oAl
8»(B,0)= Su(1%,13,0)
an TS
SUB 1) = Sw (143.1)
=D
Conder State Con input © Al
S(c,0)= Sy ($4,4,3,0 )
= 19) —A
Sc, 1) = Sul F4%,%3, 1)
= F%, 43—B
Conde Stele D on Input 041
S500, 0) = Sy (19,9, 9%), 0)

= 1, 4)=2
So(0,1)= Sul f %4,42,!)
AGL, q
A= 1%3 — Imhal glad
Be 147
Gz 1%)

SO a à 9 bee delo

7. Q 2 a) Find £ -Closure of all the states Convert following NFA to DEA

E-tlesur (40) = $999, In, %, 4,3
e Me Fay 40,943

Y (%) = tas

© C4) = 143,9, %, 9,9%, 443

= $9,9,, 40, %, %, %)
N (4) = da

“ C5) = $9, %, %, % %e, 953

"C= 49,4, % % 933
(a) 19%)
SES
E

a (%)=$%3

8. SRL Suns Shale ot DPD. = {91
E-chsu (%) = 10% 4, 93 — bh
Skee mt Sumo)
== 10
S03 Condor Bede A pta Kb
Sy (Aa) = e-come(S,(A19))
= €-casea(Sy(f %,4, %, 943,0)
= Edo (93,98)
= 89,9, %, 216,9 13-2
SoÛA 6) = E-cderur (Sn(Aıb))

= ed (5
aan 4, 96,% lc
Cada B empt 04 b
30 (B,a) = Ebru Sn (a, 4,4, 4,2,%,80),0)
CAS
$0( 8 b) = ectew ($4(8, 6)
= tum (95, 99)
= $9, 9 9 9, 44%) 0
Compdur Sek Cm agb
So (e a) Bula, a, 9, %, 4, %) a)

9. = Ech (% 9’) —p
Conor Ste
Cora o (ob) = Cam (5)
= 11,10 9, 95,9, fc
Cond Gule D m mps a ib
Sa ec (S444, 949, 4m) )
= cc Ca) — B
SoC Dib) em (4s) 40)
= 19,9 AR, A) —È
Condn LE en tb
Lo(2,0) = ene (Su (B,4))
= eu (%,%) —B
BB, ») = €-cum Cn 5)
Ed (4) — ©
Shee £45 9, Fey 9%) — trade sted
Be 19,4, % % 4,4%)
C= RI
De 19,9% %,% 09)
Be Ta, % 4,9907 Fo — fred sla

10. Seesen] a a

Te E

11. a2b)
i) Define Alphabets Strings and Languages.

Os and Us starting with at least two

ii) Construct a DFA to accept strings
at least two Ps.

Us and ending wi

[o]
on
Q3a)
i) Define Regular Expressions. *ytı =
si) Obtain RE to accept strings of a’s and b’s whose second symbol from the
right end is a = zer. la
(osa (a+b)

iii) Obtain RE to accept words with two or more letters but beginning and
ending with the same letter where {a, b} are inputs.

Atasfa + b(are) b

a atb b

12. |) Obtain NFA which accepts strings of a°s and b’s starting with the string

a

ab

v) Obtain NFA for the Regular Expression (a+b)*aa(atb)*

Q 5 2}4) Obtain the unambiguous grammar for the grammar shown and get

the derivation for the expression (a+b)*(a-b).

E> E+E|E-E
E > E*E|E/E
E> (E)|1
1alble

EDe+T/e-TiT

T> TAR ]T/E | E
Lo ce)le
I>alble

Ed Ere
=> (E)xE
(BE) E
UE) WE
(are) XB
(042) 2
(ato) ee
=> (a+) (£)
> (arb)¥(8-B)
> (a+ el
à Len
=) (a +b)» (A>
en

13. la 5 a) ii) Consider the following y

S > AbB
A > aA | €
B> aB|bB| €
Give LMD and RMD and Parse tree for the string ©
LMD
= Rup
85 AbB 65 Am
=> adb8 > AbaB
=> 20 40B => hhabB
=> aaahbB > Abab
> aaab8 >ahbab
> aaa baß > aahbab
> 094 babPh > aaabab
=> aaabab > aaa bab

A
A
a»
es

a

So

Dr
®—w

>
O~>

14. la 5 b) Design a PDA for accepting a palindrome

L(M) = (WCW | We(atby*} where Wis reverse of W and show ID

for the string “aab”

bya | bq

a, b/ab

b,b/bb

ba/bæ

a,a/aa bbe
a wo aa/e

15. fa 6 a) Construct CFG for the following languages

i) L=(0%1" | n>=0, m>=0} ta
S>AR Een
A> ooAle Mn oood Im 41
ß>1Ble
ii) Le {WW®" | WE {a, D) *}} wow
ab bg

S+asalbsb|e

iii) Le {w | w € {0,1 }* with atleast one occurance of “101” }

8> Blow
A> onlihle

iv) L= (strings of a’s and b's with equal number of a’s and b’s }
sal number of a’s and b’s |

3> ash |bsalss Je ab, bg
haba,

y) Obtain a grammar to generate a language of strings 0's and 1’s haing a

S > AOOOA
AoA) 1AJe
= u

16. Q6 b) Define with example
i. Grammar

Derivation

ftmost and Rightmost derivation

jguous grammar
tree

iv

v. Pa

Q 7 a) Convert the above grammar to CNF TACA
S>alaalB 3 back
A> aBB |e
B>Aalb

Neuabu New v2} 4)
Reset, Ginn
S>ala ala
A> aBB
B> Aa la |b
Unit Pracluehn 3>8B

s>alas|asjalb

A> aBB
Repic BB wdh Ds
22 fala |b Do> BB
Reple a wih Be
Ba

3 a|8n|as [ale
S334 [RAlAB ]a 1b|) > 8,0,
A> BR 8> AB lalo
BS 48 ja |b
Bq

17. Q7 b) Eliminate left recursion. dia ©)
S — $a als Sb|aA| B

Bip Arte |p
&>AblaBB|alb A> pA!

mB eee
B > Ba|bb
AS

Saas! los
8548 |bs'|e
A> aa | ba']aba
AS bale
BS bof
B> aß'le

18. jachine (TM). Design a TM for

} Show that the si 011 is accepted

OD

SER

ye ye)

(0,92) 0,0,L
ua à
( CT
rye
Uy
@.8,R)

19. Machine (TM). Design a TM

n>=1} Show that the Strin

Ano TT D
xl
(K&L)

Wye) Ge) QUE)
(1,8) ED (vi)
(2,2,1)