over regular Languages L and D(L)

Question

Suppose you have an operation D defined as D(L) = {nm| n,m ∈ L} where L is the language over SIGMA. If L is regular and D(L) should be also regular.

I am trying to prove this, by doing:

THE DEFINITION OF REGULAR LANGUAGES: A LANGUAGE L⊆Σ* IS REGULAR IF THERE IS A DFA M SUCH THAT L = L(M). so we know that since L is regular there is a DFA A = (Q, Σ, δ, q0, F), consisting of:

1. a finite set of states (Q)

2. a finite set of input called the alphabet (Σ)

3. a transition function (δ : Q × Σ → Q)

4. a start state (q0)

5. accept state (F ⊆ Q)

that accepts L. So there should be a NFA L' = (Σ, Γ, S, σ0, δ, w):

• Σ is the input alphabet (a finite non-empty set of symbols).
• Γ is the output alphabet (a finite, non-empty set of symbols).
• S is a finite, non-empty set of states
• σ0 is the initial state
• δ is the state-transition function
• w is the output function.

is this correct?

Answer 1

Your proof is confusing to me. I am writing hint to proof that language D: = { nm | n, m ∈ L} is regular if language L is a regular.

Hint: D is concatenation (cartesian product) of two regular languages L_n and L_m, where L_n = L_m = L — hance D is also a regular language. check wiki.

Draw DFA,

1. Draw, M(L_n) a DFA for L_a with starting state Q_n0 and F_n is set of final states.
2. Draw, M(L_m) a DFA for L_m with starting state Q_m0 and F_m is set of final states.
   _{both DFAs are same except different name of states.}
3. Add null transitions from each final state in F_n to start state Q_m0. — this is NFA.
4. Remove null transitions one by one — now the resultant DFA accepts language D.

Note: your teacher will not give you full marks if you don't explains how it accepts exactly language D. You have to write fifth point - because aftr consuming a n ∈ L you reaches to one of the final state in F_n, then without consuming any symbol you shifts to start state of DFA M(L_m) then after processing any m ∈ L you reaches to a final state in F_n chance this proofs that D is a regular language. Pick a good book so learn how to formally write these steps.

Write regular expression:

1. Suppose N regular expression for L_n
2. Suppose M regular expression for L_m
3. then NM would be regular expression for D

Again explain how NM accepts D.