Proving Regularity of $L^R$ Using DFA Construction

• MHB
• evinda
In summary, the conversation discusses the idea of proving that if a language $L$ is regular, then its reverse, denoted as $L^R$, is also regular. Two different approaches are suggested - one using deterministic finite automata and the other using regular expressions. The use of sets of states as individual states in the automaton for $L^R$ is explained, as well as the concept of extending the transition function to handle words instead of single characters. The conversation also touches on the topic of definitions and how different definitions can lead to different constructions and proofs.
evinda
Gold Member
MHB
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?

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$.

Hey evinda!

What is $w^R$? (Wondering)

evinda said:
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.

evinda said:
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?

evinda said:
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.

evinda said:
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$.

Evgeny.Makarov said:
A DFA can have several accepting states.

No need to reverse transitions?

Oh yes, right...

Evgeny.Makarov said:
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...

Evgeny.Makarov said:
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 - - -

I like Serena said:
Hey evinda!

What is $w^R$? (Wondering)

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

evinda said:
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?

Evgeny.Makarov said:
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)

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

Evgeny.Makarov said:
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)

evinda said:
If $L=R_1R_2$ where $R_i$ are arbitrary regular expressions then $L^R=R_2^R R_1^R$, right?
Yes.

evinda said:
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$?

Evgeny.Makarov said:
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}$

evinda said:
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.

Evgeny.Makarov said:
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?

evinda said:
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:
Evgeny.Makarov said:
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.

Evgeny.Makarov said:
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.

evinda said:
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.

evinda said:
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.

evinda said:
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.

Evgeny.Makarov said:
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$ ?
Evgeny.Makarov said:
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...

Evgeny.Makarov said:
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)

evinda said:
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$.

Last edited:
Evgeny.Makarov said:
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)

1. What does it mean for a language to be "regular"?

A regular language is a type of formal language that can be described by a finite automaton or a regular expression. In simpler terms, it means that the language can be recognized and accepted by a computer or machine.

2. How can you determine if a language is regular?

There are several methods for determining if a language is regular, including using a finite automaton, writing a regular expression, or using mathematical proofs such as the pumping lemma. These methods can help determine if a language can be recognized and accepted by a computer or machine.

3. Are all languages regular?

No, not all languages are regular. There are different types of formal languages, including regular, context-free, and context-sensitive languages. Each type has its own set of rules and properties, and not all languages can be described as regular.

4. What are some examples of regular languages?

Some common examples of regular languages include strings of binary numbers with a specific pattern, such as all strings with an even number of 0s, or all strings containing the substring "101". Other examples include regular expressions that match patterns such as phone numbers or email addresses.

5. Why is it important to identify if a language is regular?

Identifying if a language is regular can help in the development of computer programs and algorithms. Regular languages are easier for computers to process and manipulate, so knowing that a language is regular can help determine the most efficient way to code a solution for that language.

• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
• Programming and Computer Science
Replies
1
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
10
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
43
Views
7K
• Set Theory, Logic, Probability, Statistics
Replies
24
Views
4K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Differential Geometry
Replies
1
Views
1K