Let L = {0^k1^k0^k1^k | k >= 0}

(a)

The following rough description of a PDA may at first glance seem that it will recognize language L, but in fact it doesn't. What language does it recognize? Put $ on the stack. . Move to a new state for reading 0's. For each 0 read, put a 0 on the stack. Include an - transition to a new state for reading 1's. For each 1 read, remove a 0 from the stack. Transition to a new state for reading O's again only if the S symbol appears on the stack. (Assume you pop S and push it right back on the stack.) Read 0's again. For each 0 read, put a 0 on the stack. Include an e-transition to a new state for reading 1's again. Read 1's again. For each 1 read, remove a 0 from the stack. Transition to an accepting state if the S symbol appears on the stack. The accepting state has no transitions, so the string is accepted only if there are no symbols left to read when the accepting state is reached