0
$\begingroup$

I need your assistance with a corner case of this problem:

Find a recursive definition for the strings of odd length that start with "a" and end with "b" over the alphabet $\Sigma$={a,b}.

I've already tried the following, but I can't get the string "aaaab", "aaaaaab, etc.:

Base case: aab,abb $\in$ L

Recursive step: If u$\in$L, then uab,ubb $\in$L.

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Your "recursive step" is not right, for a few reasons. You want to say that if $u$ is any string of odd length* then $aub\in L$, not just for strings $u\in L$. Try this grammar: $$\begin{align} S &\to aOb \\ O &\to COC \mid C \\ C &\to a \mid b \end{align}$$

$C\stackrel{*}\Longrightarrow$ the symbols of $\Sigma$, and $O\stackrel{*}\Longrightarrow$ all odd length strings in $\Sigma^*$. Finally, $S\stackrel{*}\Longrightarrow aub$ for every odd-length $u$ string in $\Sigma^*$.

$\endgroup$
2
  • $\begingroup$ Thank you very much! That cleared things up. $\endgroup$
    – David Manzanarez
    Jan 28, 2016 at 14:32
  • $\begingroup$ You're welcome. $\endgroup$
    – BrianO
    Jan 28, 2016 at 16:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .