Question  No.1

Draw  the Transition graph (TG) for language of words in which the “b” occur only in even clumps and that end in four or more a’s.
Draw the Transition graph (TG) for language of words starting with three a’s or three b’s and ending with bb or aa
Draw the Transition graph (TG) for language of words having aab or bba anywhere in it
Draw the Transition Graph (TG) for language of words EVEN-EVEN,
Draw the Generalized Transition graph (GTG) for below given regular expression:

a*+ (ab+a)*(b+ Λ)+a*
Question No.2

Review the below given TG and check if the below given words can be read through this TG.

a
bba
bbab
abbaaabba


Question No.3
Consider the FA1 and FA2 given below,

FA1



FA2







Give RE’s corresponding to FA1 and FA2
Find FA and RE corresponding to the Union of FAs (FA1 + FA2)
Find FA and RE corresponding to Concatenation of FA’s (FA1.FA2)



Hint: First find FA and then find RE considering that FA as TG


Question No.4
Consider the FA1given below and find its closure (FA1*) also give RE before and after finding closure.

FA1




Question No.5

Give Non Deterministic Finite Automata (NFA) for each of the following language defined over alphabet Σ = {a, b}

Language having all strings with alternating a’s and b’s , some example strings are ababab… or bababa…
Language having all strings NOT containing aa at any place