Please explain 6.2.1 including example 6.7 (which includes a proof) in a clear, complete, detailed and easy to understand way (first two pics). I have a very hard time understanding how this is working. The last two pics (example 6.2) are included because example 6.7 references it. Thank you for a better understanding. I have to present this to class today without simply copying what the book says and sound as if I know what Im talking about. The proof part is mainly what Ill be explaining/writing on the board. Thank for your help.
Example 6.2 because it is referred to in top picture
The rest of example 6.2 referred to in top pic
6.2.1 Acceptance by Final State et P = (Q. , i", go, Zo, F) be a PDA. Then L(P), the language accepted by P by final state, is (w I (go, to, Zo) (g,e,a)} for some state q in F and any stack string a. That is, starting in the initial D with w waiting on the input, P consumes w from the input and enters an accepting state. The contents of the stack at that time is irrelevant. Example 6.7: We have claimed that the PDA of Example 6.2 accepts the language Lwer, the language of strings in (0,1] that have the form wwk. Let us see why that statement is true. The proof is an if-and-only-if statement: the PDA P of Example 6.2 accepts string r by final state if and only if z is of the form ww (If) This part is easy; we have only to show the accepting computation of P. If wwR, then observe that That is, one option the PDA has is to read w from its input and store it on its stack, in reverse. Next, it goes spontaneously to state qi and matches wR on the input with the same string on its stack, and finally goes spontaneously to state q2. (Only-if) This part is harder. First, observe that the only way to enter accepting state q2 is to be in state qi and have Zo at the top of the stack. Also, any accepting computation of P will start in state go, make one transition to n, and never return to go. Thus, it is sufficient to find the conditions on z such that (o, r, Zo) F (i,, Zo); these will be exactly the strings r that P accepts by final state. We shall show by induction on Jrl the slightly more general statement: . If (o, z,a) F (i,c,a), then z is of the form wwR BASIS: If z = , then x is of the form wwR (with w = e). Thus, the conclusion is true, so the statement is true. Note we do not have to argue that the hypothesis (go,e, a)(a,e, a) is true, although it is. INDUCTION: Suppose aa.an for some n >0. There are two moves that P can make from ID (go, r,a): 6.2.1 Acceptance by Final State et P = (Q. , i", go, Zo, F) be a PDA. Then L(P), the language accepted by P by final state, is (w I (go, to, Zo) (g,e,a)} for some state q in F and any stack string a. That is, starting in the initial D with w waiting on the input, P consumes w from the input and enters an accepting state. The contents of the stack at that time is irrelevant. Example 6.7: We have claimed that the PDA of Example 6.2 accepts the language Lwer, the language of strings in (0,1] that have the form wwk. Let us see why that statement is true. The proof is an if-and-only-if statement: the PDA P of Example 6.2 accepts string r by final state if and only if z is of the form ww (If) This part is easy; we have only to show the accepting computation of P. If wwR, then observe that That is, one option the PDA has is to read w from its input and store it on its stack, in reverse. Next, it goes spontaneously to state qi and matches wR on the input with the same string on its stack, and finally goes spontaneously to state q2. (Only-if) This part is harder. First, observe that the only way to enter accepting state q2 is to be in state qi and have Zo at the top of the stack. Also, any accepting computation of P will start in state go, make one transition to n, and never return to go. Thus, it is sufficient to find the conditions on z such that (o, r, Zo) F (i,, Zo); these will be exactly the strings r that P accepts by final state. We shall show by induction on Jrl the slightly more general statement: . If (o, z,a) F (i,c,a), then z is of the form wwR BASIS: If z = , then x is of the form wwR (with w = e). Thus, the conclusion is true, so the statement is true. Note we do not have to argue that the hypothesis (go,e, a)(a,e, a) is true, although it is. INDUCTION: Suppose aa.an for some n >0. There are two moves that P can make from ID (go, r,a)
