patternMinor
Context free grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$
Viewed 0 times
freetextgrammarforcontext
Problem
I'm trying to find a grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$, which is proving to be tricky.
I know that $L_2 = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b\}$ has the following one, so I have been trying to modify it so that I "force" to have one more $b$, but I don't see how to do this. The obvious choice would be to replace $\epsilon$ with $b$, but that would potentially get two more $b$'s. Is there a trick for this one?
$$\begin{align}
S &\to \epsilon \\
S &\to aSbS \\
S &\to bSaS \enspace.
\end{align}$$
I know that $L_2 = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b\}$ has the following one, so I have been trying to modify it so that I "force" to have one more $b$, but I don't see how to do this. The obvious choice would be to replace $\epsilon$ with $b$, but that would potentially get two more $b$'s. Is there a trick for this one?
$$\begin{align}
S &\to \epsilon \\
S &\to aSbS \\
S &\to bSaS \enspace.
\end{align}$$
Solution
You can simply consider the following grammar: $$ S\to S_1 b S_1$$ where $S_1$ is the start variable of a grammar for the language of words $w$ with $|w|_a = |w|_b$. Correctness is self-explanatory.
So using the grammar you wrote, you get the following grammar:
$$ S\to T b T$$
$$ T \to aTbT| bTaT | \epsilon$$
So using the grammar you wrote, you get the following grammar:
$$ S\to T b T$$
$$ T \to aTbT| bTaT | \epsilon$$
Context
StackExchange Computer Science Q#134868, answer score: 3
Revisions (0)
No revisions yet.