CFL or CSL

Question

Let L = $\{ a^n b^m  | m , n \in  \textbf{N}  \text{ and  m is multiple of n}\}$

How do we prove that this language is not CFL.

Answer 1

See this language is not CFL because the b's appearing are not in Arithmetic Progression and hence due to no presence of pattern our push down automata machine cannot accept it but the language is NOT CSL also as in N we have 0 so epsilon wont be present in CSL.

Answer 2

a^n b^m where m is a multiple of n:

then n = mk so the above language can  be replaced as: ( a^mk b^m) this is a CFL..

Comments

This language is NOT CFL. It is given that m is a multiple of n, so m = n*k where k is integral. But then, the value of k is ambiguous. It can be any integer ranging from 0 to +inf. If the value of k was given, suppose k = 4; then

$a^{n}b^{4n}$ would have been CFL.

Answer 3

m = nk so the above language can be replaced as: ( a^n b^(nk))

yes L is context free, as we can push k time  a’s and pop an a for each occurrence of b. Hence, we get a mid-point here as well