Constructing a PDA for the language $\{a^m b^n : m < 2n < 3m \}$

Problem Detail: 

I'm having a lot of trouble constructing a PDA for the language: \begin{equation*} \{a^m b^n : m < 2n < 3m \} \end{equation*}

I know if I push a symbol for each $a$ I see, then pop 2 symbols for each $b$ I see, then I should run out to satisfy the $m < 2n$ part of the inequality. But I really don't understand how to include the requirement $2n < 3m$. I'm assuming it has something to do with clever branching based on non-determinism, but I can't wrap my head around it. Any help would really appreciated.

Asked By : Kevin G

Answered By : Gilles

To handle the inequality $m \lt 2n$, you arrange to push a marker for each $a$, and pop two markers for each following $b$. This way the number of markers on the stack indicates the number of $a$'s. When the stack is empty, the equality is reached.

To handle the inequality $2n \lt 3m$, you could to arrange to push three markers for each $a$ and pop two markers for each following $b$. However, a stack won't let you push different numbers of markers.

There is no general way of "merging" two automata in this way. If the two automata use the stack at different rates, it may not be possible to merge them without having two stacks. This is reflected in the properties of languages recognized by pushdown automata: the intersection of two context-free languages is not always context-free.

To get an idea of what to do here, I think it helps to write a context-free grammar for this language. A grammar needs to break down the language into some recursive structure, which leads us to expressing elements of the language as expansions of shorter elements. I'll look at what happens when $b$s are added; you could obtain a different grammar by similar means by looking at what happens when $a$s are added.

If you add $1$ to $n$, what happens to the possible values of $m$? For the maximum value, it's easy: it increases by $2$, because $m \lt 2n \iff m+2 \lt 2(n+1)$. For the minimum value, it's more difficult: we need to find the threshold for $\frac{2}{3}n$, so it depends on whether $n$ is a multiple of $3$, which we cannot express in a grammar rule. However, if we add three $b$s at a time, it's easy: the minimum number of $a$s increases by $2$, because $2n \lt 3m \iff 2(n+3) \lt 3(m+2)$.

Let $L$ be the desired language. The rule above tells us how words in $L$ can be constructed from shorter words; we still need to check the base cases. $$ \begin{align} L \cap a^* &= \varnothing \\ L \cap a^* b &= \{ab\} \\ L \cap a^* b^2 &= \{a^2b^2, a^3b^2\} \\ L \cap a^* b^3 &= \{a^3b^3, a^4b^3, a^5b^3\} \\ \end{align} $$ We have all the information needed to construct a grammar for $L$. $$ \begin{array}{rl} S &\to a b \\ S &\to a^2 b^2 \\ S &\to a^3 b^2 \\ S &\to a^3 b^3 \\ S &\to a^4 b^3 \\ S &\to a^5 b^3 \\ \end{array} \qquad \begin{array}{rl} S &\to a^2 S b^3 \\ S &\to a^3 S b^3 \\ S &\to a^4 S b^3 \\ S &\to a^5 S b^3 \\ S &\to a^6 S b^3 \\ \end{array} $$ If you're unsure about the correction of this construction, prove that all words in $L$ are recognized by this grammar (construct a derivation) and prove that all the words recognized by this grammar are in $L$ (by induction over the rules).

Now you can apply a systematic method for constructing a non-deterministic pushdown automaton from a grammar. Since the right-hand part of every rule is the same, it is enough to have a single element in the stack alphabet. Push this symbol for each batch of 2 to 6 $a$'s (this is non-deterministic); pop it for 3 $b$'s.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14935