0 votes 0 votes 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. Theory of Computation theory-of-computation context-free-language context-sensitive-languages + – !KARAN asked Jan 17, 2019 !KARAN 1.7k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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. Praveenk99 answered Jan 21, 2020 Praveenk99 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 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.. Vishal Sharma answered Sep 23, 2019 Vishal Sharma comment Share Follow See 1 comment See all 1 1 comment reply curiosity commented Nov 25, 2019 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 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 Raju2021 answered Apr 7, 2020 Raju2021 comment Share Follow See all 0 reply Please log in or register to add a comment.