tailieunhanh - Lecture note Theory of automata - Lecture 7

Lecture Theory of automata - Lecture 07 presents the following content: FA of EVEN EVEN, FA corresponding to finite languages(using both methods), transition graphs, example EVEN-EVEN, FA corresponding to finite languages, defining languages. | Lecture # 16 Theory Of Automata By Dr. MM Alam 1 1 Summary Lecture#15 Equivalence of Mealy and Moore Machines – Repeat Transducers (NAND,OR,AND,NOT) Transducers Example 1 2 Example2 Taken from the Book Exercises Circuit Diagram OR DELAY AND OR Output B A input New B = old A New A = input OR(old A OR old B) output = old B AND input Example2 A = 0, B = 0 q0 A = 0, B = 1 q1 A = 1, B = 0 q2 A = 1, B = 1 q3 New B = old A New A = input OR(old A OR old B) output = old B AND input Example2 State q0 /input = 0 / A = 0, B = 0 New B = old A = 0 New A = input OR (old A OR old B) = 0 OR (0 OR 0) = 0 OR 0 = 0 Output = input AND old B = 0 AND 0 = 0 Example2 State qo / input = 1 / A =0, B = 0 new B = old A = 0 new A = input OR (old A OR old B) = 1 OR (0 OR 0) = 1 OR 0 = 1 output = input AND old B = 1 AND 0 = 0 Example2 state q1 / input = 0 /A = 0, B= 1 new B = old A = 0 new A = input OR (old A OR old B) = 0 OR (0 OR 1) = 0 OR 1 = 1 output = old B AND input = 1 AND 0 = 0 Example2 state q1/ input | Lecture # 16 Theory Of Automata By Dr. MM Alam 1 1 Summary Lecture#15 Equivalence of Mealy and Moore Machines – Repeat Transducers (NAND,OR,AND,NOT) Transducers Example 1 2 Example2 Taken from the Book Exercises Circuit Diagram OR DELAY AND OR Output B A input New B = old A New A = input OR(old A OR old B) output = old B AND input Example2 A = 0, B = 0 q0 A = 0, B = 1 q1 A = 1, B = 0 q2 A = 1, B = 1 q3 New B = old A New A = input OR(old A OR old B) output = old B AND input Example2 State q0 /input = 0 / A = 0, B = 0 New B = old A = 0 New A = input OR (old A OR old B) = 0 OR (0 OR 0) = 0 OR 0 = 0 Output = input AND old B = 0 AND 0 = 0 Example2 State qo / input = 1 / A =0, B = 0 new B = old A = 0 new A = input OR (old A OR old B) = 1 OR (0 OR 0) = 1 OR 0 = 1 output = input AND old B = 1 AND 0 = 0 Example2 state q1 / input = 0 /A = 0, B= 1 new B = old A = 0 new A = input OR (old A OR old B) = 0 OR (0 OR 1) = 0 OR 1 = 1 output = old B AND input = 1 AND 0 = 0 Example2 state q1/ input = 1 /A = 0 , B = 1 new B = old A = 0 new A = input OR (old A OR old B) = 1 OR (0 OR 1) = 1 OR 1 = 1 output = old B AND input = 1 AND 1 = 1 Example2 state q2/ input = 0/ A = 1, B= 0 new B = old A = 1 new A = input OR (old A OR old B) = 0 OR (1 OR 0) = 0 OR 1 =1 output = old B AND input = 0 AND 0 = 0 Example2 state q2 / input = 1 / A= 1/ B= 0 new B = old A = 1 new A = input OR (old A OR old B) = 1 OR (1 OR 1) = 1 OR 1= 1 output = old B AND input = 0 AND 1 = 0 Example2 state q3 / input = 0 / A= 1/ B= 1 new B = old A = 1 new A = input OR (old A OR old B) = 0 OR (1 OR 1) = 0 OR 1= 1 output = old B AND input = 1 AND 0 = 0 Example2 state q3 / input = 1 / A= 1/ B= 1 new B = old A = 1 new A = input OR (old A OR old B) = 1 OR (1 OR 1) = 1 OR 1= 1 output = old B AND input = 1 AND 1 = 1 After input 0 After input 1 Old State New State Output New State Output q0(A=0,B=0) q0 0 q2 0 q1(A=0,B=1) q2 0 q2 0 q2(A=1,B=0) q3 0 q3 0 q3(A=1,B=1) q3 0 q3 1 Regular Languages Defined by Regular Expression .