5
$\begingroup$

I wonder whether the following language is a context free language: $$A = \{w \in \{a,b,c\}^* \mid \#_a(w) + 2\#_b(w) = 3\#c(w)\}$$ where $\#_x(w)$ is the number of occurrences of $x$ in $w$. I can't find any word that would be useful to refute by the pumping lemma, on the other hand I haven't been able to find a context free grammar generating it. It looks like it has to remember more than one PDA can handle.

What do you say?

Improve this question
$\endgroup$
3
  • $\begingroup$ Is the # meant to be part of the alphabet or is it a separate symbol? What does it mean to add #a and 2#b? $\endgroup$
    – Sam Jones
    Commented Apr 28, 2012 at 21:51
  • 2
    $\begingroup$ In eastern Europe # is used to mean number of so #a should mean number of times the symbol a is present $\endgroup$
    – Vitaly Olegovitch
    Commented Apr 28, 2012 at 21:53
  • $\begingroup$ That's a nice question. It is tempting to say $A = \{w \mid |w|_a = |w|_b = |w_c|\}$ which is not context-free (by intersection with $a^*b^*c^*$ and the canonical $\{a^nb^nc^n \mid n \in \mathbb{N}\}$). $\endgroup$
    – Raphael
    Commented May 9, 2012 at 8:57

2 Answers 2

Reset to default
10
$\begingroup$

Yes, $A$ is a CFL. Use the context free language (with the notation $|x|_0$ meaning what you have as #0's in $x$):

$B=\{x\in \{0,1\}^*:3\cdot|x|_0=|x|_1\}$

and the morphism $f:\{a,b,c\}^*\rightarrow\{0,1\}^*:$ $ f(a)=0, f(b)=00, f(c)=1$

so that

$A=f^{-1}(B)$.

Since the CFL's are closed under inverse morphism, $A$ is a CFL.

The proof that $B$ is a CFL is a bit tricky. Let's do it for the simpler case $C=\{x:|x|_0=|x|_1\}$, which can fairly easily be generalized to work for $B$ (or use another morphism).

Design a PDA which keeps track of $|x|_0-|x|_1$ at all points of the input, using the stack to keep track of the difference, having read $x$. The PDA accepts only when that difference is zero, that is, the stack is empty. The idea is to push a $0$ on seeing a $0$ on the input string, and pop a $0$ when seeing a $1$ in the input. The problem is that difference might go negative at times, and you can't pop an empty stack. In that case, however, the PDA goes into another mode (a different set of states) where it pushes a $1$ on seeing an input of $1$ and pops a $1$ on seeing an input of $0$. So the second mode handles the negative case. It alternates between the two modes, accepting only if the stack if totally empty, that is, in-between the modes.

Or, you can do it with the grammar: $S\rightarrow 0S1|1S0|SS|\epsilon$. That clearly generates only strings of C, but proving that it generates all of $C$ is a bit involved, but here's a sketch, by induction on string length.

An isosymbolic string $x$ (that is $|x|_0 = |x|_1$) could be null, in which case the $\epsilon$ production applies giving the basis of the induction. Otherwise $x$ either starts and ends in different symbols (one end $0$ and the other end $1$), or the same symbol (both $0$ or both $1$). In the not-equal case, the last production to apply is either the $0S1$ or the $1S0$ production, allowing us to strip off the first and last symbols, getting a shorter isosymbolic string, so the induction applies.

In the equal case, as with the PDA, we keep track of $|y|_0-|y|_1$ as we move from left to right through prefixes $y$ of $x$. If the first and last symbols of $x$ are the same, it's fairly easy to see that that expression must be zero somewhere in the interior of the string. For example, if $x$ starts and ends with $0$, then after the first symbol the difference is $+1$ and before the last symbol it is $-1$, so it must have crossed zero in the interior. Split the string in two at that spot (reversing the $SS$ production) and the two halves, both shorter than $x$, are both isosymbolic. So the induction works there too, and we are done.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ It's not too difficult to see that the PDA accepting $B$ can be modified to accept $A$. It simply pushes one stack symbol when it sees $a$'s, two symbols when it sees $b$'s and pops three symbols when it sees $c$'s. Again, one has to be careful when the difference becomes negative. We also have only used one stack symbol here so the language is, in fact, a one-counter language (the one-counter languages are a strict subset of the context-free languages). $\endgroup$
    – Sam Jones
    Commented Apr 28, 2012 at 22:49
  • 1
    $\begingroup$ @Sam Jones -- Absolutely correct. But (a) the result about $C$ is fairly well known, so most of the work is done if you accept it as a basic result (I included the proof sketch just for completeness); (b) Proving things about formal languages with morphisms (and transducers, relations, etc) is not only neat and often quite efficient, it's the basis of a very general algebraic theory, that stands in relation to automata and grammars much the way usual algebra relates to geometry. So it's worthwhile building those muscles. $\endgroup$
    – David Lewis
    Commented Apr 29, 2012 at 1:04
  • $\begingroup$ I couldn't agree more. $\endgroup$
    – Sam Jones
    Commented Apr 29, 2012 at 11:11
  • $\begingroup$ Great approach. But why did you not use another morphism, as you suggest in your answer, i.e., mapping to $C$ by having $f(c) = 111$ instead? $\endgroup$
    – Hendrik Jan
    Commented Dec 22, 2012 at 12:04
7
$\begingroup$

All an automaton has to remember is the balance of the equation: $\#_a + 2 \#_b - 3 \#c$. It can do this by maintaining a unary counter on the stack, using two symbols - and +:

  • On encountering $a$, pop - if possible, otherwise push +.
  • On encountering $b$, pop two - if possible, otherwise pop - and push + if possible, otherwise push ++.
  • On encountering $c$, pop three + if possible, or pop ++ and push -, or pop + and push --, or push --- (so that there is never both a + and a - on the stack).

The automaton accepts the input only if the stack is empty.

To build a grammar, decompose each word in $A$ into disconnected groups such that the letter that pushes a symbol is grouped with the letter that pops it. (“Group” is to be taken in the intuitive sense, this has nothing to do with the mathematical concept.) For example (each color represents a different group):
$\quad \color{red}{aa}\color{blue}{abc}\color{red}{ca}\color{magenta}{cab} $
$\quad \color{red}{b}\color{blue}{abc}\color{red}{ac}\color{magenta}{acaa} $
$\quad \color{red}{a}\color{blue}{abc}\color{red}{cacaab} $
$\quad \color{red}{b}\color{blue}{abc}\color{red}{cb}\color{magenta}{cab}\color{red}{aca} $
$\quad \color{red}{bcbcb} $

Between the elements of a group, what you have is an element of $A$ (since it brings the balance back to where it was). Furthermore, there are only a finite number of possible groups if you decompose as much as possible, because the length of each group is at most the least common multiple of the coefficients of the equation ($\mathrm{lcm}(1,2,3)=6$): if there was a longer group, you could find a decomposable subgroup inside it. This leads to the following grammar, which expresses that a word in $A$ is the group that it starts with with words in $A$ interspersed at any point:

$$\begin{align*} S ::=& \epsilon \\ |& a \,S\, a \,S\, a \,S\, c \,S\, \\ |& a \,S\, b \,S\, c \,S\, \\ |& b \,S\, b \,S\, b \,S\, c \,S\, c \,S\, \\ |& b \,S\, a \,S\, c \,S\, \\ |& \ldots & \text{(all permutations of \(a,b,c\) above)} \\ \end{align*}$$

This approach generalizes to any (one) linear equation between the number of occurrences of various letters.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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