# Parallelism, products, and automata

I have an unreasonable love of alliterations, so I wish I knew a common word for automata that started with P. I even considered calling this post “Paralleilism, Products, Producers”, but feared introducing non-standard nomenclature and confusion into Professor Prakash Panangaden’s class. Hence, the current title; not too bad? If we count “and automata” as an alliteration then I can claim to have introduced an example of parallelism as used in rhetoric right in the title. Unfortunately, the post’s on parallelism in processing; sorry, having too much fun.

Proving that the left half of a regular language is regular was the hardest question on the first assignment. It was also challenge for me as a TA, because I couldn’t find many avenues for hints and advice that didn’t reveal the answer directly. From grading however, I was impressed by the number of students that solved it, but a bit disappointed by those that Googled “half of a regular language” and clicked on the first result like Ben Reichardt’s notes. Since there are solutions already online, I decided that I can give answers, too. Although Prakash provided a full solution set, I thought I would sketch a pedantic treatment of question 5.

One of the best tools from theory of computing is showing that potentially distant seeming languages or even models of computation actually have the same or similar complexity. The regular languages serve as a microcosm to learn and hone these tools. When you first see the boringly serial finite state machines presented, a natural question is: what if I run two DFAs in parallel, is that still a DFA? Well, pedantically no, it doesn’t match the definitions, but in reality — yes, we just have to be more precise.

DFAs are introduced because they recognize (or produce; hence my titular temptation) a regular language. Hence, we should try to relate our machines to languages, if we have two machines $M_1, M_2$ with languages $L_{M_1}, L_{M_2}$ then is the language $L_{M_1} \cap L_{M_2}$ regular? The tempting answer is “yes, run the two machines in parallel”. Since both are finite, running them in parallel seems finite, too. However, we have to build a standard serial DFA to prove regularity, and we can do this with the product construction. Let $M'$ have states $Q = Q_1 \times Q_2$, with start state $s' = (s_1, s_2)$ (where $s_b$ is the start state of machine $M_b$), and transition function $\delta'((q_1,q_2),a) = (\delta_1(q_1,a),\delta_2(q_2,a))$. Clearly, the machine just treats the two parts of the tuple as independent sub-machines running in parallel, and it isn’t hard to show (by induction on word length) that $\forall w \in \Sigma^* \;\; \delta'^*(s',w) = (q_1,q_2) \iff (\delta_1^*(s_1,w) = q_1 \; \mathrm{and}\; \delta_2^*(s_2,w))$. This is the product construction (I encourage the reader to check that we could do the same thing with two NFAs to make a product NFA), and leaves us with only the final states $F'$ to specify. This is where we usually implement our way of combining the two languages. In the case of intersection, the natural logical operation is ‘and’, so we let $F' = \{(q_1,q_2) \;|\; q_1 \in F_1 \; \mathrm{and} q_2 \in F_2\}$. If we wanted to implement $L_{M_1} \cup L_{M_2}$ then we would just use ‘or’: $F' = \{(q_1,q_2) \;|\; q_1 \in F_1 \; \mathrm{or} q_2 \in F_2\}$. In a very natural sense, we have shown that the product construction runs two machines in parallel.

For a more involved example, consider the language $L' = \mathrm{palindrome}^{-1}(L) = \{ w \;|\; ww^\mathrm{rev} \in L\}$. If L is regular then is L’ regular? To see that it is, we have to turn a machine M for L into one for L’. The intuitive way to do this, is as we read a word for L’, pretend that instead we are actually reading a word from both ends for L — run the DFA $M$ and NFA $M^\mathrm{rev}$ in parallel, and accept only if they reach the same state. We know this can be done using our product construction above, with final states defined as $F' = {(q,q) | s \in Q}$.

Alternatively, we might have a language where both words are in the forward direction. Consider $L' = \mathrm{double}^{-1}(L) = \{ w \;|\; ww \in L\}$ where $L$ is recognized by a machine $M$. Now, we have to guess the middle point and run the second machine from that point. So, for every $q \in Q$, define $M'_q$ as $M$ except with $F'_q = \{q\}$, and $M''_q$ as $M$ except with $s''_q = q$. Now, run these two machines in parallel, accepting only if both accept. In other words, for every $q \in Q$ consider the language $L_q = L(M'_q) \cup L(M''|q) = \{ w \;|\; ww \in L(M) \;\mathrm{and}\; \delta(s_0,w) = q\}$. Clearly, if we take the union of these over all $q \in Q$ then we get $\bigcup_{q \in Q} L(M'_q) \cap L(M_q) = L'$.

If we want to explicitly build a machine using these ideas for $L'$ then we could just use our product construction, or notice acute trick that works because of union. We could define an NFA $M'$ with $Q' = Q\times Q\times Q$, $S' = \{(s_0,q,q) \; |\; q \in Q\}$, $F' = \{(q,q,f) \; | \; q \in Q \; \mathrm{and}\; f \in F\}$, and $\delta'((p,q,r),a) = (\delta(p,a),q,\delta(q,a))$. Notice, that the only non-determinism we have is in the start state where we guess what state to put in the second component of the tuple. Once the second component is set to $q$, it is kept fixed by $\delta'$, and we are basically running the machine for $L_q$.

How does all of this relate to the $\mathrm{lefthalf}(L) = \{w \;|\; \exists w' \in \Sigma^* \;\; ww' \in L \; \mathrm{and} \; |w| = |w'|\}$? Well, it is obvious that we can modify the construction for either palindrome-1 by changing the labels of all the non-epsilon transitions in $M^\mathrm{rev}$ to work for every $a \in \Sigma$, or with double-1 by changing the transitions of the third component to work for any letter; i.e. by making $\Delta'((p,q,r)) = \{(\delta(p,a),q,\delta(r,b)) \;|\; b \in \Sigma\}$.