tailieunhanh - Lecture note Theory of automata - Lecture 6
In this chapter, the following content will be discussed: Language of strings beginning with and ending in different letters, Accepting all strings, accepting non-empty strings, accepting no string, containing double a’s, having double 0’s or double 1’s, containing triple a’s or triple b’s, EVEN-EVEN. | Lecture # 15 Theory Of Automata By Dr. MM Alam 1 1 Lecture 14 at a glance 2 Example Moore and Mealy Machines Repeat Incrementing Mealy machines Overflow state. Constructing the incrementing machine continued The Mealy machine have the states q0, q1, q2 , where q0 is the start state and = {0,1}, Г={0,1} 3 Overflow state Due to typical property of Mealy machines of having input bits equals to outputs, if string 1111 is run as input, the output will be 0000 and not 10000. This is called overflow state. 4 Relationship between input and output Generally, a Mealy machine does not accept or reject an input string, there is an implicit relationship between the input and output string. Consider the following example Mealy machine taken from Daniel A Cohen book, in which whenever a double letter such as aa or bb appears, the output string places 1 as indication. 5 6 Theorem Statement: For every Moore machine there is a Mealy machine that is equivalent to it (ignoring the extra character . | Lecture # 15 Theory Of Automata By Dr. MM Alam 1 1 Lecture 14 at a glance 2 Example Moore and Mealy Machines Repeat Incrementing Mealy machines Overflow state. Constructing the incrementing machine continued The Mealy machine have the states q0, q1, q2 , where q0 is the start state and = {0,1}, Г={0,1} 3 Overflow state Due to typical property of Mealy machines of having input bits equals to outputs, if string 1111 is run as input, the output will be 0000 and not 10000. This is called overflow state. 4 Relationship between input and output Generally, a Mealy machine does not accept or reject an input string, there is an implicit relationship between the input and output string. Consider the following example Mealy machine taken from Daniel A Cohen book, in which whenever a double letter such as aa or bb appears, the output string places 1 as indication. 5 6 Theorem Statement: For every Moore machine there is a Mealy machine that is equivalent to it (ignoring the extra character printed the Moore machine). Proof: see the following example 7 8 Theorem Statement: For every Mealy machine there is a Moore machine that is equivalent to it (ignoring the extra character printed the Moore machine). Proof: Let M be a Mealy machine. At each state there are two possibilities for incoming transitions All incoming transitions have the same output. All incoming transitions have different output. 9 Proof continued If all the transitions have same output characters, handling it is very easy. If all the transitions have different output characters, then the corresponding state will be divided in to the number of outputs generated by incoming transitions. Please note that the divided state shall behave like the undivided one, that is the output should be same. 10 Continued Initial state conversion . No output on a set of transitions . 11 Example Consider the following Mealy machine 12 Example continued . Dividing the state q0 into q0/0 and q0/1 13 Example continued . .
đang nạp các trang xem trước
