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'$.

• Tigerion: Thank you for sharing your knowledge! I have never seen that machine and property, and descriptions about Cone are very hard to find in my language on the Web. So the knowledge is very informative. Welterusten (^^)/
• Hendrik Jan: As wikipedia states, the notion "cone" is also called "full trio", depending on the French or American sources. Most of the theory was developed in the days of the typewriter, so long before the web.
• Hendrik Jan: Oops. The construction does not work for the last $n-1$ letters. There no match can be found, but the construction still generates sequences. A solution would be to have special end-symbols, and include those in $g, R$ and $h$.