Structural Induction Regular Expression Example

Problem

• For some string $x\in {\Sigma }^{\ast }$
• There exists $b(x)$ which represents $x$ in reverse
• Let $BW(L)$ be the set of all backwards strings of $L$
• For example, $L=\{\text{ark},\text{bone}\},BL=\{\text{kra},\text{enob}\}$
• Prove that if $L$ is regular, then $BW(L)$ is also regular

Solution

We prove with Proof by Structural Induction Define $B(R)$ as ‘There exists a $R^{\prime }$ s.t $BW(L(R^{\prime }))=\mathcal{L}(R^{\prime })$

Base Case

We show that $B(x)$ holds for $\varnothing ,ϵ,a$

1. Let $R=\varnothing ,R^{\prime }=\varnothing$
2. Let $R=ϵ,R^{\prime }=ϵ$
3. Let $R=a,R^{\prime }=a$

Induction Step

• Let $S,T\in \mathcal{R}\mathcal{E}$
• Suppose $B(S),B(T)$ IH
• This means $\exists S^{\prime },T^{\prime }$ s.t $\mathcal{L}(S^{\prime })=BW(\mathcal{L}(S))$ and $\mathcal{L}(T^{\prime })=BW(\mathcal{L}(T))$ We need to show 3 cases: $B(S+T)$, $B(ST)$, $B(S^{\ast })$
• Case 1: $R=S+T$
  • Then, $BW(\mathcal{L}(R))=BW(L(S+T))=BW(L(S))\cup BW(L(T))$
  • $=L(S^{\prime })+L(T^{\prime })$ by IH
  • $=L(S^{\prime }+T^{\prime })$ as $+$ order doesnt matter
  • $=L(R^{\prime })$
• Case 2: $R=ST$
  • Then, $BW(\mathcal{L}(R))=BW(\mathcal{L}(ST))=BW(\mathcal{L}(T))\cdot BW(\mathcal{L}(S))$ as swapping order of concatenation reverses the roder
  • $=\mathcal{L}(T^{\prime })\cdot \mathcal{L}(S^{\prime })$ by IH
  • $=\mathcal{L}(T^{\prime }{S}^{\prime })$
  • $=\mathcal{L}(R^{\prime })$
• Case 3: $R=S^{\ast }$
  • Then, $BW(\mathcal{L}(R))=BW(\mathcal{L}(R^{\ast }))=BW(\mathcal{L}(R{)}^{\ast })$ as order does not matter for $\ast$
  • $=L(S^{\prime }{)}^{\ast }$
  • $=L(S^{\prime \ast })$
  • $=\mathcal{L}(R^{\prime })$
• Then, by structural induction $B(R)$ holds $\forall R\in \mathcal{R}\mathcal{E}$