cs402 assignmnet 2 solution

  solution   idea
                

               Cs402 theory of automata

                  Assignment solution 2

                        Fall 2011

Question 1:

Theory of Automata (CS402)
Assignment No.2
 Objective of this assignment is to make students able to understand the following
concepts,
• Finite Automata
• Transition Graph
• Generalized Transition Graphs
• Kleene’s Theorem Part III
 

Question No.1
Finite Automata
Consider the Language L of Strings, defined over Σ = {a, b}, staring and ending with
same letter. The RE of language is: (a+b) +a (a + b)*a + b (a + b)*b. Draw the FA of
given Language.

Sol:

                                  FA according to regular expression :

Question No.2
Transition Graph
Draw the TG for the language L of strings, defined over Σ = {a, b} in which if a occur it is
in the form of aaa and that ends in two or more b's.

                  RE  of language    (aaa)*b (b*+ (aaa (aaa)*b)*bb

TG as shown in fig a

 Question No.3
Transition Graph
Draw the TG for the language L of strings, defined over Σ = {a, b}, beginning and ending
in same letters. The language L may be expressed by RE a(a + b)*a + b(a + b)*b.

sol:

  in fig b