1. Consider a non-deterministic automata that is similar to PDAs but has a first-in-first-out queue instead of a stack. Call them QDA. Remeber that a queue has a head and a tail; enqueue happens at the head and dequeue happens at the tail.

(i, 4 point) Formally define a QDA (like we defined PDA as a 6-tuple), define an "instantaneous description" of a QDA, define the notion of "yield" (|-*), and define ``acceptance'' of a string in terms of the IDs (just like we defined for PDAs).
(ii 5 point) Then show that there exists some non-context-free language that is accepted by a QDA. For this choose some known non-context-free language, and design a QDA (both as a tuple and a state diagram). Explain the intuition behind the QDA design for your chosen language. Next, trace an accepting path of some string of your choice (length at least 4) in the language (the list of IDs such that ID1 |- ID2 |- ... accepting ID).
(iii, 1 point) It is known that every CFL can be accepted by some QDA. Based on this fact and (ii), derive a relationship between CFL and the class of languages accepted by QDAs. Explain in 1-2 lines.