# Unambiguous context-free grammar for strings with at least as many a's as b's

I have designed this Grammar but it is ambiguous:

$$S\to aSbS \mid bSaS \mid aS \mid\epsilon$$

Would anyone help me make it unambiguous? Assume the alphabet is $$\{a,b\}$$.

Let us replace $$a$$ with $$\nearrow$$ and $$b$$ with $$\searrow$$. Given a sequence of arrows, we construct a "walk" in which each arrow's tail starts from the preceding arrow's head. We keep track of the height. You are interested in walks which end up at or above the starting height.

Given such a walk $$w = w_1 \ldots w_n$$, let $$i \in \{0,\ldots,n\}$$ be the last position at which the walk reaches the starting height, and write $$w = (w_1 \ldots w_i) (w_{i+1} \ldots w_n) =: xy$$. The first part $$x$$ is a sequence with an equal number of $$\nearrow$$ and $$\searrow$$. The second part $$y$$ is either empty, or of the form $$y = \nearrow z$$, where $$z$$ is a walk that never dips below the starting height.

Let us start with $$x$$. We can partition $$x$$ into subwords $$x_1 \ldots x_\ell$$, breaking $$x$$ at each point in which the walk reaches the starting height. Each $$x_i$$ is of one of the following forms: $$\nearrow U \searrow$$, where $$U$$ is a walk that never dips below the starting height and returns to the origin, and $$\searrow D \nearrow$$, where $$D$$ is a walk that never exceeds the starting height and returns to the origin.

A walk of type $$U$$ is either empty, or must be of the form $$\nearrow U \searrow U$$, and similarly for a walk of type $$D$$. We can therefore express the $$x$$ part of our overall walk using the rules: \begin{align} &X \to \nearrow U \searrow X \mid \searrow D \nearrow X \mid \epsilon \\ &U \to \nearrow U \searrow U \mid \epsilon \\ &D \to \searrow D \nearrow D \mid \epsilon \end{align}

Now let's tackle the $$z$$ part, which is a walk that never dips below the starting height. Either $$z$$ ends up at the starting height, in which case it is of type $$U$$, or it is of the form $$U \nearrow z'$$, where $$z'$$ satisfies the exact same constraints. In other words, the $$y$$ part is just $$(\nearrow U)^*$$. In total, we get the grammar \begin{align} &S \to S \nearrow U \mid X \\ &X \to \nearrow U \searrow X \mid \searrow D \nearrow X \mid \epsilon \\ &U \to \nearrow U \searrow U \mid \epsilon \\ &D \to \searrow D \nearrow D \mid \epsilon \end{align}

Here is an unambiguous grammar for strings with at least as many $$a$$'s as $$b$$'s. $$\def\L#1{{\mathcal L(#1)}}$$

\begin{align} S&\to EM\mid E\\ M&\to aDM\mid aD\\ E&\to aBE\mid bAE\mid\epsilon\\ D&\to aBD\mid\epsilon\\ B&\to b\mid aBB\\ A&\to a\mid bAA\\ \end{align}

The following table should help us understand the strings generated by each non-terminal.

$$\text{number of a's minus number of b's}$$

$$\begin{array}{|c|c|} \hline &\text{in the whole string} & \text{in every proper prefix}\\\hline A&1& \lt 1\\\hline B&-1&\gt -1\\\hline D&0&\ge0\\\hline E&0&\text{no restriction}\\\hline M&\gt0&\gt0\\\hline S&\ge0&\text{no restriciton}\\\hline \end{array}$$

Some notations. For all string $$w$$, let $$d(w)=|w|_a-|w|_b$$, i.e., the number of $$a$$'s minus the number of $$b$$'s. Define $$d_w:\{1,\cdots, |w|-1\}\to \mathbb N$$, $$w(i)=d(p_i(w))$$, where $$p_i(w)$$ is the proper prefix of $$w$$ of length $$i$$. For example, for $$w=abb$$, \begin{align}d_w(1)&=d(a)=1 - 0=1,\\ d_w(2)&=d(ab)=1-1=0.\end{align}

