GATE may not directly ask to prove a theorem but questions can be based on the proofs as to why a particular theorem holds true or some crucial point in proof of theorem. And more importantly TOC is a theoretical subject , so it will be good if you're familiar with the important proofs like Pumping lemma for Regular and CFL and closure properties of languages. As far as i know PSUs question more about practical subjects like programming, CN, DBMS, Digital rather than theory.