I need to find a CFG where the word length $|w|$ is odd. Plus there must be a $0$ in the middle.
In a previous exercise I had to specify a CFG only for odd word length. I chose the following:
$G = (\{A,B\},\{0,1\},P,A)$
$P =\{A \to 1B \mid 0B, B \to 11B \mid 00B \mid 01B \mid 10B \mid \epsilon \}$
But with $0$ in the middle I have to make sure that I add the same amount of symbols on each side. How could I manage that? I was maybe thinking of a pushdown automata which keeps track of the symbols on each side..
any hints I could use?
EDIT: I may have found a solution. Could this work? $A \to 0A0 \mid 1A1 \mid 1A0 \mid 0A1 \mid 0$
Best Answer
We want to find the following set $S = \{w \mid \text{the length of $w$ is odd and its middle symbol is a 0}\}$, but first we will considerer just as being odd, and we have the grammar:
$S \to 0 \mid 1 \mid 0S0\mid 0S1 \mid 1S0 \mid 1S1$
obs.: | stands for "or" (meaning a choice)
we can see that both $0$ and $1$ have length 1 which is odd. The same happens if we analyse the $0S0 = {000,010, 0(0S0)0 = 00000, 00100, ...}$, if we continue it will always have an odd number. This happens because once we pick a rule, it will have 1 or three symbols, each time we pick another, we will add always odd number and subtract 1 which is the symbol to be replaced.
But, since a $1$ (which is a terminal) can't ever appear in the middle, we take it out of the rules, obtaining:
$S \to 0 \mid 0S0\mid 0S1 \mid 1S0 \mid 1S1$
By recurrence we can see that $0$ is always in the middle, since $S$ is always in the middle, and in the last chance we have to replace, replace it with a zero, which is the middle symbol.