CS402 Theory of Automata Assignment No 1 Solution Fall 2012

CS402 Theory of Automata Assignment No 1 Solution & Discussion Due Date:05-11-2012

Q. 1. Draw a Finite Automaton (FA) that accepts the following strings:

         Λ, a, aabc, acba and accb                                                                    Marks [7]


We draw a Finite Automaton (FA) in the following manner: The machine’s states are represented by circles and transitions are represented by arrows. Every transition is marked by a symbol from thealphabet. The start state is marked by a sign and the final states are marked by a + sign as shown in the FA for a*ba*.

We draw another finite automaton which accepts all strings from a*bb*aa*(ba*bb*aa*)*.


Q. 2. Construct a finite automaton for the given Regular Expression (RE):

          (a + b)*(ab + ba)+a+                                                                              Marks [8]


The Transition graph that accepts only theempty word is,



Q. 3. Draw a Transition Graph (TG) for the language expressed by the following regular expression:

     ^ + 0(01 + 10)*1 + 1(10 + 01)*0                                                         Marks [5]

Now by reversing an edgeof “a” the above transition graph accepts the language. The resultant TG is