Language Transformations

Today is our last day discussing regular languages, and we’re going to take advantage of all the things we learned.

By definition (essentially,) regular languages are those represented by regular expressions. By Kleene’s theorem and its proof, we know the regular languages are also those accepted by NFAs, and they are also those accepted by DFAs. So if you want to show a language is regular, you “simply” describe a DFA, NFA, or regular expression for it.

We’ve also discussed another way to show a language is regular. We can take one or more known regular languages and construct another regular language using a handful of simple operations:

• By definition of regular languages/expressions, you can use union, concatenation, or Kleene closure.
• Through product constructions of DFAs and careful choice of accept states, you get intersection, complement, and pretty much any other set algebraic function of the languages you’d like.

But it turns out there’s so much more we can do to construct new regular languages. Often, we can get away with manipulating the individual strings of the language in various ways. Specifically, let’s say we have a function f that takes a language L and returns a whole other language f(L) (typically, but not always over the same alphabet.) We’d like to prove that regular languages are closed under f, i.e., if L is regular, then f(L) is regular.

In the typical approach to doing so There are two general techniques we can use:

• Describe an algorithm that takes an arbitrary regular expression R as input and outputs a new regular expression R' such that L(R') = f(L(R)).
• Describe an algorithm that transforms an arbitrary DFA M into a new NFA M' (with \varepsilon-transitions) such that L(M') = f(L(M)).

In principle, we can use either approach (and I believe one could translate one approach’s algorithm into an algorithm for the other approach using the proofs of Kleene’s theorem. Probably.) However, the latter approach tends to be more powerful and, once you wrap your head around it, easier to use.

A large part of why the latter method is more complicated (at first) but also more powerful is in the asymmetry between the algorithm’s input and output. All regular languages can be accepted by a DFA, and DFAs are (in my opinion) the easiest of the models we have to reason about. So it’s enough to use the nice, simple, predictable DFAs as the way to describe arbitrary regular languages. On the other hand, every language accepted by some NFA is regular. NFAs can also follow the same logic as a DFA if we want but with more capabilities like having choices of what transition to take, \varepsilon-transitions for guessing when to move between different pieces of an NFA, etc. So, we take a DFA, something that is fairly limited and easy to reason about, and then use whatever powerful tools we want from the construction of NFAs to manipulate what can be accepted.

There’s no real big definitions or theorems for today. It’s just time to practice.

Examples

Bitwise complement

The bitwise complement w^c of a binary string w is given by replacing every 0 in w with a 1 and vice verse. In other words, each character a is replaced with 1 - a. More formally: w^c := \begin{cases} \varepsilon &\text{if $w = \varepsilon$}\\ 1 \cdot x^c &\text{if $w = 0 \cdot x$}\\ 0 \cdot x^c &\text{if $w = 1 \cdot x$} \end{cases} A straightforward induction proof shows (w^c)^c = w. Let extend the definition of bitwise complement to entire languages: L^c = \{w^c \mid w \in L\} = \{w \mid w^c \in L\}.

Theorem: For any regular language L, then L^c is regular.

We’ll describe how to take an arbitrary DFA M for L and build a new NFA M^c that accepts L^c. In short, M^c is exactly the same as M, except all transitions use the complementary symbol.

Okay, yes, M^c could have been a DFA, but the next example will show why we want to build NFAs in many cases.

String reversal

Recall the reversal function for a string w as seen in Lab 1a. w^R := \begin{cases} \varepsilon & \text{if $w = \varepsilon$}\\ x^R \bullet a & \text{if $w = ax$} \end{cases} In the same lab, you saw (w^R)^R = w. Let’s extend the definition of reversal to entire languages: L^R := \{w^R \mid w \in L \} = \{w \mid w^R \in L\}.

Theorem: For any regular language L, language L^R is regular.

As before, we’ll start with an arbitrary DFA M = (Q, \delta, s, A) accepting L and use it to build an NFA M^R. It should accept a reversed string w^R if and only if the original w would be accepted by M.

Intuitively, string w is accepted if and only if it takes machine M from start state s to some accept state r \in A (although we don’t know a priori which accept state it goes to.)

Therefore, it is possible to “trace” these transitions backwards from some r \in A to s while reading string w^R if and only if w \in L, and our NFA will model this idea. Each time M^R reads a symbol a from a string w^R while at a state q, we’ll let it go to any of the states p that would have M transition to q while reading a. NFA M^R should accept only at s to model DFA M only starting from s. Also, M^R should start from any of the accept states in A to model DFA M reaching any of those states. Therefore, it needs multiple start states.

