MHB Proving Regularity of $L^R$ Using DFA Construction

[evinda]

Hello! (Wave)

I want to prove that if $L$ is regular then $L^R=\{ w | w^R \in L \}$ is regular.

I have thought the following:

We suppose that $L$ is regular. Then there is a dfa that recognizes $L$.
Assume that $q_0$ is the starting state and $q_n$ is an accepting state, where $n \in \mathbb{N}$.
Taking as $q_n$ the starting state and as $q_0$ the accepting state, we get a dfa that recognizes $L^R=\{ w | w^R \in L \}$. So $L^R=\{ w | w^R \in L \}$ is also regular.

Is my idea right?

 

[evinda]

I have found the following:

Since $L$ is regular , there is a finite automaton $M=(Q, \Sigma, \delta, q_0, F)$ that recognizes it.

In order to show that $L^R$ is regular, we have to show that there is a finite automaton $N=(Q', \Sigma, \delta', q_0', F')$ that recognizes it.

For the automaton $N$ we have:

$Q'$: the set of all the subsets of the states of $M$,

$q_0'$: the set that contains all the final states of $M$,

$F'=\{ q_0 \}$,

$\delta'$: if there is a transition $r \in \delta(q,a), a \in \Sigma$ in $M$ then we will have $q \in \delta'(r,a)$ in $N$.Thus $N$ recognizes the language $L^R$, $L^R$ is regular.Could you explain to me why it has to hold that $Q'=\mathcal{P}(Q)$? (Thinking)

Also why do we define the transition function of $N$ as follows?

$\delta'$: if there is a transition $r \in \delta(q,a), a \in \Sigma$ in $M$ then we will have $q \in \delta'(r,a)$ in $N$.

 

[I like Serena]

Hey evinda!

What is $w^R$? (Wondering)

 

[Evgeny.Makarov]

We suppose that $L$ is regular. Then there is a dfa that recognizes $L$.
Assume that $q_0$ is the starting state and $q_n$ is an accepting state, where $n \in \mathbb{N}$.

A DFA can have several accepting states.

Taking as $q_n$ the starting state and as $q_0$ the accepting state, we get a dfa that recognizes $L^R=\{ w | w^R \in L \}$.

No need to reverse transitions?

Since $L$ is regular , there is a finite automaton $M=(Q, \Sigma, \delta, q_0, F)$ that recognizes it.

I assume it's a DFA, not an NFA.

Could you explain to me why it has to hold that $Q'=\mathcal{P}(Q)$?

It does not. The author of the proof chose to give this definition. Another person can give a different constructions for the automaton that accepts $L^R$ and come up with a different proof. Strictly speaking, questions about definitions are illegitimate. Only questions like "Why does something hold?" or "Why does this follow from that?" are legitimate.

That said, the idea behind the suggested proof is to reverse the transitions of the original automaton $M$. However, it may happen that $\delta(q,a)=q'$ for several $q$ and given $a$, $q'$. Therefore, we can't define $\delta'(q',a)=q$ because there are several $q$s to choose from. In other words, the automaton that acceots $L^R$ is nondeterministic in general. Therefore, this proof combines the idea of reversing transitions with converting the resulting NFA into a DFA, where the key idea is to consider sets of states of NFA as individual states of the DFA.

Another legitimate question is what to prove. Most of claims about finite automata is ultimately proved by induction, and induction often requires strengthening the inductive hypothesis. Coming up with such hypothesis may be nontrivial. Suppose that $\delta$ is extended from $Q\times\Sigma\to Q$ to $Q\times\Sigma^*\to Q$, and similarly for $\delta'$, in the natural way. Then one proves by induction on word length that
\[
\{q\in Q\mid\delta(q,w)\in F\}=\delta'(q_0',w^R)\text{ for all }w\in\Sigma^*.\qquad(*)
\]
I would also change the definitions of $F'$ and $\delta'$.
\[
F'=\{P\subseteq Q\mid q_0\in P\}\\
\delta'(P,a)=\{q\in Q\mid\delta(q,a)\in P\}
\]
Then the required statement is a corollary of (*).
\[
w\in L\iff\delta(q_0,w)\in F\overset{(*)}{\iff} q_0\in\delta'(q_0',w^R)\iff\delta'(q_0',w^R)\in F'\iff w^R\text{ is accepted by }M'
\]

