6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Hint: For each $a$, push either $1$, $2$ or $3$ symbols. (But not always $1$ and not always $3$!)

$\endgroup$
  • $\begingroup$ I don't think it's so simple: how do you know how many symbols can be pushed for each $a$? The set of allowed values isn't always $\{1,2,3\}$. $\endgroup$ – Gilles 'SO- stop being evil' Oct 9 '13 at 19:14
  • 2
    $\begingroup$ You don't know. The result is a non-deterministic PDA. After the first phase, you can ensure that the stack contains $x$ symbols, where $m < x < 3m$, and moreover you can arrange for any such $x$. Then you just have to remove two symbols for each $b$. $\endgroup$ – Yuval Filmus Oct 9 '13 at 22:26
-4
$\begingroup$

yes, we can create PDA for the given language.

first i find the relation between n & m.

given that m < 2n < 3m

i break this in two equation

  1. 2n > m i.e [ n > m/2 ] -----------eqn-1

  2. 2n < 3m i.e [ n < 1.5m ] -------------eqn-2

from eqn 1 & 2 i found that [ m >= n+1 ]for n,m >= 2 i.e if n=2 then m=3 n=3 then m=4 etc

now it is simple to construct PDA for the above language a^m b^n where m>=n+1 & m,n>=2

push all a into stack and when see 1st b leave it and when see 2nd b then start popping a from stack.

$\endgroup$
  • 2
    $\begingroup$ This is just wrong. The inequalities do not imply that $m=n+1$: all they tell you is that $n$ is somewhere between $m/2$ and $3m/2$. $\endgroup$ – David Richerby Aug 3 '15 at 7:38
  • $\begingroup$ sorry sir, i did mistake here. i apologies for this. now i correct my solution, in place of m == n+1 , can i write m >= n+1.??? $\endgroup$ – Aditya Dhanraj Aug 4 '15 at 5:06
  • $\begingroup$ No, that's still wrong. You could have $m=n=1$. $\endgroup$ – David Richerby Aug 4 '15 at 7:48

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.