CS402 Assignment 1 Solution Spring 2022

 

CS402 Assignment 1 Solution Spring 2022

 

Due 14 June 2022

 

 

Questions No 01                                                                                                           Marks (5+5)=10

a)                  Construct a Regular Expression for the given language defined over ∑= {a, b, c}:

 

b (a + b) c (a + b)* a

 

b)                  Construct Finite Automata (FA) for the generated RE in part (a).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Question No 2:                                                                                            Marks: 2.5+2.5 +5=10

a)                         Draw a Transition Graph (TG) defining the following language over ∑= {a, b}:

All words starting with triple letters.

 

(aaa + bbb) (a+b)*

 

 

 

b)                         Draw Generalized Transition Graph (GTG) of the language stated in part (a).

 

c)                   Give transition table for the union of the given FA’s (FA1 U FA2).

 

FA1:

 

FA2:

 

Old states	Reading a	Reading b
x1, y1 =z1	x2, y2 =z2	x2, y2 =z2
x2, y2 =z2 +	x2, y4 =z3	x2, y3 =z4
x2, y4 =z3 +	x2, y4 =z3	x2, y4 =z3
x2, y3 =z4 +	x2, y3 =z4	x2, y3 =z4