Automata

4. Let L be a language accepted by a PDA M. Define Prefix(L) = {x : there exists y such that ry E L. Describe a construction of a PDA M' accepting Prefiz(L). (You only need to describe in English how M' works.) 5. Consider the following pseudo-C code: int x-0; char d while (1) d-getchar ); if (d--EOF) break; //when reads EOF (end of the input) //get out of the while-loop //get here after breaking the loop if (x-0) putchar('y'); //write yes to stdout This program writes 'y' (yes) to stdout (your screen) for some particular sequences of input characters (i.e., strings). These strings form a language L. Construct a PDA to accept L. (What we learn from this problem is that a program with one integer variable can always be simulated by a PDA.)