Question

Do not use Pumping Lemma for Regular Expression to prove the following. You may think of Closure Properties of Regular Languages

1. Fix an alphabet. For any string w with |w| ≥ 2, let middle(w) be the string obtained by removing the first and last symbols of w. That is, Given L, a regular language on Σ, prove that f1(L) is regular, where

f1(L) = {w : middle(w) ∈ L}

Answer 1

Let, suppose that the alphabet is a. = {a}

So , the language L is given by { , a ,aa, aaa, aaaa, ..........................................} which is a regular language.

Now,

f1(L) represents the language whose words are formed by taking each word from L (length>=2) and stripping its first and last letters.

The first two words in L { , a } are not candidates to form a word in f1(L) because length is < 2.

The following words after are all candidates:

{ aa, aaa, aaaa, ..........................................}.

Now we begin forming the language f1(L) by taking input words from above and applying (stripping) operation

{ , a ,aa, ..........................................}

Note aa --->  ,  aaa ----> a, aaaa ----> aa and so on

Since this is an infinite series , the words formed are already present and same as in langugae L. So both the languages are actually same .

Since L is already proved to be regular, hence f1(L) is also regular.