2
$\begingroup$

I don't know if this question should have better been on math.Stackexchange

Let be the operation $Double$ on the words on an $\Sigma$ alphabet which inserts after each character a copy of this character. Thus, $D(ab) = aabb$, $D(abaab) = aabbaaaabb$, etc... We had to prove that these regular expressions are closed by this operation and it was a sucess.

We now have to prove this properties for automata. In other words, we have to prove that if we have a language $L$ such that it exists an automata $A$ that recognize $(L=L(A))$, there also exists an automata $A'$ that recognize tha language $Double(L)$.

I shouldn't use equivalence between automatas and regular expressions

goal : I therefore deduce that I have to prove that autmomatas are closed by the Double operation.

the hypothese : is that it exists a language $L$ such taht it exists an automata $A$ which recognizes it.

proof attempt : $D(L)$ being a language, it must be a automata associated.

But:

  1. has(have ?) every language(s?) an associated automata?
  2. Isn't this proof too short or taking its goal has an hypothesis ?

Proof attempt n°2

Following Rick Decker's advises, here is the second attempt to prove that if we have a language $L$ such that it exists an automata $A$ that recognize $(L=L(A))$, there also exists an automata $A'$ that recognize tha language $Double(L)$ :

To prove it, we are goint to construct an automata $A'$ such that $A'=D(L)$.

The idea is to construct an input string of $w$ that we reads from left to right. After having read the entire string $w$, it checks whether the following char is the same. If it is the case we remain in the final state. Otherwise, we go to a transitional state and if the following char isn't exactly the same, we go to the bin state.

    1. $Q=\{q_0, q_1, q_2, p\}$, $q_1,q_2$ are waiting states, $p$ is a bin state.
    1. $\Sigma$ is the alphabet. For the example it is : $\{a,b\}$.
    1. $\delta : Q × \Sigma → Q$ is a function, called the transition function,

$$\begin{array}{c|cc|c|c|} & a & b\\ \hline q_0 & q_2 & q_1\\ q_1 & p& q_0\\ q_2 & q_0&p\\ p & p & p\\ \hline \end{array}$$

    1. $q=q_0$.
    1. $F=q_0$ is the final state. It corresponds to the intial state because the empty set is accepted by the automata.

enter image description here

$\endgroup$
2
$\begingroup$

Unfortunately, your second attempt is not correct. Since your automaton recognized all the words of the type $aabbbbaabb$, etc. And not the $Double(L)$ for a given regular language $L$.

You should proceed as follows. If $L\subseteq\{a,b\}^*$ is regular, then there is a DFA which recognizes it. Let $\mathcal{A}=\langle\{a,b\},Q,F,q_0,\delta\rangle$ the description for such a DFA. Assume $Q=\{q_0,q_1,\ldots,q_k\}$ and $F=\{q_k\}$ (WLOG we assume only one final state).

Now we are supposed to describe the DFA for $Double(L)$ provided $\mathcal{A}$. Here is the description of $D(\mathcal{A})=\langle\{a,b\},Q',F',q'_i,\delta'\rangle$.

$q'_i=q_i$

$Q'=Q\cup\bar{Q^a}\cup\bar{Q^b}\cup\{q_P\}\;$ where $\;\bar{Q^a}=\{\bar{q^a_j},\,q_j\in Q\}$ and $\bar{Q^b}$ is defined similarly; $q_P$ is for the sink state.

$F'=\{\bar{q^a_k},\bar{q^b_k}\}$

where all the "barred" symbols are new symbols.

The idea is to use the "barred" states to check the "Double" property. Hence here is how we define the function $\delta'$ on the basis of the old $\delta$.

Step 1: $\delta'=\emptyset$

Step 2: if $(q_i,a,q_j)\in\delta$ then $\delta'=\delta'\cup(q_i,a,\bar{q^a_j})\cup(\bar{q^a_j},a,q_j)\cup(\bar{q^a_j},b,q_P)$ and $\delta=\delta\setminus\{(q_i,a,q_j)\}$

Step 3: if $(q_i,b,q_j)\in\delta$ then $\delta'=\delta'\cup(q_i,b,\bar{q^b_j})\cup(\bar{q^b_j},b,q_j)\cup(\bar{q^b_j},a,q_P)$ and $\delta=\delta\setminus\{(q_i,b,q_j)\}$

Step 4: if $\delta\ne\emptyset$ then goto Step 2.

The idea is that you store in the barred state the next symbol you expect; if the next symbol is the expected symbol then you go on, otherwise send everything to the sink.

$\endgroup$
  • $\begingroup$ Thank you for your answer ! Yet I don't understand what $\;\bar{Q^a}=\{\bar{q^a_j},\,q_j\in Q\}$ is ... especially ${\bar{q^a_j}}$ where does these new symbols come from ? $\endgroup$ – IggyPass Feb 28 '17 at 15:03
  • $\begingroup$ They are new symbols different from the previous ones. We need them as checkpoints between two former states in $Q$. $\endgroup$ – Maczinga Feb 28 '17 at 15:58
2
$\begingroup$

You said you showed this result using regular expressions. Take the idea you used then and apply it to automata. You assume you're given an automaton $A$ for the language $L$. You need to construct an automaton $A'$ which accepts all and only the strings in $D(L)$.

Here's a hint to get you started: if you have a rule in $A$ of the form $\delta(p, a) = q$, meaning that in state $p$, seeing input $a$, you go to state $q$, how would you modify that rule so that from state $p$, seeing $a$ and $a$ again, will go to state $q$? Perhaps you might introduce another state along the way from $p$ to $q$?

$\endgroup$
  • $\begingroup$ Thank you for your answer, I've updated my question according to your advises. I'm quite skeptical about the generalization of it. (I've only given an example for an $a,b$ aplhpabet)! $\endgroup$ – IggyPass Feb 27 '17 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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