tailieunhanh - Lecture note Theory of automata - Lecture 19

The following will be discussed in this chapter: NFA corresponding to closure of FA, examples, memory required to recognize a language, example, distinguishing one string from another, example, theorem, proof. | Lecture # 28 Theory Of Automata By Dr. MM Alam 1 1 Lecture 27 recap Chomsky Normal Form conversion in JFLAP Push Down Automata Definition PDA Symbols 2 Adding A Pushdown Stack A PUSHDOWN STACK is a place where input letters can be stored until we want to refer to them again. It holds the letters it has been fed in a long line. The operation PUSH adds a new letter to the line. The new letter is placed on top of the STACK, and all the other letters are pushed back (or down) accordingly. Before the machine begins to process an input string the STACK is presumed to be empty, which means that every storage location in it initially contains a blank. 3 Adding A Pushdown Stack If the STACK is then fed the letters a, b, c, d by this sequence of instructions: PUSH a PUSH b PUSH c PUSH d Then top letter in the STACK is d, the second is c, the third is b, and the fourth is a. If we now execute the instruction: PUSH b the letter b will be added to the STACK on the top. The d will be pushed down to | Lecture # 28 Theory Of Automata By Dr. MM Alam 1 1 Lecture 27 recap Chomsky Normal Form conversion in JFLAP Push Down Automata Definition PDA Symbols 2 Adding A Pushdown Stack A PUSHDOWN STACK is a place where input letters can be stored until we want to refer to them again. It holds the letters it has been fed in a long line. The operation PUSH adds a new letter to the line. The new letter is placed on top of the STACK, and all the other letters are pushed back (or down) accordingly. Before the machine begins to process an input string the STACK is presumed to be empty, which means that every storage location in it initially contains a blank. 3 Adding A Pushdown Stack If the STACK is then fed the letters a, b, c, d by this sequence of instructions: PUSH a PUSH b PUSH c PUSH d Then top letter in the STACK is d, the second is c, the third is b, and the fourth is a. If we now execute the instruction: PUSH b the letter b will be added to the STACK on the top. The d will be pushed down to position 2, the c to position 3, the other b to position 4, and the bottom a to position 5. 4 Adding A Pushdown Stack One pictorial representation of a STACK with these letters in it is shown below. Beneath the bottom a we presume that the rest of the STACK, which, like the INPUT TAPE, has infinitely many storage locations, holds only blanks. b d c b a Δ 5 5 Adding A Pushdown Stack How the following PDA is working: 6 b a 6 Adding A Pushdown Stack Its operation on the input string aaabbb. We begin by assuming that this string has been put on the TAPE. Δ a a a b b b Δ TAPE STACK 7 7 Adding A Pushdown Stack Its operation on the input string aaabbb. We begin by assuming that this string has been put on the TAPE. a a a b b b Δ a Δ STACK TAPE 8 8 Adding A Pushdown Stack We now read another a and proceed as before along the a edge to push it into the STACK. Again we are returned to the READ box. Again we read an a (our third), and again this a is .