Cheap and Secure Web Hosting Provider : See Now

[Answers] How to Trace Path in Proof that Regular Languages are Closed Under Reversal

, , No Comments
Problem Detail: 

I'm self studying automata theory and I need help with proving that regular languages are closed under reversal.

I have a basic proof, but am unsure about last statement in my proof. Is this sufficient? Could you help me explain why it works? Is it rigorous enough?

Problem: For any string $w=w_1w_2\cdots w_n$, the reverse of $w$, written $w^\mathcal{R}$, is the string $w$ in reverse order, $w_n\cdots w_2w_1$. For any language $A$, let $A^\mathcal{R} = \{w^\mathcal{R} | w \in A \}$. Show that if $A$ is regular, so is $A^\mathcal{R}$.

Proof: Let $N = (Q, \Sigma, \delta, q_0, F)$ be an DFA recognizing $A$. We construct an NFA $M = (Q', \Sigma, \delta', q_0', F')$. Let $Q' = \mathcal{P}(Q) \cup \{q'_0\}$. For this NFA, $q'_0$ is a new start state. Let $F' = \{q_0\}$, the start state of $N$.

Define $\delta'$ so that for any $q \in Q'$ and any $a \in \Sigma_\epsilon$, \begin{equation*} \delta'(q,a) = \begin{cases} F & q = q'_0, a = \epsilon\\ q'_0 & q = q'_0, a \neq \epsilon\\ \{ x | x \in Q\ and\ \delta(x,a) = q \}&q \neq q'_0 \end{cases} \end{equation*}

For any $w \in \Sigma^*$, there is a path from $q_0$ to $q_{acc} \in F$ in $N$ if there is a path following $w^\mathcal{R}$ from $q'_0$ to $q_0$. Therefore, $w^\mathcal{R} \in A^\mathcal{R}$ iff $w \in A$.

Asked By : Srinivas Vasudevan

Answered By : Peter Leupold

Whether a proof is sufficiently detailed is in part a question of taste. Your last statement is very general and with little detail. A more detailed argumentation could be like this:

  • Let the path from $q_0$ to $q_{acc}$ go through the sequence of states $q_0 -> q_1 -> ... -> q_{n-2} -> q_{n-1} -> q_{acc}$.
  • Transition $q_{n-1} -> q_{acc}$ reads the letter $w[n]$ (w has length n) which is equal to $w^R[1]$. According to the third clause in the definition of $\delta'$ there is a transition $\delta'(q_{acc},w[1]) = q_{n-1}$ which can start a path for $w^R$ in M.
  • Now you can continue by induction or by simply stating that the same is true for every transition in the path for $w$. At any rate, since your construction is on the level of transitions, your argumentation should go down to the level of transitions somewhere and not stop at the level of paths.
Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback