The Gateway to Computer Science Excellence

0 votes

We can generalize question $8$ to a number of functions that determine how much of the string we take.If $f$ is a function of integers, define $f(L)$ to be $\text{\{w| for some $x,$ with $|x|=f(|w|)$,we have $wx$ in L.\}}$ For instance,the operation $\text{half}$ corresponds to $f$ being the identity function $f(n)=n,$ since $\text{half(L)}$ is define by having $|x|=|w|.$Show that if $L$ is a regular language,then so is $f(L),$ if $f$ is one of the following function$:$

- $f(n)=2n(i.e.,$ take the first thirds of strings$).$
- $f(n)=n^{2}(i.e.,$ the amount we take has length equal to the square root of what we do not take.
- $f(n)=2^{n}(i.e,$ what we take has length equal to the logarithm of what we leave$).$

52,345 questions

60,521 answers

201,948 comments

95,368 users