Synchronizing Sequence

Today I found another interesting problem in Sipser (refer to 1.59). The problem is the problem of synchronizing sequence, and is a "starred" problem! We are to find the upper bound of a k-state synchronizable DFA (which we are to show as $k^3$).
The definition of synchronizing sequence is somewhat intuitive. Let $M$ be a DFA and $h$ be a state of it called home. A synchronizing sequence for $M$ and $h$ is a string $s \in \Sigma^*$, where $\delta(q,s)=h$ for every $q \in Q$.

A little bit of research in net yielded interesting facts about synchronizing sequence. The problem of estimating the length of synchronizing sequence has a long history and one very important result was Cerny's conjecture which says $(k-1)^2$ is the upper bound of shortest synchronizing sequence of a k-state synchronizable DFA. He was Czech, and the paper was in his native language, so I couldn't make out a single word of what he has written.

I got hold of a paper by A. N. Trahtman, in which he proved that

every n-state aperiodic DFA with a state that is accessible from every state of the automaton has a synchronizing word of length not greater than $\frac{n(n-1)}{2}$, and therefore, for aperiodic automata as well as for automata accepting only star-free languages, the Cerny´s conjecture holds true.

Certain terms seem alien to me at first sight. For example, a star-free language is a regular language if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, union and concatenation but no Kleen star. An aperiodic monoid needs a bit discussion, but I will shorten it because I do not have much of an idea about it right now. An aperiodic semigroup is a semigroup such that for every $x \in S$, there exists an integer $n$ so that $x^n=x^{n+1}$. An aperiodic monoid is, in short, an aperiodic semigroup which is monoid. A syntactic monoid $M(L)$ for a language $L$ is the smallest monoid that recognizes language $L$ (??). Schutzenberger concluded that a language is star free if it is accepted by a DFA with aperiodic syntactic transition monoid. Now this transition monoid need a lot of discussion on semiautomation, so I leave it for another blog. Readers may take the pain to write down something about it, I will appreciate it.

I am marking up this blog for further discussion, not before I learn a bit about these terms though. Before writing this blog, I didn't have much of an idea how group theory can be linked to language theory. This discussion gave an insight!

Another Interesting Regular Language

Refer to Sipser 2.49a.

Let $B=\{1^ky|y\in \{0,1\}^* \textrm{ and y contains at least k 1s }, k \geq 1\}$.

Again a language that seemingly looks irregular for memory involvement. But we can prove it to be regular instead. It is surprising to see that $B$ can be written as $10+1(1+0)^*$, which is a trivial regular expression. The forward subset relation is trivial. For backward subset relation (i.e., the regular expression is a subset of $B$), we see that other than $10$, we can adjust the first occurrences of 1's in two groups - one corresponding to $1^k$ and the other corresponding to $y$, such that the constraint holds.

An Almost Irregular Regular Language!

This problem has its own class. The problem says,

Let $\Sigma=\{0,1\}$ and let \[D=\{w|w \textrm{ contains an equal number of occurances of the substring }01 \textrm{ and }10\}\] Thus $101 \in D$ but $1010$ doesn't. Prove that $D$ is a regular language.

Refer to Sipser 1.48. Well, at a first glace, this language doesn't seem like regular at all, because it involves memory to an extent ("an equal occurance").  But I gave it a try, and tried to develop a DFA (well, an NFA, so to say). It gave me a hard time, so I tried to develop a regular grammar, which seemed even more difficult.

I came across this DFA somewhere in net, which looks flawless. It surfaces up some interesting properties indeed. Starting with $0$, no matter how many $10$ (and only $10$) you have in the string, you will have the same number of occurrences of $01$ and $10$ substrings. Symmetrically, starting with $1$, no matter how many $01$ (and only $01$) you have in the string, you will have the same number of occurrences of $01$ and $10$ substrings.
Another interesting problem which looks closely nonregular can be found in Sipser 1.44. The problem again deals with equal occurance, as follows:

