Closure property of regular language

Question

I am trying to prove the closure property of regular language with a function $f(w)$ over alphabet $\Sigma$ for any string $w \in \Sigma^*$.

$f(w) =$ string obtained by taking symbols of $w$ at even position (ex. $f(aabbaa) = aba$).

I define $$ f(L) = \{ f(w) \mid w ∈ L \} $$

I am trying to prove that for any regular language $L$, $f(L)$ is also regular.

I am a little confused on how to prove this. What I am thinking is to create a NFA that would skip every other string through empty string progression but not sure how to define this mathematically. Any help is appreciated

Answer 1

I'm not sure what you mean by "skip every other string", however, I assume that you want to build an NFA with $\epsilon$-transitions.

You can generate a new NFA with $\epsilon$-transitions accepting your modified language as follows. For each state $q$ of your NFA, create two states in your modified NFA: one corresponding to "original" $q$, and one "phantom state" $q^\prime$. For each transition labelled by symbol $s$ from state $a$ to $b$ in the original NFA, generate an $\epsilon$-transition from $a$ to $b^\prime$ and a transition labelled by $s$ from $a^\prime$ to $b$.

This results in a bipartite graph, and your NFA now jumps to the "phantom"-half of the graph in every second step, essentially skipping all the characters that were on the odd positions in the original string. Now, one should be able to verify that this NFA accepts the new modified language by the obvious induction.

Answer 2

I am trying to prove the closure property of regular language with a function f(w) over alphabet Σ for any string w ∈ Σ∗.

I expect that closure property to hold only for certain mappings. Wikipedia lists string homomorphisms (replace characters with words), inverse string homomorphisms (seem to replace words with characters) and finite state transducers (seem to replace words with words).

$f(w)$ = string obtained by taking symbols of $w$ at even position, ex. $f(aabbaa) = aba$.

This kind of function acts on position, IMHO in general it can not be implemented by a finite list of input strings to be replaced with some output strings.

I define

f(w) = { f(w): w ∈ L }

Do you mean $f(L)$?

Answer 3

Use closure properties of regular languages. Define the new alphabet $\Gamma = \Sigma \cup \{\chi\}$, where $\chi \notin \Sigma$. The languages $L_a = \{a, \chi\}$ are finite, thus regular. So the substitution defined by $s(a) = L_a$ applied to your language $L$ gives a regular language. Intersecting that with $((a \mid b \mid \ldots) \chi)^*$ gives a regular language. Use the homomorphism: $$h(x) = \begin{cases} x & x \ne \chi \\ \epsilon & x = \chi \end{cases}$$ The result of the homomorphism is what you want:

$$f(L) = h(s(L) \cap ((a \mid b \mid \ldots) \chi)^*)$$

Each step preserves regularity, thus the result is regular.