# Context free grammar for $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$

I try to find a context free grammar for the language $$L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$$. There is a hint in the task that one should first construct the context free grammar for cases such as $$L_1 = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a > \vert v \vert_a\}$$ and later combine all of these.

I would appreciate a hint to come up with $$L_1$$. I do not know how construct $$u\#v$$ such that $$u$$ and $$v$$ are free independent from each other except of the fact that $$u$$ has more $$a$$'s than $$v$$. I tried to build my language around the $$\#$$ and also tried to move the $$\#$$ in the direction of the most appearing $$a$$'s but none of my attempts worked.

What is the proper way to tackle such constructions in general?

• @greybeard Thank you. I don't think it is nessecary to keep this discussion here, so I deleted the other comments. – Discrete lizard May 18 '20 at 10:46

I'll just show how to build a grammar for $$L_1 = \{ u\#v, |u|_a > |v|_a \}$$. Then it'll be straightforward to combine 4 similar grammars into a grammar for $$L$$.
The idea is to write $$u\#v$$ as $$xay\#v$$ with $$x,y,v \in \{a,b\}^*$$ and $$|y|_a = |v|_a$$. The construction of $$y\#v$$ is handled by the non-terminal $$Z$$ which "grows" it from the center.
\begin{align*} S &\to aS \mid bS \mid aZ \\ Z &\to bZ \mid Zb \mid aZa | \,\# \end{align*}
• Why? The part preceding $aZ$ can have any number of $a$s and $b$s. – Steven May 17 '20 at 8:13
• @greybeard Consider $S \Rightarrow bS \Rightarrow baS \Rightarrow baaS \Rightarrow baaaZ \Rightarrow baaaZb \Rightarrow baaa\#b$. Obviously $baaa$ does have $3$ $a$'s more than $b$. – Ludwig M May 17 '20 at 20:48