Cheap and Secure Web Hosting Provider : See Now

[Answers] Showing that A' is a regular language

, , No Comments
Problem Detail: 

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.

Asked By : moenad

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/31921

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback