Popular Posts

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

Visitor's Feedback

"I am very thankful, providing good stuff for engg students. I got good information about TOC and its information valuable for me."
: - Ankur Loriya (Ahmedabad)

"An amazing work, i just love your work!! please please please keep updating application based problems as well, it will definitely add interests to those whose visit your blog!! Thank you"
: - Preethi Velmurughan (Coimbatore)

"I got chance to learn what is the theory of computation thats why thankh you very much for this blog"
: - Ajay Sapkota (Kathmandu)

"Very nice presentation ,easy to go through the content"
: - Dr. A ramesh babu(Trichy)

"Nice tutorial example of constructing dfa..... thanks"
: - Manoj kumar (Delhi)

"I am a lecturer who is handling TOC for B.E students ....This is blog is very much useful for me ..It gives a lot of informations."
: - Sivaranjani.s (Theni)

"This is very good material for theory of computation thank you sir"
: - Mohan lal jat (Udaipur)

"its very good for engg student to get a readymade questions at the exam time. thank you."
: - Asfiya Peerjade (Kolhapur)

"I am a lecturer....this blog is awussom for me to understand.... and to learn more practical example....thanx nd plzzzz update more 1"
: - Sumedha Bhagat (Lecturer, Pune)

"You are doing very good job for an engg student for getting more problems with solution."
: - Chandrakant (Student, Nanded)