0
$\begingroup$

$$L=\left \{ a^nb^m|n\leq m\leq 2n \right \}$$ Is this even context free?
I am asking because by looking at the condition, for an expression that holds:$n< m<2n$ can be written as : $a^nb^nb^c (c<n)$.
Following this term(taken from geeks for geeks https://www.geeksforgeeks.org/check-if-the-language-is-context-free-or-not/) :"An expression that involves counting and comparison of three or more variables independently is not context free language, as stack allows comparison of only two variables at a time."
So here I need to make sure that number of first b's is the same as a's and the second b's are less than n$(c<n)$, which makes me think that L might not be context free(although it specified clearly to build PDA for this).

$\endgroup$
1
$\begingroup$

Yes, the language is context-free. I recommend that you ignore that article on geeks for geeks; its so-called "analysis" is stated in a way that is highly ambiguous, and appears to be faulty in some cases.

Hint: The language has the form $L = \{a^j a^k b^k b^{2j}\}$. Build a PDA that non-deterministically guesses $j$. (I assume you know how to build a PDA for $\{a^n b^n\}$ and $\{a^n b^{2n}\}$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.