Constructive Proof on Regular Languages

Question

As an assignment, I've to come up with constructive proofs for the following languages to be regular supposing A and B are two distinct regular languages.

$$L_1=\{w│w^R∈A\}$$ $$L_2=\{w│w=a_1 b_1,…,a_k b_k;a_i∈A,b_i∈B\}$$ $$L_3=\{xy│yx∈0A\}$$ $$L_4=\{w│w∈A,∄y∈B:w=xyz for some x,z∈Σ^* \}$$ $$L_5=\{w│∃x∈B:wx∈A\}$$

I've already come up with answers for the first two, but I've no idea about the rest. For L3 no information on what x and y are is provided, so I thought they must be strings concatenated together.

My main question is, is there any generalized algorithm which by using it one can derive an appropriate NFA or RegEx to prove that such languages are regular? Could these things be broken down into primitive structures or operators by some rules or methods so the corresponding NFA or RegEx for the constructive proof be derived from it?

Answer 1

In general, the answer is usually "no". Equality of languages is, most of the time, undecidable; regular languages are a special case here, at least when they are given in certain representations.

What you can do is to break down those languages in terms of closure properties of REG, e.g. reversal, homomorphism, complement, etc.

Since your task here is to prove such closure properties, you'll have to take the long and creative route: come up with a construction and prove it correct. The purpose of the exercise is to train doing exactly that, so taking a shortcut would be unwise.

Answer 2

If your task is to come up with constructions that find automata for the languages $L_1$ to $L_5$ given automata for $A$ and $B$, then I suggest to follow Raphaels advice and try the remaining cases. Think of what information to store in the states of the new automaton to make the new language. Most of these closure properties are considered somewhere on this site: reversal, shuffle, rotation, substring, quotient.

Now, if the question is philosophical, i.e., does there exist a powerful closure property that encompass all the closure properties from your exercise, in that case I have a suggestion.

Apart from the usual finite state automata, one also considers two-way finite state automata that may move in both directions over the tape. Shepherdson famously proved in 1959 that every two-way FSA can (constructively) be reduced to an ordinary one-way FSA.

Now consider automata with output, or better two-way FSA with output which we will call here 2NGSM. Let $T_M(A) = \{y\in\Sigma_2^* \mid \text{ for some } x\in A, M \text{ outputs } y \}$. Those automata are quite powerful. (0) They can duplicate the input string by copying it twice to the output. (1) They can reverse a string by walking to the end of the tape and then returning to the beginning copying the letters to the output tape. (2) They can first write the letters at odd positions, write a special marker $\#$, then write the letters at even positions in the string.

Then

• $T_{M0}(A) = \{ww\mid w\in A\}$.
• $T_{M1}(A) = \{w^{R}\mid w\in A\}$,
• $T_{M2}((ab)^*) = \{a^n\#b^n\mid n\ge0\}$,

From these examples it is clear that while the input is regular, the output might not be regular. But it follows quite directly from Shepherdsons result that inverse 2NGSM do maintain regularity:

If $B$ is regular, and $M$ is a 2NGSM, then $T^{-1}_M(B) = \{x\in\Sigma_1^* \mid \text{ on input } x, M \text{ outputs } y\in B \}$ is regular.

Now $T_{M0}$ above show the closure property root, $T_{M1}(A)$ is reversal $L_1$, and $T_{M2}$ on target language $A\#B$ solves your shuffle $L_2$.

At this moment I can only solve $L_3$ this way if $0$ is a special symbol that does not occur in $A$.

The last one $L_5$ can be solved by constructing a 2NGSM $T_B$ (actually one way) that on input $w$ concatenates an arbitrary $x\in B$ to $w$. Then $T^{-1}_B(A) = L_5$.