Intersection Process of Two DFAs | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Introduction

  • Let’s understand the intersection of two DFA with an example. 
  • Designing a DFA for the set of string over {0, 1} such that it ends with 01 and has even number 0f 1’s. 

There two desired language will be formed:

L1= {01, 001, 101, 0101, 1001, 1101, ....} 

L2= {11, 011, 101, 110, 0011, 1100, .....}

L = L1 and L2 = L1 ∩ L2

State Transition Diagram for the language L1 :
This is a DFA for language L1
Intersection Process of Two DFAs | Theory of Computation - Computer Science Engineering (CSE)

It accepts all the string that accept 01 at end. 

State Transition Diagram for the language L2 : 
This is a DFA for language L2 
Intersection Process of Two DFAs | Theory of Computation - Computer Science Engineering (CSE)

It accepts all the string that accept with even number of 1’s.
State Transition Diagram of L1 ∩ L2 :
Intersection of L1 and L2 can be explained by language that a string over {0, 1} accept such that it ends with 01 and has even number of 1’s.

L = L1 ∩ L2

= {1001, 0101, 01001, 10001, ....}

Intersection Process of Two DFAs | Theory of Computation - Computer Science Engineering (CSE)

Thus as we see that L1 and L2 have been combined through intersection process and this final DFA accept all the language that has even number of 1’s and is ending with 01.

The document Intersection Process of Two DFAs | Theory of Computation - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
Are you preparing for Computer Science Engineering (CSE) Exam? Then you should check out the best video lectures, notes, free mock test series, crash course and much more provided by EduRev. You also get your detailed analysis and report cards along with 24x7 doubt solving for you to excel in Computer Science Engineering (CSE) exam. So join EduRev now and revolutionise the way you learn!
Sign up for Free Download App for Free
18 videos|70 docs|44 tests

Up next

18 videos|70 docs|44 tests
Download as PDF

Up next

Explore Courses for Computer Science Engineering (CSE) exam
Related Searches

shortcuts and tricks

,

Intersection Process of Two DFAs | Theory of Computation - Computer Science Engineering (CSE)

,

Extra Questions

,

Intersection Process of Two DFAs | Theory of Computation - Computer Science Engineering (CSE)

,

ppt

,

Important questions

,

Previous Year Questions with Solutions

,

Exam

,

Objective type Questions

,

past year papers

,

practice quizzes

,

Viva Questions

,

MCQs

,

study material

,

Summary

,

mock tests for examination

,

Intersection Process of Two DFAs | Theory of Computation - Computer Science Engineering (CSE)

,

pdf

,

Free

,

Semester Notes

,

Sample Paper

,

video lectures

;