Given a string $$w$$ and one of its prefixes $$p$$, let $$w-p$$ denote $$w$$ with $$p$$ removed, i.e. $$w = p(w-p)$$.

Continuity Lemma. $$d(\cdot)$$ is continuous in the sense that $$d(w)$$ changes at most by 1 if $$w$$ is extended or shrunk by one terminal. $$d_w(\cdot)$$ is continuous in the sense that $$d_w(i)$$ changes at most by 1 if $$i$$ becomes one less or bigger. So we have "intermediate value theorem" for $$d(\cdot)$$ and $$d_w(\cdot)$$.

Linearity Lemma. Given two strings $$p$$ and $$w$$, we have \begin{align}|w-p|&=|w|-|p|,\\ d_{w-p}(i) &= d_{w}(|p| +i) - d(|p|),\color{#d0d0d0}{\text{ for } i=1,2,\cdots, |w|-1} \end{align} Proof. By definition. $$\blacksquare$$

Proposition AB. We have two equivalences, \begin{align} w\in \L A &\iff d(w) =1\text{ and } d_w \lt 1,\\ w\in \L B &\iff d(w) =-1\text{ and } d_w \gt -1. \end{align} Proof: By induction on $$|w|$$, it is straightforward to establish the "$$\Rightarrow$$" implications.

Let us prove the "$$\Leftarrow"$$ implications by induction on $$|w|$$ as well. The base cases when $$|w|=1$$ are immediate to verify. Suppose $$w$$ is of greater length.

• $$d(w) =1\text{ and } d_w \lt 1$$. Since $$d_w(1)\lt 1$$, $$w$$ starts with $$b$$, i.e, the first value of $$d_w$$ is $$d(b)=-1$$. Since $$d(w)=1$$, $$d(p)=0$$ for some proper prefix $$p$$ of $$w$$. Let $$b\mu$$ be the shortest such prefix. Since $$d_\mu < 1$$, $$d(\mu)=d(b\mu)-d(b)=1$$, and $$\mu$$ is shorter than $$w$$, we have $$\mu\in \L A$$ by induction hypothesis.

Since $$d_w\lt 1$$ and $$d(a\mu)=0$$, $$d_{w-b\mu} \lt 1$$. Also note $$d(w-b\mu)=1-0=1$$. Since $$w-b\mu$$ is shorter than $$w$$, $$w-b\mu\in\L A$$ by induction hypothesis. So $$w=b\mu(w-b\mu)$$ can be generated from $$A\to bAA$$.

• $$d(w) = -1\text{ and } d_w \gt -1$$. This case is the same as the case above, but with $$-1$$ and $$1$$ switched, $$>$$ and $$<$$ switched, $$a$$ and $$b$$ switched, $$A$$ and $$B$$ switched. We obtain that $$w$$ can be generated from $$B\to aBB$$. $$\blacksquare$$

Proposition DE. We have two equivalences, \begin{align} w\in \L D &\iff d(w)=0\text{ and } d_w \gt 0,\\ w\in \L E &\iff d(w)=0. \end{align}

Proof: By induction on $$|w|$$, it is straightforward to establish the "$$\Rightarrow$$" implications.

Let us prove the "$$\Leftarrow"$$ implications by induction on $$|w|$$ as well. The base cases when $$|w|=0$$ are immediate to verify. Suppose $$w$$ is of greater length.

• $$d(w)=0$$ and $$d_w>0$$. Since $$d_w(1)>0$$, $$w$$ starts with $$a$$. Let $$a\mu$$ be the shortest non-empty prefix with $$d(a\mu)=0$$. Then $$d(\mu)=-1$$ and $$d_{\mu}\gt0$$, which means $$\mu\in\mathcal L(aB)$$. Since $$d(a\mu)=0$$, have $$d_{w-a\mu}\gt0$$. Since $$d(w-a\mu)=d(w)-d(a\mu)=0$$ and $$w-a\mu$$ is shorter than $$w$$, $$w-a\mu\in\L D$$ by induction hypothesis. The rule $$E\to aBE$$ tells that $$w=a\mu(w-a\mu)\in D$$.
• $$d(w)=0$$.
• $$w$$ starts with $$a$$. Let $$a\mu$$ be the shortest prefix of $$w$$ such that $$d(a\mu)=0$$. Then $$d(\mu)=-1$$ and $$d_\mu > -1$$, which means $$\mu\in \L B$$. Since $$d(w-a\mu)=d(w)-d(a\mu)=0$$ and $$w-a\mu$$ is shorter than $$w$$, $$w-a\mu\in\mathcal L(E)$$ by induction hypothesis. The rule $$E\to aBE$$ tells that $$w=a\mu(w-a\mu)\in E$$.
• $$w$$ starts with $$b$$. This case is the same as the case above, but with $$-1$$ and $$1$$ switched, $$>$$ and $$<$$ switched, $$a$$ and $$b$$ switched, $$A$$ and $$B$$ switched. We obtain that $$w\in E$$. $$\blacksquare$$

Proposition M. $$w\in \L M \iff d_w \ge 1$$.
Proof. The "$$\Rightarrow$$" direction is implied by the proposition above immediately since $$M$$ becomes multiple $$aD$$'s.
To prove the "$$\Leftarrow$$" direction, suppose $$d_w\ge1$$. Note that $$w$$ starts with $$a$$. Let $$p$$ be the longest prefix of $$w$$ such that $$d(p)=1$$, which implies $$d_{w-p}\ge1$$. Since we also have $$d_p\ge1$$, $$p\in\L U$$. If $$p=w$$, $$w$$ can be generated from $$M\to U$$. Otherwise, since $$w-p$$ has the same restriction as $$w$$, $$w$$ can be generated from $$M\to UM$$. $$\blacksquare$$.

Proposition S. $$w\in \L S \iff d(w) \ge 0.$$
Proof. The "$$\Rightarrow$$" direction is implied by proposition E and proposition M immediately.
To prove the "$$\Leftarrow$$" direction, consider a string $$w$$ with $$d(w)\ge0$$. If $$d(w)=0$$, then $$\mu\in\L E$$. Otherwise, $$d(w)>0$$. Let $$p$$ be the longest prefix of $$w$$ such that $$d(p)=0$$. Then $$p\in\mathcal L(E)$$. Consider $$w-p$$. We must have $$d_{w-p}\ge 1$$; otherwise, we can extend $$p$$. So $$w-p\in \mathcal L(M)$$. $$w=p(w-p)$$ can be generated by $$S\to EM$$. $$\blacksquare$$

Proposition unambiguity. The grammar is unambiguous.
Proof. Given the propositions above that characterize each language involved numerically, it is relative easy to prove as the following.

• Let $$s\in\L S$$.
• $$d(s)=0$$. Then $$s$$ has to be parsed by $$S\to E$$.
• $$d(s)\gt 0$$. Then $$s$$ has to be parsed by $$S\to EM$$. Suppose $$s=e_1m_1=e_2m_2$$, where $$e_1,e_2\in\L E$$ and $$m_1, m_2\in\L M$$. Since $$d_{m_1}>0$$, if $$m_2$$ is a proper suffix of $$m_1$$, i.e., $$m_1-m_2$$ is a proper prefix of $$m_1$$, we would have $$d(m_1-m_2)>0$$, which contradicts with $$d(m_1-m_2)=d(m_1)-d(m_2)=(d(s)-d(e_1))-(d(s)-d(e_2))=0$$. This contradiction means $$m_1$$ cannot be a proper suffix of $$m_1$$. By symmetry, $$m_2$$ cannot be a proper suffix of $$m_1$$, either. Hence, $$m_1=m_2$$ and $$e_1=e_2$$.
• Let $$m\in\L M$$.
• $$\min d_m=1$$. Then $$m$$ has to be parsed by $$M\to aD$$.
• $$\min d_m>1$$. Then $$m$$ has to be parsed by $$M\to aDM$$. Suppose $$m=ad_1m_1=ad_2m_2$$, where $$d_1,d_2\in\L D$$ and $$m_1, m_2\in\L M$$. Since $$d_{m_1}>0$$, if $$m_2$$ is a proper suffix of $$m_1$$, i.e., $$m_1-m_2$$ is a proper prefix of $$m_1$$, we would have $$d(m_1-m_2)>0$$, which contradicts with $$d(m_1-m_2)=d(m_1)-d(m_2)=(d(s)-d(ad_1))-(d(s)-d(ad_2))=0$$. This contradiction means $$m_1$$ cannot be a proper suffix of $$m_1$$. By symmetry, $$m_2$$ cannot be a proper suffix of $$m_1$$, either. Hence, $$d_1=d_2$$ and $$m_1=m_2$$.
• Let $$e\in\L E$$.
• $$|e|=0$$. Then $$e$$ has to be parsed by $$E\to \epsilon$$.
• $$|e|>0$$.
• $$e$$ starts with $$a$$. Then $$e$$ has to be parsed by $$E\to aBE$$. Suppose $$e=ab_1e_1=ab_2e_2$$, where $$b_1,b_2\in\L B$$ and $$e_1, e_2\in\L E$$. Since $$d_{b_1}>-1$$ and $$d(b_2)=-1$$, $$b_2$$ cannot be a proper prefix of $$b_1$$. By symmetry, $$b_1$$ cannot be a proper prefix of $$b_2$$, either. Hence, $$b_1=b_2$$ and $$e_1=e_2$$.
• $$e$$ starts with $$b$$. This case is symmetric to the case above.
• Let $$w\in\L D$$.
• $$|w|=0$$. Then $$w$$ has to be parsed by $$D\to \epsilon$$.
• $$|w|>0$$. Then $$w$$ has to be parsed by $$D\to aBD$$. Suppose $$w=ab_1q_1=ab_2q_2$$, where $$b_1,b_2\in\L B$$ and $$d_1, d_2\in\L D$$. Since $$d_{b_1}>-1$$ and $$d(b_2)=-1$$, $$b_2$$ cannot be a proper prefix of $$b_1$$. By symmetry, $$b_1$$ cannot be a proper prefix of $$b_2$$, either. Hence, $$b_1=b_2$$ and $$d_1=d_2$$.
• Let $$w\in\L B$$.
• $$|w|=1$$. Then $$w$$ has to be parsed by $$B\to b$$.
• $$|w|>1$$. Then $$w$$ has to be parsed by $$B\to aBB$$. Suppose $$w=ab_1b_3=ab_2b_4$$, where $$b_1,b_2,b_3,b_4\in\L B$$. Since $$d_{b_1}>-1$$ and $$d(b_2)=-1$$, $$b_2$$ cannot be a proper prefix of $$b_1$$. By symmetry, $$b_1$$ cannot be a proper prefix of $$b_2$$, either. Hence, $$b_1=b_2$$ and $$b_3=b_4$$.
• Let $$w\in\L A$$. This case is symmetric to the case above. $$\blacksquare$$

Here is a simpler unambiguous grammar given by Yuval. \begin{align} S&\to SaU \mid X\\ X&\to aUbX\mid bDaX\mid\epsilon\\ D&\to bDaD\mid\epsilon\\ U&\to aUbU\mid\epsilon\\ \end{align}

Here is the numerical characterization for the language generated by each terminal. Check his answer for visual explanations. $$\text{number of a's minus number of b's}$$ $$\begin{array}{|c|c|} \hline &\text{in the whole string} & \text{in every proper prefix}\\\hline S&\ge0&\text{no restriciton}\\\hline X&0&\text{no restriciton}\\\hline U&0&\ge0\\\hline D&0&\le0\\\hline \end{array}$$

• Perhaps you should explain why your grammar works, possibly even a proof. This way there’s a higher chance you’ll get it right. – Yuval Filmus May 11 '20 at 18:41
• The comment above are outdated now. They had been great. – John L. May 13 '20 at 21:32