A problem maybe related to pattern-matching

Question

Let $\Sigma_{1}=\{a,b\}$ and $\Sigma_{2}=\{t,f\}$.

Define the function $f_{w}:\Sigma_{1}^{*}\rightarrow\Sigma_{2}^{*}$ for every $w\in\Sigma_{1}^{*}$; $f_{w}(w')\in\Sigma_{2}^{*}$ is the word obtained from $w'\in\Sigma_{1}^{*}$ by replacing the start position of each subword that matches $w$ with $t$ and any other position with $f$.

I meant;

$f_{w}(w')=x_{1}...x_{|w'|}$;

here

$\exists(u,v)\in\Sigma_{1}^{*}\times\Sigma_{1}^{*}[w'=uwv\wedge|u|=i-1]\Rightarrow x_{i}=t$ $\neg\exists (u,v)\in\Sigma_{1}^{*}\times\Sigma_{1}^{*}[w'=uwv\wedge|u|=i-1]\Rightarrow x_{i}=f$

for every $i\in\{1,...,|w|\}$.

Also, define the function $f_{w}^{*}:P(\Sigma_{1}^{*})\rightarrow P(\Sigma_{2}^{*})$ for every $w\in\Sigma_{1}^{*}$; $f_{w}^{*}(L):=\{f_{w}(w')|w'\in L\}$.

I want to know whether each of the assumptions below is true or not;

1. For every $w\in\Sigma_{1}^{*}$ satisfying $|w|>0$; $L$ is a regular language $\Rightarrow$ $L'$ is a regular language.
2. For every $w\in\Sigma_{1}^{*}$; $L$ is a context-free language $\Rightarrow$ $L'$ is a context-free language.

Answer 1

Yes, both assumptions are true.

Your pattern matching operation can be performed by a finite state automaton with output, a finite state transducer. Keep the last $|w|$ read symbols in memory, and output $t,f$ accordingly. (And at the end affix some $f$'s.)

This closure property of the regular and context-free languages is not well known. It is equivalent to closure under (inverse) homomorphisms and under intersection with regular languages. Part of the theory abstract family of languages.

Transducers can be decomposed into inverse morphism, intersection with regular languages, and morphism. So if you are not familiar with the transducer instead you can apply those three closure properties.

Here we go. Starting with an alphabet $\Sigma$ and a string $w$ of length $n$, we make a large new alphabet $\Sigma^n$ consisting of all $n$-sequences of letters.

The morphism $g: \Sigma^n\to \Sigma$ maps a sequence to its first letter: $g([\sigma_1\sigma_2\dots\sigma_n]) =\sigma_1$. The inverse morphism $g^{-1}$ nondeterministically assigns a sequence to every letter with matching first symbol.

The regular language $R$ over $\Sigma^n$ consists of all strings where the consecutive sequences overlap. Thus $[\sigma_1\sigma_2\dots\sigma_n][\sigma_2\dots\sigma_n\sigma_{n+1}]$ must be consecutive.

The morphism $h:\Sigma^n\to \{t,f\}$ assigns $[\sigma_1\sigma_2\dots\sigma_n]$ to $t$ if $\sigma_1\sigma_2\dots\sigma_n = w$ and $f$ otherwise.

If you apply $g^{-1}$, intersection with $R$, and finally $h$ to the original language $L$, you will obtain your pattern language $L'$.