Question 1156 – Theory-of-Computation

→ L₁ is Context Free language because we can push all the a’s that come as input and when b’s come as input pop “n” number of a’s for “n” b’s from top of the stack and when again a’s come as input pop-up all the remaining a’s(i.e. “M” number of a’s) from top of the stack for “m” number of a’s coming as input.
Since we can have a pushdown automata for L₁ so we can say L₁ is a CFL.
→ L₂ is not a context free language because L is equivalent to language = {a^pb^pa^p | p ≥ 0}.
So for every “b” we can POP a’s came before “b” but for “a” which came after “b” we have nothing to POP on the top of stack. Since we can’t have a pushdown automata that can accept L₂.
L₂ is not a CFL.