Below is an actual proof at about the level we’d expect for an exam. The lab solutions are closer to what we want for homework.

Here’s a full example of the transformation: On the left below, we have the left a DFA that accepts binary strings ending in 00 or 11. To the right, we have the NFA that accepts the reversal of the language (which in this case happens to be binary strings beginning with 00 or 11.)

Again, for both homework and exams, we’ll be looking for an unambiguous description of the new NFA (M^R in the latter case) as a function of the input DFA (M) along with a brief justification of why your NFA is correct. For exams at least, the justification is just a one or two sentence explanation of what a state in your NFA (M^R) represents. We need the justification even in exams, because the goal here is to do a proof, not merely to demonstrate to demonstrate designing something. Homework problems may warrant a bit more justification just because they’re more complicated.

If you’re interested, the end of these notes shows another proof that if L is regular, then L^R is regular. The second proof directly manipulates a regular expression representing L.

First half of palindromes

The next language transformation is a bit fancier and much harder to do by only manipulating regular expressions. If also shows off a couple more ideas common to these types of proofs.

For any language L, let \text{palin}(L) : \{w \mid w \bullet w^R \in L\} be the first half of every even-length palindrome in L. For example, if 0110110110 \in L, then 01101 \in \text{palin}(L).

Theorem: For any regular language L, then \text{palin}(L) is regular.

It’s important to recognize that \text{palin}(L) is not the set of even-length palindromes in L, i.e., \{w \bullet w^R \mid (w \bullet w^R) \in L\}. In fact, \{w \bullet w^R \mid \Sigma^*\} is not regular! \text{palin}(L) is not the set of strings w \bullet w^R where w \in L; in fact \{w \bullet w^R \mid w \in \Sigma^*\} is the set of all palindromes which we saw last time is not regular, either. Finally, \text{palin}(L) is not the concatenation of L with its reversal, i.e., L \bullet L^R. This last language actually is regular, though, because regularity is closed under reversal (as we just saw) and concatenation.

As a general rule of thumb, it’s often possible to manipulate how a DFA handles reading a string, but as soon as you need to remember an arbitrary amount of symbols or counts to check against while reading later parts of the string, the language stops being regular.

So how do we handle this one? Let M = (Q, \delta, s, A) be a DFA that accepts L and consider how to build an NFA M' for \text{palin}(L). Some string w \in \text{palin}(L) if and only if M reads w to reach some state h and then reads w^R to take h to an accept state r \in A. We need to simulate two processes at the same time as we read in w once; going forward from s to h and going backward from r to h. That suggests using pairs of states from M as the states in M'. Each time M' reads a symbol, we should simulate both M in the forward and backwards direction. If there was any common h that can be reached and can reach an accept state, then M' should accept.

Complementing a suffix

Let’s do one more example to show off what’s possible with \varepsilon-transitions. For a language L, let \text{comp-suffix}(L) = \{xy^c \mid x y \in L\}. In other words, it’s what you get when you take strings and L and apply bitwise compliments to all of their (possibly empty) suffixes. For example, if 1001 \in L, then 1001, 1000, 1010, 1110, and 0110 are all in \text{comp-suffix}(L).

Theorem: For any regular language L, then \text{comp-suffix}(L) is regular.

Once again, we let M = (Q, \delta, s, A) be a DFA accepting L and describe an NFA M'. A string xy^c \in \text{comp-suffix}(L) if and only if M has x take s to some state h and then has y take h to some accept state r \in A. In our sense, M' needs to simulate two completely separate computations. Unfortunately, we don’t know ahead of time which state h is the one to jump between them or how much of the input string belongs to x. We need a way to let M' guess when to jump between the two modes of computation.

The trick is to essentially make two disjoint machines, one being M itself and another being M^c so we can read y^c. And to guess when to jump between them, we add \varepsilon-transitions between each state in M and its copy in M^c.

Notice how I included that last type of transition even though there are no \varepsilon-transitions out of the M^c states. You either need to fully specify the function \delta for all possible inputs or explicitly declare that missing combinations go to the empty set of states.

Reversal revisited

Just for completeness, let’s try proving regularity is closed under reversal by manipulating a regular expression. I doubt you’ll use this technique in any coursework.

Theorem: For any regular language L, language L^R is regular.