But as I said, this proof basically repeats the proof of the theorem about the equivalence of NFAs and DFAs. It may be easier to start with a nondeterministic $M$. One can assume without loss of generality that an NFA has a single accepting state. Then we simply reverse the transitions.

Yet another way to prove that $L^R$ is regular is to construct a regular expression that describes $L^R$ from the one that describes $L$.

 

[evinda]

A DFA can have several accepting states.

No need to reverse transitions?

Oh yes, right...

It does not. The author of the proof chose to give this definition. Another person can give a different constructions for the automaton that accepts $L^R$ and come up with a different proof. Strictly speaking, questions about definitions are illegitimate. Only questions like "Why does something hold?" or "Why does this follow from that?" are legitimate.

That said, the idea behind the suggested proof is to reverse the transitions of the original automaton $M$. However, it may happen that $\delta(q,a)=q'$ for several $q$ and given $a$, $q'$. Therefore, we can't define $\delta'(q',a)=q$ because there are several $q$s to choose from. In other words, the automaton that acceots $L^R$ is nondeterministic in general. Therefore, this proof combines the idea of reversing transitions with converting the resulting NFA into a DFA, where the key idea is to consider sets of states of NFA as individual states of the DFA.

Another legitimate question is what to prove. Most of claims about finite automata is ultimately proved by induction, and induction often requires strengthening the inductive hypothesis. Coming up with such hypothesis may be nontrivial. Suppose that $\delta$ is extended from $Q\times\Sigma\to Q$ to $Q\times\Sigma^*\to Q$, and similarly for $\delta'$, in the natural way. Then one proves by induction on word length that
\[
\{q\in Q\mid\delta(q,w)\in F\}=\delta'(q_0',w^R)\text{ for all }w\in\Sigma^*.\qquad(*)
\]
I would also change the definitions of $F'$ and $\delta'$.
\[
F'=\{P\subseteq Q\mid q_0\in P\}\\
\delta'(P,a)=\{q\in Q\mid\delta(q,a)\in P\}
\]
Then the required statement is a corollary of (*).
\[
w\in L\iff\delta(q_0,w)\in F\overset{(*)}{\iff} q_0\in\delta'(q_0',w^R)\iff\delta'(q_0',w^R)\in F'\iff w^R\text{ is accepted by }M'
\]

But as I said, this proof basically repeats the proof of the theorem about the equivalence of NFAs and DFAs. It may be easier to start with a nondeterministic $M$. One can assume without loss of generality that an NFA has a single accepting state. Then we simply reverse the transitions.

I think that I got it...

Yet another way to prove that $L^R$ is regular is to construct a regular expression that describes $L^R$ from the one that describes $L$.

How can we do so although the regular expression that describes $L$ is not known?

- - - Updated - - -

Hey evinda!

What is $w^R$? (Wondering)

It's the reverse word of $w$...

 

[Evgeny.Makarov]

How can we do so although the regular expression that describes $L$ is not known?

You write in post #1: "We suppose that $L$ is regular. Then there is a dfa that recognizes $L$." Then you assume that the automaton $M$ recognizing $L$ is given, and you proceed to describe how to turn it into a different automaton $M'$. What prevents you from similarly writing "Then there is a regular expression that describes $L$" and treating this regular expression as given?

 

[evinda]

You write in post #1: "We suppose that $L$ is regular. Then there is a dfa that recognizes $L$." Then you assume that the automaton $M$ recognizing $L$ is given, and you proceed to describe how to turn it into a different automaton $M'$. What prevents you from similarly writing "Then there is a regular expression that describes $L$" and treating this regular expression as given?

Yes, that makes sense. (Smile)

So, we suppose that $L$ is regular. Then there is a regular expression that describes $L$. We have the following cases:

