tailieunhanh - Lecture note Theory of automata - Lecture 18

The main contents of this chapter include all of the following: NFA corresponding to union of FAs, example, NFA corresponding to concatenation of FAs, examples, NFA corresponding to closure of an FA, example. | Lecture # 27 Theory Of Automata By Dr. MM Alam 1 1 Lecture 26 RECAP Unit Production Elimination Chomsky Normal Form JFLAP practical for CNF 2 Chomsky NORMAL Form in JFLAP Practical Demonstration 3 A new Format for FAs We will start with our old FA's and throw in some new diagrams that will augment them and make them more powerful. In this chapter complete new designs will be created for modeling FA’s. 4 New terminologies We call it INPUT TAPE to the part of the FA where the input string lives while it is being run. The INPUT TAPE must be long enough for any possible input, and since any word in a* is a possible input, the TAPE must be infinitely long. The TAPE has a first location for the first letter of the input, then a second location, and so on. Therefore, we say that the TAPE is infinite in one direction only. 5 A new Format for FAs The locations into which put the input letters are called cells. (See table below) Name the cells with lowercase Roman numerals. The Δ used to . | Lecture # 27 Theory Of Automata By Dr. MM Alam 1 1 Lecture 26 RECAP Unit Production Elimination Chomsky Normal Form JFLAP practical for CNF 2 Chomsky NORMAL Form in JFLAP Practical Demonstration 3 A new Format for FAs We will start with our old FA's and throw in some new diagrams that will augment them and make them more powerful. In this chapter complete new designs will be created for modeling FA’s. 4 New terminologies We call it INPUT TAPE to the part of the FA where the input string lives while it is being run. The INPUT TAPE must be long enough for any possible input, and since any word in a* is a possible input, the TAPE must be infinitely long. The TAPE has a first location for the first letter of the input, then a second location, and so on. Therefore, we say that the TAPE is infinite in one direction only. 5 A new Format for FAs The locations into which put the input letters are called cells. (See table below) Name the cells with lowercase Roman numerals. The Δ used to indicate the blank Input string is aab 6 a a b Δ Δ Input tape parsing As TAPE is processed, on the machine we read one letter at a time and eliminate each as it is used. When we reach the first blank cell we stop. We always presume that once the first blank is encountered the rest of the TAPE is also blank. We read from left to right and never go back to a cell that was read before. 7 New symbols for FA To streamline the design of the machine, some symbols are used. The arrows (directed edges) into or out of these states can be drawn at any angle. The START state is like a state connected to another state in a TG by a ʎ edge. We begin the process there, but we read no input letter. We just proceed immediately to the next state. 8 A new Symbol for FAs A start state has no arrows coming into it. An ACCEPT state is a shorthand notation for a dead-end final state-once entered, it cannot be left, shown on next slide : 9 Start Accept Reject A new Format for FAs A REJECT state is a dead-end state