tailieunhanh - Lecture note Theory of automata - Lecture 5

This chapter includes contents: Different notations of transition diagrams, languages of strings of even length, Odd length, starting with b, ending in a (with different FAs), beginning with a, not beginning with b, beginning with and ending in same letters | Lecture # 14 Theory Of Automata By Dr. MM Alam 1 1 Lecture 13 at a glance NFA conversion – Repeat Closure Task Solution 2 Finite Automata with output In Finite Automata, the input string represents the input data to a computer program. Reading the input letters is very much similar to how a computer program performs various instructions. The concept of states tell us that what we are printing and what we have printed so far. 3 Our goal in this chapter is to prove that the mathematical models that we have studied so far can be represented as machines. We will study two machines created by Mealy (1955) and by Moore (1956). Initially both models were intended for sequential circuit design. 4 Moore machine Definition A Moore machine consists of the following A finite set of states q0, q1, q2, where q0 is the initial state. An alphabet of letters = {a,b,c, } from which the input strings are formed. An alphabet Г={x,y,z, } of output characters from which output strings are . | Lecture # 14 Theory Of Automata By Dr. MM Alam 1 1 Lecture 13 at a glance NFA conversion – Repeat Closure Task Solution 2 Finite Automata with output In Finite Automata, the input string represents the input data to a computer program. Reading the input letters is very much similar to how a computer program performs various instructions. The concept of states tell us that what we are printing and what we have printed so far. 3 Our goal in this chapter is to prove that the mathematical models that we have studied so far can be represented as machines. We will study two machines created by Mealy (1955) and by Moore (1956). Initially both models were intended for sequential circuit design. 4 Moore machine Definition A Moore machine consists of the following A finite set of states q0, q1, q2, where q0 is the initial state. An alphabet of letters = {a,b,c, } from which the input strings are formed. An alphabet Г={x,y,z, } of output characters from which output strings are generated. 5 Moore machine continued 4. A transition table that shows for each state and each input letter what state is entered the next. 5. No final state, so no question of acceptance of input strings. 6 Moore Machine with JFLAP 7 Example: Moore NOT machine 8 Example: Divide an Input in to half 9 Mealy machine A Mealy machine consists of the following A finite set of states q0, q1, q2, where q0 is the initial state. An alphabet of letters = {a,b,c, } from which the input strings are formed. An alphabet Г={x,y,z, } of output characters from which output strings are generated. 10 Example Mealy machine 11 Complementing Mealy Machine 12 Incrementing Mealy Machine Consider the following additions a) 100101100 b) 1001111111 + 1 + 1 100101101 1010000000 If the right most bit is 0 then If the right most bit is 1 then 13 Incrementing Mealy Machine The machine will have three states: start, owe-carry (OC), and no-carry(NC). Owe-carry state will output 0 when two 1 bits are added. The .