1. Lecture # 27 Theory Of Automata By Dr. MM Alam 1
  2. Lecture 26 RECAP.. • Unit Production Elimination • Chomsky Normal Form • JFLAP practical for CNF 2
  3. • Chomsky NORMAL Form in JFLAP • Practical Demonstration 3
  4. 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
  5. 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. 5
  6. 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. a a b Δ Δ • The Δ used to indicate the blank • Input string is aab 6
  7. 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
  8. 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
  9. A new Symbol for FAs • A start state has no arrows coming into it. Start Accept Reject • An ACCEPT state is a shorthand notation for a dead-end final state-once entered, it cannot be left, shown on next slide : 9
  10. A new Format for FAs • A REJECT state is a dead-end state that is not final. 10
  11. A new Format for FAs • READ states are introduced. • These are depicted as diamond shaped boxes 11
  12. A new Format for FAs • The FA that is used to be drawn • The FA that accepts all words ending in the letter a becomes, in the new symbolism, 12
  13. A new Format for FAs 13
  14. A new Format for FAs • We have also used the electronic diagram notation for wires flowing into each other. 14
  15. A new Format for FAs • We have also used the electronic diagram notation for wires flowing into each other. • Becomes 15
  16. Lecture 27 Summary • Chomsky Normal Form conversion in JFLAP • Push Down Automata Definition • PDA Symbols • Deterministic PDA Examples • Non-Deterministic PDA Examples • Thanks to Daniel I.A. cohen. The material for these slides has been taken from his 16 book Automata Theory