Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know how I want to do the proof, but I don't know how to represent it. It's an automata proof, so all I need to do is show that it is regular. How could I represent a DFA as a copy? So I have the automaton $L_1$ let's say and I want to copy $L_1$ to $L'_1$ basically. So, it will be the same exact language, have the same states etc., but i need a copy of it for the final construction. I just want to show that it's a copy.

$L_1$ is defined as $L_1 = (Q_1, E, \delta_1, q_1, F_1)$. Could I simply just state $L'_1 = (Q_1, E, \delta_1, q_1, F_1)$? I just don't know how to show on paper what I want to do.


share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

For ease of typing I’m going to remove the subscript $1$, since it plays no role in this question.

If you actually need $L'$ to be a distinct copy of $L$ and want to be somewhat rigorous about it, you’ll have to do some extra writing. You have (after minor modification) $L = (Q,E,\delta,q_0,F)$; I’m assuming that $Q$ is the state set, $E$ the input alphabet, $\delta:Q \times E \to Q$ the transition function, $q$ the initial state, and $F$ the set of acceptor (final) states. First you need a disjoint copy, $Q'$, of $Q$. A standard trick for constructing such a $Q'$ is to let $Q' = Q \times \{Q\} = \{\langle q,Q \rangle:q \in Q\}$; this ensures that $Q$ and $Q'$ are disjoint while at the same time providing a natural bijection between them. $Q'$ will be the state set of $L'$, and from that it’s easy to specify the rest of $L'$.

Certainly $L'$ will have the same input alphabet $E$. For convenience let $q' = \langle q,Q \rangle \in Q'$ for each $q \in Q$. Clearly we want $q_0'$ to be the initial state of $L'$ and $F' = \{q':q \in F\}$ to be the set of acceptor states. The transition function $\delta':Q' \times E \to Q'$ is defined by setting $\delta'(q',e) = \left(\delta(q,e)\right)'$. With these definitions $L' = (Q',E,\delta',q_0',F')$ is easily seen to be a DFA isomorphic to but disjoint from $L$, i.e., a distinct copy of $L$.

For your purpose you may or may not actually need this level of rigor in constructing $L'$. You would need it if, for instance, you wanted to combine two copies of $L$ to make some larger DFA.

share|improve this answer
Yea that's what i want. I have to create a much bigger DFA, but hey are clones. –  Matt Sep 12 '11 at 21:48
add comment

You can either say that $L'_1$ is a copy of $L_1$, or write it out explicitly (though that's not needed).

This type of proofs are not called formal but rather informal. This doesn't mean that they have no rules. The language of informal proofs is not defined explicitly anywhere, and must be learned by example. A general rule is that you're allowed to use everyday language whenever it's unambiguous (or can be disambiguated from the context). Also watch out for words which have a specific technical meaning in math.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.