How do you write a recursive definition for the language ODDnotBB over the alphabet $\Sigma=\{a,b\}$ where ODDnotBB consists of all words that are odd length and that do not contain the bb-substring?
So far I have my answer as follow:
Base Case:
$aba\in ODDnotBB$
Recursive Case:
If $x \in ODDnotBB,\;then\;CONCAT(x,\;aa),\;CONCAT(x,\;ab),\;CONCAT(x,\;ba),\;CONCAT(aa,\;x),\;CONCAT(ab,\;x)\;and\;CONCAT(ba,\;x) \in ODDnotBB$
Bounding Clause:
There are no other words in ODDnotBB
Notes:
- CONCAT is a function that is allowed to generate new words. It concatenates the two words found in its parameters.
- I'm not sure about my generator; there might be more that I'm not thinking about.
- I generated some words with this algorithm and it works. I'm just not sure if there might be more words by adding more generators.
I'll appreciate if you will correct my mistakes; fill in the blanks. Thanks.
Your system would falsely place $abaabba$ in ODDnotBB and would fail to place the string $a$ in ODDnotBB.
Instead, ODDnotBB can be defined by the string rewriting system $x\rightarrow axa, x\rightarrow xab, x\rightarrow bax$ with the initial strings $a$, $b$.
Or, in your notation:
Base cases:
$a\in$ ODDnotBB, $b\in$ ODDnotBB.
Recursive cases:
$\text{If } x\in \text{ ODDnotBB then }\text{CONCAT}(a,\text{CONCAT}(x,a)), \text{CONCAT}(x,ab) \text{ and } \text{CONCAT}(ba,x) \in$ ODDnotBB
It should be obvious that every string produced by this recursion is of odd length and does not contain the substring $bb$. To prove the other direction, note that, for every string $y$ in ODDnotBB, either both the first and last letters of $y$ are $a$ so that $y=axa$ for some $x$ in ODDnotBB, or the first letter of $y$ is $b$ so that $y=bax$, or the last letter of $y$ is $b$ so that $y=xab$.