• $L \equiv \varnothing, \epsilon, a$ for some $a \in \Sigma$ or a singleton then $L^R=L$.
• $L=a_1 a_2 \dots a_{k}$ where $a_i \in \Sigma, i=1, \dots, k$ then $L^R=a_k a_{k-1} \dots a_2 a_1$.
• $L=R_1 \cup R_2$ for some sets $R_1, R_2$ then $L^R=R_1^R \cup R_2^R$.
• $L=R_1^{\ast}$ for some set $R_1$ then $L^R=(R_1^R)^{\ast}$

Is this complete? Or haven't I considered all the possible cases? (Thinking)

 

[Evgeny.Makarov]

You have not considered the case where $L=R_1R_2$ and $R_i$ are arbitrary regular expressions (and not simply symbols from $\Sigma$).

 

[evinda]

You have not considered the case where $L=R_1R_2$ and $R_i$ are arbitrary regular expressions (and not simply symbols from $\Sigma$).

If $L=R_1R_2$ where $R_i$ are arbitrary regular expressions then $L^R=R_2^R R_1^R$, right?
Could we not generalize the third and fourth case that I have written above and consider that $R_1$ and $R_2$ are arbitrary regular expressions? (Thinking)

 

[Evgeny.Makarov]

If $L=R_1R_2$ where $R_i$ are arbitrary regular expressions then $L^R=R_2^R R_1^R$, right?

Yes.

Could we not generalize the third and fourth case that I have written above and consider that $R_1$ and $R_2$ are arbitrary regular expressions?

I am not sure I understand your suggestion. Are you suggesting viewing $R_1$ and $R_2$ as arbitrary regular expressions or arguing against it? Then what are $R_i$?

 

[evinda]

I am not sure I understand your suggestion. Are you suggesting viewing $R_1$ and $R_2$ as arbitrary regular expressions or arguing against it? Then what are $R_i$?

I suggest viewing $R_1$ and $R_2$ as arbitrary regular expressions.
That's what I mean:

• $L=R_1 \cup R_2$ for some regular expressions $R_1, R_2$ then $L^R=R_1^R \cup R_2^R$.
• $L=R_1^{\ast}$ for some regular expression $R_1$ then $L^R=(R_1^R)^{\ast}$

 

[Evgeny.Makarov]

I suggest viewing $R_1$ and $R_2$ as arbitrary regular expressions.
That's what I mean:

• $L=R_1 \cup R_2$ for some regular expressions $R_1, R_2$ then $L^R=R_1^R \cup R_2^R$.
• $L=R_1^{\ast}$ for some regular expression $R_1$ then $L^R=(R_1^R)^{\ast}$

How is this different from https://driven2services.com/staging/mh/index.php?posts/88208/? Please describe clearly what you mean.

 

[evinda]

How is this different from https://driven2services.com/staging/mh/index.php?posts/88208/? Please describe clearly what you mean.

At the https://driven2services.com/staging/mh/index.php?posts/88208/ I considered that $R_1, R_2$ are sets but we should consider that they are arbitrary regular expressions. Shouldn't we?

 

[Evgeny.Makarov]

At the https://driven2services.com/staging/mh/index.php?posts/88208/ I considered that $R_1, R_2$ are sets but we should consider that they are arbitrary regular expressions

Yes. My suggestion in post #4 was:

Yet another way to prove that $L^R$ is regular is to construct a regular expression that describes $L^R$ from the one that describes $L$.

You define the function $(\cdot)^R$ by recursion on regular expressions.

 

[evinda]

You define the function $(\cdot)^R$ by recursion on regular expressions.

Isn't this the only way to construct a regular expression that describes $L^R$ from the one that describes $L$ ?Also I think that the one case that I mentioned, namely this one: $L=a_1 a_2 \dots a_{k}$ where $a_i \in \Sigma, i=1, \dots, k$ , is a subcase of $R_1 R_2$ where $R_1, R_2$ are regular expressions.

So I think it is complete as follows. Am I right?

We suppose that $L$ is regular. Then there is a regular expression that describes it. We distinguish the following cases.

