[Math] Recursive definition of a set of strings.

discrete mathematics

Need assistant with this problem, Assume that
$\Sigma=\{a,b\}$. Give a recursive definition of the set $E_a$ of
all the strings $x\in\Sigma^*$ such that all the symbols occurring
at the even positions in $x$ are equal to $a$. I know that Base case $\lambda$ $ \epsilon$ $ \Sigma^* $ but where should I go from there.

Best Answer

You can describe $E_a$ using the regular expression $(aa+ba)^*(a+b+\lambda)$, which translates into a recursive definition with

  • Base case: $\lambda, a, b\in E_a$
  • Recursive case: if $w\in E_a$, then $aaw, baw\in E_a$.
Related Question