I am a self taught software developer and i came to a problem which i can not solve , can you please help me find the context free language of this language?
Thank you .
Here is the example , i am trying to find the context free gramar.
$$\{w\in \{a,b\}^+\mid|w|_a = |w|_b+1\}$$
In the comments, saulspatz referenced a very useful question https://cs.stackexchange.com/questions/22729/defining-a-context-free-grammar-for-w-in-0-1-0w-1w. BinyaminR also provided a solution, but I think there are some things that can be improved or corrected. Using this information, I propose the following rules: $$S\rightarrow S'aS' \\ S'\rightarrow aS'bS' \\ S'\rightarrow bS'aS' \\ S'\rightarrow\varepsilon$$ Using the referenced question, we can check that the language generated from $S'$ is $\{w\mid|w|_a=|w|_b\}$ (This is non trivial). In order to prove that our CFG produces $L_0:=\{w\mid|w|_a=|w|_b+1\}$, we can once again proceed by double inclusion.
Denote by $L$ the language produced by our CFG. If $w\in L$, then $w$ is of the form $uau'$ where $u$ and $u'$ have the same number of $a$ and $b$. Therefore $w\in L_0$. Therefore, $L\subseteq L_0$.
Conversely, let $w\in L_0$, and let $n=|w|$. Denote by $w_{\leq k}$ the first $k$ letters of $w$, and $f(k):=|w_{\leq k}|_a-|w_{\leq k}|_b$. Then $$\forall k\in\{1,\ldots,n-1\},\quad f(k+1)=f(k)\pm1,$$ depending on if the $(k+1)^\text{th}$ letter is an $a$ or a $b$. Thus $f$ increments by $\pm1$. Since $f(0)=0$ and $f(n)=1$, there must exist $k\geq1$ where $f(k)=0$ and $f(k+1)=1$, i.e. the $(k+1)^\text{th}$ letter of $w$ is an $a$, and $|w_{\leq k}|_a=|w_{\leq k}|_b$. Therefore we can write $$w=w_{\leq k}aw',$$ where $w'$ is just the rest of the word. We calculate that $|w'|_a=|w'|_b$ as well, so $w_{\leq k}$ and $w'$ are both produced by $S'$, so $w$ is produced by $S$, so $w\in L$. Therefore, $L_0\subseteq L$.
Thus, by double inclusion, $L=L_0$.
Sorry it's a bit long ^^ for future reference, these kinds of questions about formal languages are probably more appropriate in the CS StackExchange.