Let $\Sigma = \{0,1\}$, and suppose that $A$ is a regular language. Define $$A' = \{ u \mid \exists a, b \in\Sigma: abu \in A\}$$ i.e., $A'$ is obtained from $A$ by taking every string in $A$ and removing its first 2 characters. Show that $A'$ is regular.

My solution so far is:

  • $ab \in \Sigma^*$ which is regular.
  • $A$ is a regular language
  • $abu ∈ A$, this means $u$ must be regular for all $abu \in A$ so $A'$ is regular.

Not sure if this makes sense, but please let me know if there's a better way, more formal.

Note: It's not an assignment, I'm just studying for my exam.


A word cannot be regular, only a language can be regular. So it's not clear what you mean by "$ab \in \Sigma^*$ which is regular", and even less what you mean by "$u$ must be regular for all $abu \in A$".

Given a DFA (or an NFA) $M$ for $A$, you can construct an NFA $M'$ for $A'$ as follows. Let $T$ be the set of states in which $M$ finds itself after reading some $ab \in \Sigma^*$ (so $1 \leq |T| \leq |\Sigma|^2$), in symbols $$T = \{ q(\sigma,ab) \mid a,b \in \Sigma \},$$ where $\sigma$ is the starting state of $M$ and $q$ is its transition function. Add to $M$ a new starting state $s$, and connect it to all sets in $T$ using $\epsilon$ productions. Hopefully you can see why the resulting automaton $M'$ accepts $A'$.

Here is a more difficult exercise for you to try. Show that if $A$ is regular then $\{u \mid abu \in A\text{ for a }\textit{unique}\text{ pair }a,b \in \Sigma\}$ is also regular.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.