0
$\begingroup$

I am trying to recognize a particular language,

L= {a^n b^k | n<=k<=2n}

and according to me it should not be CFL, as i can see two comparision i.e. firstly number of a is compare to keep count less than equal to k, and secondly for count of b that should be less than twice n. My question then how it is still CFL??

Thankyou in advance for sharing your wisdom!! :)

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
0
$\begingroup$

If you're using grammars, then this is easy to see: $$S\to aSb\mid aSbb\mid \epsilon$$ That is, each $a$ corresponds to either 1 or 2 $b$'s.

If you're thinking about it from the automata perspective, then a PDA can push to the stack $n$ symbols while reading $a^n$, and then start popping those symbols upon reading $b^k$, with the following change: it may nondeterministically choose not to pop a symbol, but the it moves to a new state from which it must pop a symbol after reading $b$. This ensures that the number of $b$'s that are read is between $n$ and $2n$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks!! @Shaull , i truly respect you for your answer also for other answer you mention for Finite Automata mixture combinatorics, here i am able to get grammar part, but with respect to PDA, as per your approach will it not accept number of b greater than 2 times n? $\endgroup$
    – Niraj Jain
    Commented Oct 21, 2022 at 5:59
  • $\begingroup$ No, because after not popping a symbol upon reading $b$, you move to a new state where you have to pop upon reading $b$, and then go back to the first state. $\endgroup$
    – Shaull
    Commented Oct 21, 2022 at 6:06
  • $\begingroup$ got it completely!! Thanks for clarification @Shaull !! :) $\endgroup$
    – Niraj Jain
    Commented Oct 21, 2022 at 6:41

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