1,749 views

3 Answers

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.

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

Related questions

3 votes
3 votes
2 answers
1
kanahanin asked Dec 8, 2015
1,738 views
Is the language given by $ww^R ww^R$, where $w$ is any string over the binary alphabet, Context Free or Context Sensitive?