• $L \equiv \varnothing, \epsilon, a$ for some $a \in \Sigma$ then $L^R=L$.
• $L=R_1 \cup R_2$ for some regular expressions $R_1, R_2$ then $L^R=R_1^R \cup R_2^R$.
• $L=R_1^{\ast}$ for some regular expression $R_1$ then $L^R=(R_1^R)^{\ast}$
• $L=R_1 R_2$ for some regular expressions $R_1, R_2$ then $L^R=R_2^R R_1^R$

Thus there is a regular expression that describes $L^R$ and so it is also regular.

 

[Evgeny.Makarov]

Isn't this the only way to construct a regular expression that describes $L^R$ from the one that describes $L$ ?

It's never the case that there is a single way to construct something.

Also I think that the one case that I mentioned, namely this one: $L=a_1 a_2 \dots a_{k}$ where $a_i \in \Sigma, i=1, \dots, k$ , is a subcase of $R_1 R_2$ where $R_1, R_2$ are regular expressions.

Yes, but I don't see how it occurred to you to consider concatenation of symbols. One of the cases in the definition of a regular expression is that $R_1R_2$ is a regular expression provided $R_i$ are. If you had followed the definition closely, it would have saved us ten unnecessary posts in this thread.

So I think it is complete as follows. Am I right?

We suppose that $L$ is regular. Then there is a regular expression that describes it. We distinguish the following cases.

• $L \equiv \varnothing, \epsilon, a$ for some $a \in \Sigma$ then $L^R=L$.
• $L=R_1 \cup R_2$ for some regular expressions $R_1, R_2$ then $L^R=R_1^R \cup R_2^R$.
• $L=R_1^{\ast}$ for some regular expression $R_1$ then $L^R=(R_1^R)^{\ast}$
• $L=R_1 R_2$ for some regular expressions $R_1, R_2$ then $L^R=R_2^R R_1^R$

Thus there is a regular expression that describes $L^R$ and so it is also regular.

I agree, though strictly speaking $L=R_1R_2$ is an abuse of notation. $L$ is a language and $R_1R_2$ is a regular expression describing this language. That said, one often writes a regular expression to mean the language that this expression describes, so it is usually acceptable.

 

[evinda]

It's never the case that there is a single way to construct something.

How else could we construct for example a regular expression describing $L^R$ ?

Yes, but I don't see how it occurred to you to consider concatenation of symbols. One of the cases in the definition of a regular expression is that $R_1R_2$ is a regular expression provided $R_i$ are. If you had followed the definition closely, it would have saved us ten unnecessary posts in this thread.

I am sorry...

I agree, though strictly speaking $L=R_1R_2$ is an abuse of notation. $L$ is a language and $R_1R_2$ is a regular expression describing this language. That said, one often writes a regular expression to mean the language that this expression describes, so it is usually acceptable.

I see... (Smile)

 

[Evgeny.Makarov]

How else could we construct for example a regular expression describing $L^R$ ?

For every computable mathematical function there is an infinite number of programs that compute this function. These programs may differ from each other in trivial or nontrivial ways. A trivial way is, for example, adding a non-reachable code. A nontrivial way may rely on a theorem that provides an equivalent condition. For example, one can establish that a natural number is composite by finding its nontrivial divisors through brute force, or one can use little Fermat's theorem.

In this case, it is possible to take a regular expression for $L$, convert it into a DFA, apply the construction described in post #4 to obtain a DFA that accepts $L^R$ and finally convert it to a regular expression describing $L^R$.

 

[evinda]

For every computable mathematical function there is an infinite number of programs that compute this function. These programs may differ from each other in trivial or nontrivial ways. A trivial way is, for example, adding a non-reachable code. A nontrivial way may rely on a theorem that provides an equivalent condition. For example, one can establish that a natural number is composite by finding its nontrivial divisors through brute force, or one can use little Fermat's theorem.

In this case, it is possible to take a regular expression for $L$, convert it into a DFA, apply the construction described in post #4 to obtain a DFA that accepts $L^R$ and finally convert it to a regular expression describing $L^R$.

I understand... Thanks a lot! (Smile)