# Help converting a CFG to an APD So I have this contest free grammar, and I’m having trouble when checking that there are more a’s than c’s, because I would have to check that the string I am processing is consumed in its entirety, but with the stack not empty, and I have no idea how to do that. The way we studied this in my class, I have no way of knowing if a string has been consumed.

\begin{align}S&\to AB | aSc\ A&\to aA | a\ B&\to bB | b\ \end{align}

Maybe it’s easier to read the definition of the language: $$L = \{x \in L(a^∗b^∗c^∗) : |x|_a > |x|_c; |x|_b > 0; |x|_c ≥ 0\}$$

This are the transitions I have so far: $$\delta(q_0, a , Z_0) = (q_0, A/Z_0)\ \delta(q_0, a, A) = (q_0, A/A)\ \delta(q_0, b, A) = (q_0, A)\ \delta(q_0, b, A) = (q_1, A)\ \delta(q_1, c, A) = (q_2, \epsilon)$$ What I have up until here is, I read the a’s and push them on the stack, then when i read the first b I go to another state (because I have to make sure there is at least one a, otherwise I could do it in the same state) and keep the stack the same. When I read the first c I go to yet another state and start reading the c’s and popping the a’s in the stack. What I should do now is verify that the string has been consumed, while the stack still has a’s, but I can’t think of a way to do that because I have no way of knowing if the string I am processing has been consumed or not. Posted on Categories proxiesTags ,