# 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