NPTEL Theory of Computation Assignment 5 Answer

What is the language accepted by the following pushdown automaton? (Rev(w) is reverse of string w, w¯w¯ is bit wise negation of w)

For an input string w and context-free grammar G, suppose TG,wTG,w be the parse tree and let h denote its height and d be the maximum degree at any node. Which of the following is always true?

Suppose pumping lemma in the contrapositive form is being applied on the language L={ambmcndn|m≥n}L={ambmcndn|m≥n} in order to prove that it is not context free. Given p (refer to pumping lemma), we choose the string apbpcpdpapbpcpdp. For any partition uvxyz of it such that |vxy|≤p and |vy|>0|vxy|≤p and |vy|>0, consider the case when vxy=ak1bk2 such that k1,k2>0vxy=ak1bk2 such that k1,k2>0, what could be the choice(s) of i, where i≥0i≥0, such that uvxyz is not in L?

Continuing from the previous question, consider the case when vxy=ck1dk2 such that k1,k2>0vxy=ck1dk2 such that k1,k2>0, what could be the choice(s) of i, where i≥0i≥0, such that uvxyz is not in L?