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