CS402 1st Assignment idea solution last date 5th Nov 2012
We draw a Finite Automaton (FA) in the following manner: The machine's states are represented by circles and transitions are represented by arrows
A finite set of states, one of which is a start state, and some of which may be designated as accept states or final states.
An alphabet .
A finite set of transitions that tell for each state and for each letter of the alphabet which state to go to next
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 the alphabet . 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*.
![[Image: 2u8udkl.jpg]](http://i48.tinypic.com/2u8udkl.jpg)
We draw another Finite Automaton (FA) below which accepts any string from ab*.
![[Image: 24mc7kn.jpg]](http://i46.tinypic.com/24mc7kn.jpg)
We draw another finite automaton which accepts all strings from a*bb*aa*(ba*bb*aa*)*.
![[Image: et9l06.jpg]](http://i48.tinypic.com/et9l06.jpg)
The Transition graph that accepts only theempty word is,
![[Image: 34q1wd5.jpg]](http://i47.tinypic.com/34q1wd5.jpg)
Now by reversing an edge of "a" the above transition graph accepts the language a*
![[Image: 35kra7m.jpg]](http://i45.tinypic.com/35kra7m.jpg)
The resultant TG is
We draw a Finite Automaton (FA) in the following manner: The machine's states are represented by circles and transitions are represented by arrows
A finite set of states, one of which is a start state, and some of which may be designated as accept states or final states.
An alphabet .
A finite set of transitions that tell for each state and for each letter of the alphabet which state to go to next
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 the alphabet . 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 (FA) below which accepts any string from ab*.
We draw another finite automaton which accepts all strings from a*bb*aa*(ba*bb*aa*)*.
The Transition graph that accepts only theempty word is,
Now by reversing an edge of "a" the above transition graph accepts the language a*
The resultant TG is
