Example of Finite Automata

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