Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
In this chapter, you will learn to: Examples of writing REs to the corresponding TGs, RE corresponding to TG accepting EVEN-EVEN language, Kleene’s theorem part III (method 1:union of FAs), examples of FAs corresponding to simple REs, example of Kleene’s theorem part III (method 1) continued. | Lecture # 21 Theory Of Automata By Dr. MM Alam 1 1 Lecture#20 Recap Pumping Lemma 1 Examples Need for Pumping Lemma Version II JFLAP for Pumping Lemma Version II PUMPING Lemma Version II using JFLAP Pumping Lemma in JFLAP and in Daniel I. Cohen Book M is not taken as a length of x and y but it other words, it is shown as xy<= m Within the string decomposition, y cannot be null, but pumping 0 times, y cannot be empty. This fact is not very much obvious in the book. However, the following example, make a clear note on it. Pumping Lemma Example in Daniel I cohen Book Example Let us illustrate the action of the Pumping Lemma on a concrete example of a regular language. The machine below accepts an infinite language and has only six states 5 Example Any word with six or more letters must correspond to a path that includes a circuit. Some words with fewer than six letters correspond to paths with circuits, such as baaa. The word we will consider in detail is w = bbbababa Which has more than | Lecture # 21 Theory Of Automata By Dr. MM Alam 1 1 Lecture#20 Recap Pumping Lemma 1 Examples Need for Pumping Lemma Version II JFLAP for Pumping Lemma Version II PUMPING Lemma Version II using JFLAP Pumping Lemma in JFLAP and in Daniel I. Cohen Book M is not taken as a length of x and y but it other words, it is shown as xy<= m Within the string decomposition, y cannot be null, but pumping 0 times, y cannot be empty. This fact is not very much obvious in the book. However, the following example, make a clear note on it. Pumping Lemma Example in Daniel I cohen Book Example Let us illustrate the action of the Pumping Lemma on a concrete example of a regular language. The machine below accepts an infinite language and has only six states 5 Example Any word with six or more letters must correspond to a path that includes a circuit. Some words with fewer than six letters correspond to paths with circuits, such as baaa. The word we will consider in detail is w = bbbababa Which has more than six letters and therefore includes a circuit. 6 Example The path that this word generates through the FA can be decomposed into three stages: The first part, the x-part, goes from the - state up to the first circuit. This is only one edge and corresponds to the letter b alone. The second stage is the circuit around states q2, q3, and q5. 7 Example This corresponds to edges labeled b, b, and a. We therefore say that the substring bba is the y-part of the word w. After going around the circuit, the path proceeds to states q3, q6, q3, and q6. 8 This corresponds to the substring baba of w, which constitutes the z-part. w = b bba baba x y z 9 what would happen to the input string xyyz. x y y z = b bba bba baba Clearly, the x-part (the letter b) would take this path from -- to the beginning of the circuit in the path of w. Then the y-part would circle the circuit in the same way that the path for w does when it begins xy. Pumping Lemma Version II from book Let L be an infinite language .