0
$\begingroup$

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.

Thanks!

2 Answers 2

1

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.

  • 0
    Yea that's what i want. I have to create a much bigger DFA, but hey are clones.2011-09-12
0

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.