2

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$

Chris
  • 521
  • 2
    Yep, looks correct and intuitive. – Dan Shved Mar 18 '14 at 10:32
  • 2
    From a programmer's perspective, an even cleaner way may be $S \to 0 | CSC, C \to 0|1$. It reads literally as "$C$ stands for an arbitrary terminal character", "0 is in the language", and "whenever something is in the language, you can add two arbitrary characters on both ends to get another word in the language". – Dan Shved Mar 18 '14 at 10:37
  • I like that even better.. it is much cleaner indeed – Chris Mar 18 '14 at 10:41

1 Answers1

1

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.

João Víctor Melo
  • 424