Question

The chopleft operation of a regular language L is removing the leftmost symbol of every string in L:

chopleft(L) = { w | vw ∈ L, with |v| = 1}.

Prove or disprove that the family of regular languages is closed under the chopleft operation.   

Hint: If it’s regular, give an idea of constructing an FA that accepts chopleft(L) using an FA M that accepts L.

Otherwise, give a counterexample.

Answer 1

Solution

• Given the language L is regular.
• chopleft (L) made by removing leftmost symbol for all strings in L.
• Since L is regular, there is a finite automata f, with initial state q_0, that accepts the strings in L.
• For all transitions from initial state q_0, replace the transition input symbol by epsilon.
  • For example, Let the transition in f from initial state q₀ is δ(q₀, 1) = q₁ δ(q₀, 0) = q₂
  • This transition can be replaced by δ(q₀, 1) = epsilon δ(q₀, 0) = epsilon
• This will remove the leftmost symbol of the string.
• The resulting finite automata f accepts all strings in L without leftmost symbol in strings.
• The language accepted by finite automata is regular.
• Therefore chopLeft (L) is also regular