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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,491 answers

195,437 comments

100,670 users