patternMinor
Constructive Proof on Regular Languages
Viewed 0 times
languagesconstructiveregularproof
Problem
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?
$$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?
Solution
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.
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.
Context
StackExchange Computer Science Q#89402, answer score: 4
Revisions (0)
No revisions yet.