My Youtube Video Channel ( With Theory of Computations)

Loading...

Monday, July 5, 2010

Example of Finite Automata


B. H. Gardi College of Engineering and Technology
MCA Semester - II
Subject: 620007 - Theory of Computation
Unit - II
Important Question

DFA for Language L1 and L2 are given as follow

Figure – I: DFA for Language L1

Figure – II: DFA for Language L2

       Find out. (a) L1 U L2, (b) L1 ∩ L2, (c) L1 – L2

Step-I

Common Diagram For All three Question



(a)   L1 U L2

-         In Figure - I ‘C’ is Final State and In Figure -II ‘Z’ is Final State, So All the State Containing Either ‘C’ or ‘Z’ becomes a Final State.
-         So, CY, AZ, BZ, and CZ become Final State.

Now, We can simplify the above figure as per follow.   

Final DFA which accept L1 U L2



(b)   L1 ∩ L2

- In Figure - I ‘C’ is Final State and In Figure -II ‘Z’ is Final State, So All the State Containing both ‘C’ AND ‘Z’ becomes a Final State.
- So, CZ becomes Final State.

Now, we can simplify the above figure as per follow.

Final DFA which accept L1 ∩ L2



(C) L1 – L2

- In Figure - I ‘C’ is Final State and In Figure -II ‘Z’ is Final State, So All the State Containing ‘C’ and Does Not Containing ‘Z’ becomes a Final State.
- So, CY becomes Final State.

Now, we can simplify the above figure as per follow.

Final DFA which accept L1 - L2     

No comments:

Post a Comment