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.
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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$.
-
$\begingroup$ Would I not be able to get $ba\lambda \in E_a$, which has a $b$ as the second (i.e. an even position) letter? $\endgroup$– mrpFeb 18, 2015 at 14:50
-
$\begingroup$ But $ba$ ($\lambda$ being the empty string) has an a as its second letter... $\endgroup$ Feb 18, 2015 at 15:05
-
$\begingroup$ Ah yes, I was reversing things in my head. Good answer, +1. $\endgroup$– mrpFeb 18, 2015 at 15:09
$\begingroup$
$\endgroup$
0
Let $\varepsilon$ be the empty string, let $w*x$ be the concatenation of a symbol $x \in \Sigma$ and a string $w \in \Sigma^*$, and let $\lambda(w)$ be the length of a string $w \in \Sigma$ (this can be defined recursively as well, if you like).
Base case: $\varepsilon$ is in $E_a$.
Recursive case: If $w \in E_a$, then
- if $\lambda(w)$ is even, $w*a$ and $w*b$ are also in $E_a$, and
- if $\lambda(w)$ is odd, $w*a$ is also in $E_a$.
Is this a satisfactory answer?
