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\}.


About Artem Kaznatcheev
From the Department of Computer Science at Oxford University and Department of Translational Hematology & Oncology Research at Cleveland Clinic, I marvel at the world through algorithmic lenses. My mind is drawn to evolutionary dynamics, theoretical computer science, mathematical oncology, computational learning theory, and philosophy of science. Previously I was at the Department of Integrated Mathematical Oncology at Moffitt Cancer Center, and the School of Computer Science and Department of Psychology at McGill University. In a past life, I worried about quantum queries at the Institute for Quantum Computing and Department of Combinatorics & Optimization at University of Waterloo and as a visitor to the Centre for Quantum Technologies at National University of Singapore. Meander with me on Google+ and Twitter.

One Response to Parallelism, products, and automata

  1. Pingback: Cataloging a year of blogging: the algorithmic world | Theory, Evolution, and Games Group

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.