Construct a Turing machine that prints the strings on {0, 1}* in the lexicographic order. Hint: The tape's initial contents: U0 The output is: U0 U 1 U 00 U 01:

2. Show a natural PDA that accepts L. 2. (35 points) Construct a Turing machine that prints the strings on {0,1} in the lexicographic order. Hint: The tape's initial contents: 0 The output is: 010001 3. (30 points) Let L be a language that is represented by the following regular expression