Question No1: Let r 1 = b(a+b)* r 2 = (a+b)*a FA 1 corresponding to r 1 FA 2 cor
ID: 3615141 • Letter: Q
Question
Question No1:
Let
r1= b(a+b)*
r2= (a+b)*a
FA1 corresponding to r1
FA2 corresponding to r2
Using the FAs corresponding to r1 and r2,Build an FA corresponding to
a) r1+ r2(Union of r1 and r2).
b) r1r2(Concatenation of r1 and r2).
c) r2* (Closure ofr2).
Note :You have to specifytransition table and transition diagram for eachpart(a)(b)(c)
Explanation / Answer
Note :You have to specifytransition table and transition diagram for eachpart(a)(b)(c)
Answer.
a) r1 + r2
Old States
New States after reading
a
b
z1 - (x1,y1)
(x3,y2) z2
(x2,y1) z3
z2 + (x3,y2)
(x3,y2) z2
(x3,y1) z4
z3 + (x2,y1)
(x2,y2) z5
(x2,y1) z3
z4 (x3,y1)
(x3,y2) z2
(x3,y1) z4
z5 + (x2,y2)
(x2,y2) z5
(x2,y1) z3
DRAW DIAGRAM YOURSELF BY JUST FOLLOWING THE STATES GIVEN INABOVE TABLE
b) r1r2
Old States
New States after reading
a
b
z1 - x1
x3 z2
(x2,y1) z3
z2 x3
x3 z2
x3 z2
z3 (x2,y1)
(x2,y1,y2) z4
(x2,y1) z3
z4 + (x2,y1,y2)
(x2,y1,y2) z4
(x2,y1) z3
DRW DIAGRAM YOURSELF BY JUST FOLLOWING THE STATES GIVEN IN ABOVETABLE
a) r2*
Old States
New States after reading
a
b
Final z1 ± y1
(y2,y1) z3
y1 z2
Non-Final z2 y1
(y2,y1) z3
y1 z2
z3 + (y2,y1)
(y2,y1) z3
y1 z2
DRW DIAGRAM YOURSELF BY JUST FOLLOWING THE STATES GIVEN IN ABOVETABLE
Question No 2: Marks: 5
Convert the following NFA into FA.
Answer.
Draw diagram yourself.
Old States
New States after reading
a
b
-Q0
Q1
There is no transition showing b in this case
+Q1
Q1
Q2
Q2
Q1
There is no transition showing a in this case
Old States
New States after reading
a
b
z1 - (x1,y1)
(x3,y2) z2
(x2,y1) z3
z2 + (x3,y2)
(x3,y2) z2
(x3,y1) z4
z3 + (x2,y1)
(x2,y2) z5
(x2,y1) z3
z4 (x3,y1)
(x3,y2) z2
(x3,y1) z4
z5 + (x2,y2)
(x2,y2) z5
(x2,y1) z3
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.