The Gateway to Computer Science Excellence
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.
in Theory of Computation by Active | 155 views

3 Answers

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

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,222 questions
59,849 answers
118,094 users