155 views
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.
| 155 views

+1 vote

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.

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..
0
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.