Let $B$ and $C$ be languages over $\Sigma=\{0,1\}$. Define \[B \sqsubset C=\{w\in B| \textrm{ for some }y \in C, \textrm{ strings }w\textrm{ and }y\textrm{ contains equal number of 1s}\}\] Show that the class of regular language is closed under $\sqsubset$ operation.

The construction of $M$ from $M_B$ and $M_C$ can be done as follows.

1. $Q=Q_B X Q_C$
2. For $(q,r) \in Q$ and $a \in \Sigma$, we define 
1. $\delta((q,r),a)=\{(\delta_B(q,0),r)\}$ if $a=0$
2. $\delta((q,r),a)=\{(\delta_B(q,1),\delta_C(r,1))\}$ if $a=1$
3. $\delta((q,r),a)=\{(q,\delta_C(r,0))\}$ if $a=\epsilon$. This step nondeterministically selects the strings of $C$. (Power of nondeterminism at its best!)
3. $q_0=(q_B,q_C)$
4. $F=F_B X F_C$ 

Interesting problem, ain't it?

Shuffle and Perfect Shuffle

These two problems from the book of Mike Sipser (1.41 and 1.42) need a little bit of discussion, for I guess these two are the most coveted problems in all university coursework. Question# 1.41 deals with shuffle and question# 1.42 is an extension of shuffle  called perfect shuffle. Let's look at the problem of perfect shuffle  first, then we can modify our answer for shuffle.  

For language $A$ and $B$, let the perfect shuffle of $A$ and $B$ be the language \[\{w|w=a_1b_1...a_kb_k. \textrm{ where }a_1...a_k \in A \textrm{ and } b_1...b_k \in B, \textrm{ each }a_i,b_i \in \Sigma\}\]. Show that the class of regular language is closed under perfect shuffle.

 This is a proof by construction. Let $M_A = (Q_A;\Sigma; \delta_A; q_A; F_A)$ and $M_B = (Q_B;\Sigma; \delta_B; q_B; F_B)$ be two DFAs that recognize $A$ and $B$, respectively. Here, we shall construct a DFA $M = (Q;\Sigma; \delta; q; F)$ that recognizes the perfect shuffle of $A$ and $B$. The construction proceeds as follows.

1. $Q=Q_A \textrm{ x }Q_B \textrm{ x }\{A,B\}$.
2. $q=(q_A,q_B,A)$.
3. $F=F_A \textrm{ x }F_B\textrm{ x }{A}$, as the next character to read should be in $M_A$. (The last character read was in $M_B$).
4. $\delta$ is defined as -
1. $\delta((x,y,A),a)=(\delta_A(x,a),y,B)$.
2. $\delta((x,y,B),b)=(x,\delta_B(y,a),A)$.

The construction of shuffle DFA is more or less the same, but with fewer restrictions. Let me state the question first.

For language $A$ and $B$, let the shuffle of $A$ and $B$ be the language \[\{w|w=a_1b_1...a_kb_k. \textrm{ where }a_1...a_k \in A \textrm{ and } b_1...b_k \in B, \textrm{ each }a_i,b_i \in \Sigma^*\}\]. Show that the class of regular language is closed under shuffle.

Now let's take a look at the construction. Again we are going to design a combined DFA with the same tuples as defined for the last problem.

1. $Q=Q_A \textrm{ x }Q_B \cup {q_0}$, $q_0$ defines the state when nothing is read.
2. $q=q_A$.
3. $F=F_A \textrm{ x }F_B \cup {q_0}$, as this DFA can accept the null string.
4. $\delta$ is defined as -
1. $\delta(q_0,\epsilon)=(q_A,q_B)$.
2. $(\delta_A(x,a),y) \in \delta((x,y),a)$.
3. $(x,\delta_B(y,a)) \in \delta((x,y),a)$.

I guess these two construction answer the problems satisfactorily. Thanks to Wing-Kai Hon of National Tsing Hua University for the discussion of the above problems.