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$:$

  1. $f(n)=2n(i.e.,$ take the first thirds of strings$).$
  2. $f(n)=n^{2}(i.e.,$ the amount we take has length equal to the square root of what we do not take.
  3. $f(n)=2^{n}(i.e,$ what we take has length equal to the logarithm of what we leave$).$
in Theory of Computation by
edited by | 25 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,521 answers
95,368 users