Theory of Formal Languages, Automata, and Computation/Properties of Language Classes

A comprehensive picture of the hierarchy of language classes is shown in Figure LanguageHierarchy, along with the briefest reference to concepts and factoids that have been covered. It is intended as a reference that can be reviewed quickly to good effect, possibly before an exam, or perhaps years later to confirm a fleeting memory.

Figure LanguageHierarchy: The languages classes studied thus far, but with a few references on some of the topics to come, most notably algorithm complexity and more on undecidability.

Kinds of Properties

A property of a given language is a statement or predicate that is true of the language. Suppose the language is the set of prime numbers. One property is that there is an algorithm for recognizing any input as a prime number or not. That is, the language of prime numbers is recursive. We've spent a lot of time on such properties -- that a language is in a class of languages, or that a particular language includes a particular string or not. We've covered other properties of specific languages too, perhaps only briefly, such as the property that a given language is inherently ambiguous or not.

A property of a language class is a statement or predicate that is true of all members of the class. We have not spent much time thus far on properties of language classes, other than definitional properties, which we discuss below.

Closure Properties

To preview one example, lets consider the class of CFLs. ∀_L L $\in$ CFLs → P(L), where L is a language and P is a property. A property of the CFLs is that if L is a CFL then L^* is a CFL. This is an example of a closure property -- that the CFLs are closed under Kleene Closure, aka repetition. As another example of a closure property, again of the CFL class, ∀_L1,_L2 (L₁ $\in$ CFLs ∧ L₂ $\in$ CFLs) → R(L₁, L₂), where L₁ and L₂ are languages and R is a property, such as union: if L₁ and L₂ are CFLs then L₁ $\cup$ L₂ is a CFL; the CFLs are closed under union.

Figure ClosurePropertiesSummary: Closure properties of language classes. A check $\checkmark$in a cell indicates that the language class in the corresponding column is closed under the operation of the corresponding row. No check in a cell indicates that the language class is not closed under the operation.

But if we say that a property does not hold for a language class, such as the CFLs, this means that the property is not true of all CFLs, or equivalently, there exists a CFL for which the property does not hold. That is, for CFLs, ¬(∀_L L $\in$ CFLs → P(L)) ≡ ∃_L ¬(L $\not \in$ CFLs $\lor$ P(L)) ≡ ∃_L L $\in$ CFLs $\land$ ¬P(L)), where L is a language and P is a property. For example, if L is a CFL, then L's complement, ${\bar {L}}$, is not necessarily a CFL; the CFLs are not closed under complement, or put another way, the class of CFLs does not possess the closed-under-complement property. Its important to recognize that this is a statement about a class of languages, the CFLs, not a statement about a particular language. Thus, its not inconsistent to say that the class of CFLs do not possess the closed-under-complement property, but that the complement of a particular CFL is also a CFL.

We have talked extensively about certain definitional properties of various language classes already -- the type of grammar that generates languages in the class, the kind of automata that recognize them, and other representations and patterns of languages in the class (e.g., as stated in the Pumping Lemma). These are all examples of definitional properties of selected language classes. A new focus in this chapter is closure properties (or not) of language classes. This text focuses on six closure properties, but there are many other closure properties that are addressed in other texts. A preview of our coverage is shown in Figure ClosurePropertiesSummary.

Decision Properties

In addition to closure properties, we will also discuss selected decision properties in this chapter. A decision property corresponds to a yes/no question about a language class that is decidable in all cases. We have already covered in considerable detail, for example, membership decision properties. Every language class we have studied, except RE, has the decision property that a test of membership in a language of the class is an algorithm. A test of membership is decidable for regular languages, DCFLs, CFLs, CSLs, and recursive languages, and thus each of those classes has the test-of-membership decision property. The recursively enumerable languages generally, notably to include those languages that are not recursive, do not have the test-of-membership decision property because the question of membership of an arbitrary recursively enumerable language is undecidable. We've spent so much time on this question already that we don't repeat the analysis in discussing each language class in this chapter, but we do include it in the summary of decision properties in Figure DecisionPropertiesSummary.

Recall that a question is decidable if there exists a TM (or computer program) that given a requisite number of language specifications (e.g., as grammars or automata) as input, and correctly answers the question for which the TM was designed to answer. As yet another example of a decision property, in this case of the regular languages, recall we have already sketched an algorithm for answering whether two regular languages, as represented finitely through DFAs, NFAs, RegExps, or RGs, are the same language. So if we are given a RegExp that represents a language and an NFA that represents a language, then clearly the languages represented by each are regular, and we can translate each language specification into a DFA, minimize each of the resulting DFAs, and see if the two minimal state DFAs are identical, aside from state names. This process can be implemented as a TM or computer program that correctly answers whether its two input language specifications represent the same language or not. In my example I seemed to suggest that the inputs can be different in form -- one as an RegExp and one as a NFA -- but for purposes of implementation we could insist on both inputs as RegExps, or both as NFAs, or both as DFAs, or both as RGs; or we could use TMs as the way we represent all languages that are input to decision questions.

The class of regular languages has the property that the question of equivalence is decidable because we can test for equivalence by using a single correct TM for all (pairs of) regular languages that are inputs to the TM.

In contrast, if we say that a decision question is undecidable for a class of languages then that means that there does not exist a TM that correctly answers the question (and halts) for all languages in the class. For example, it is undecidable whether two CFLs, as represented finitely by CFGs or PDAs, or TMs, are the same language. But we want to be careful about language here. We've said earlier that a property of a class of languages is a statement that is true of all languages in the class. So rather than saying that the class of CFLs has the property that the question of equivalence is undecidable, which you might see in some sources, we'll say that the class of CFLs does not have the property of decidability on the question of equivalence. This is consistent with the discussion on closure properties as well. It is still the case that particular pairs of CFL specifications can be shown to be equivalent using a TM created to answer the equivalence questions for CFLs, but no TM can be found that is always correct and always halts.

As with closure properties we will only reference a limited number of decision properties, though when we reach the RE languages we will describe Rice's theorem and its astounding conclusion that an infinite number of decision questions are undecidable in the case of the RE languages generally.

Properties of Regular Languages

If we want to show that a language is regular it will be possible to construct an FA, regular expression, or regular grammar that demonstrably represents the language, perhaps verified by a proof by induction or contradiction. A construction argument, whether followed by an auxiliary proof or not, often represents a kind of gold standard of demonstration.

Closure Properties of Regular Languages

Closure properties can also be used to show a language, L, is regular (or in some other class of languages for that matter). We can do this by applying transformations known to preserve regularity to a language, X, known to be regular (e.g., by construction), until reaching the target language, L, thus demonstrating that X $\in$ RL $\rightarrow$ L $\in$ RL. In addition, closure properties can be handy in showing that a language, L, is not regular, by applying transformations known to preserve regularity to L, until a language, X, is derived that is known through some other demonstration to not be regular. Thus, the original language, L, must not have been regular either (i.e., demonstrating X $\not \in$ RL $\rightarrow$ L $\not \in$ RL).

The regular languages are closed under

• Complement
• Union
• Intersection
• Concatenation
• Repetition or Kleene Closure
• Substitution

It will be interesting to compare the closure properties of the regular languages with those closure properties of more inclusive languages – context free, context sensitive, and unrestricted.

Regular Languages are closed under Complement

Theorem: If L is a regular language then the complement of L, ${\bar {L}}$, is regular.

Since L is regular, there is a DFA, M, that recognizes L. Construct the DFA for ${\bar {L}}$, call it ${\bar {M}}$, by simultaneously changing all accepting states in M to non-accepting states, and changing all non-accepting states in M to accepting states. If ${\bar {M}}$ accepts a string w then w must have taken a path to an accepting state of ${\bar {M}}$, which was a non-accepting state in M, so w is not in L. If ${\bar {M}}$ did not accept a string w then w must have taken a path to a non-accepting state of ${\bar {M}}$, which was an accepting state in M, so w is in L.

Regular Languages are closed under Union

Theorem: If L₁ and L₂ are both regular languages, then L₁$\cup$ L₂ is a regular language.

Since L₁ and L₂ are each regular languages, there are DFAs M₁ and M₂, respectively, that recognize each. Construct an NFA with $\varepsilon$ transitions, M_1$\cup$2, for L₁ $\cup$ L₂ as follows.

• Create copies of M₁ and M₂, call the copies M₁' and M₂'.
• Create a start state for M_1$\cup$2, and add $\varepsilon$ transitions from that start state to each of the start states of M₁' and M₂'.
• Create a single accepting state for M_1$\cup$2, and add an $\varepsilon$ transition for each of the accepting states of M₁' and of M₂' to the accepting state of M_1$\cup$2.
• Change the accepting states of M₁' and M₂' to non-accepting states.

M_1$\cup$2 is an NFA that recognizes L₁ $\cup$ L₂ and thus L₁ $\cup$ L₂ is a regular language.

Regular Languages are closed under Intersection

Figure DFAofIntersection: The language {0^m | m is evenly divisible by 2 and evenly divisible by 3} is regular.

Theorem: If L₁ and L₂ are both regular languages, then L₁ $\cap$ L₂ is a regular language.

Suppose L₁ and L₂ are regular languages over alphabet Σ. Then L₁ $\cap$ L₂ is regular. This must be so since L₁ $\cap$ L₂ = ~(~L₁ $\cup$ ~L₂) and the regular languages are closed under complement and union. But we can also directly construct a DFA that accepts L₁ $\cap$ L₂ from the DFAs that must exist for L₁ (M₁ = (Q₁, Σ , $\delta$₁, q₁, F₁)) and L₂ (M₂ = (Q₂, Σ , $\delta$₂, q₂, F₂)), respectively. The following is adapted from (pp. 59-60, ; p. 137, ).

M_1∩2 = (Q₁×Q₂, Σ, $\delta$ , [q_1, q₂ ], F₁×F₂) that accepts L₁ $\cap$ L₂. For each pair of states from M₁ and M₂ respectively, define a state in M_1∩2 . For each of these pairs of states, on each symbol a in Σ, define a transition in M_1∩2

                                                                          $\delta$([q_1i, q_2k ], a) = [$\delta$₁(q_1i, a), $\delta$₂(q_2k, a)]

As an example, consider {0^m | m is evenly divisible by 2 and evenly divisible by 3}. Its easy to build a DFA that accepts an even number of 0s, and its easy to build a DFA that accepts an integer multiple of 3 number of 0s. A DFA for their intersection is shown in Figure DFAofIntersection, and thus the intersection of the two regular languages is thus regular.

Regular Languages are closed under Concatenation

Theorem: If L₁ and L₂ are both regular languages, then L₁L₂ is a regular language.

The concatenation of languages L₁ and L₂, written L₁L₂, is {w₁w₂ | w_1j $\in$ L₁ and w_2k $\in$ L₂}. That is, any word from L₁ followed immediately by any word of L₂, is a string in the language of the concatenation.

Since L₁ and L₂ are each regular languages, there are DFAs M₁ and M₂, respectively, that recognize each. Construct an NFA M₁₂ with $\varepsilon$ transitions by

• copying M₁ and M₂ , call them M₁' and M₂',
• make the start state of M₁₂ be the start state of M₁',
• make the accepting states of M₁₂ be the accepting states of M₂',
• connect M₁' and M₂' by adding an $\varepsilon$ transition from each accepting state of M₁' to the start state of M₂', and
• change every accepting state in M₁' to be a non-accepting state.

M₁₂ is an NFA that recognizes L₁L₂ and thus L₁L₂ is a regular language.

As a matter of interest and subsequent utility, we can extend concatenation to a sequence of more than two languages, so that L₁L₂...L_m = {w₁w₂...w_m | w_1j $\in$ L₁ and w_2k $\in$ L₂ and ... and w_mi $\in$ L_m}.

Regular Languages are closed under Kleene Closure

Theorem: If L is a regular language then L* is a regular language.

We introduced Kleene closure in defining regular expressions, and also called it the repetition operator. The Kleene closure of a language L, L*, equals {w₁w₂w₃...w_m | for all m $\geq$ 0 and each w_k $\in$ L}. That is, strings in L* are each a concatenation of an indefinite number of strings from L.

If L is a regular language then there is a DFA, M, that recognizes it. To construct an NFA with $\varepsilon$ transitions that recognizes L*,

• copy M as M',
• add an $\varepsilon$ transition from each accepting state to M' to the existing start state of M',
• add a new start state to M' with an $\varepsilon$ transition to the original start state of M', and
• make the new start state of M' an accepting state as well (so that the NFA accepts the empty string).

The resulting NFA accepts L* and so L* is a regular language.

Regular Languages are closed under Substitution

Substitution is the most complicated of the operations that we will consider. Suppose L is a language, regular or not, over alphabet Σ. Suppose further that for each symbol in Σ, x_k, we associate a language Lx_k. We will speak of the substitution operation, Subst, as being applied to each symbol of Σ, to each string of L, and to L itself. If x_k is a symbol in Σ then Subst(x_k) is the strings in Lx_k, i.e., simply Lx_k itself. If w = a₁a₂...a_m is a string in L, then Subst(w) = Subst(a₁)Subst(a₂)...Subst(a_m), that is Subst(w) is the concatenation of the languages (see above) associated with the various symbols in w. Finally, Subst(L) = {Subst(w) $\mid$ w $\in$ L}, that is Subst(L) is the set of strings resulting from the substitution applied too all strings in L. Importantly, the alphabets for the various languages, L and the Lx_k's don't have too be the same. The alphabet for the language Subst(L) is the union of the alphabets of all the Lx_k languages, and that alphabet may or may not share any symbols with the alphabet of L.

If L is the set of strings of 0s and 1s with at least two consecutive 0s, and L₀ = {w $\mid$ w matches ($\S$+$\aleph$)⁺} and L₁ = {$\varepsilon$, a, ba} then Subst(0) = L₀ = {w $\mid$ w matches ($\S$+$\aleph$)⁺} and Subst(1) = L₁ = {$\varepsilon$, a, ba} . Subst(100) = {w $\mid$ w in Subst(1)Subst(0)Subst(0)} = {$\S$, $\S$$\aleph$, $\aleph$$\S$, $\aleph$, a$\S$, a$\S$$\aleph$, a$\aleph$$\S$, a$\aleph$, ba$\S$, ba$\S$$\aleph$, ..., a$\aleph$$\S$$\aleph$$\S$$\aleph$, ...}. That is, Subst(100) is all possible ways of drawing a string from L₁, i.e., {$\varepsilon$, a, ba}, followed by two draws from L₀ = {w $\mid$ w matches ($\S$+$\aleph$)⁺}. Subst(L) is the set of strings over an alphabet of {a,b,$\S$,$\aleph$} where each b must followed immediately by an 'a' (why?), and there must be at least one consecutive pair of $\S$ and/or $\aleph$ (why?).

Theorem: If L is a regular language over an alphabet Σ and for each symbol, x_k in Σ, there is an associated regular language Lx_k, then Subst(L) is a regular language.

If L and all Lx_k's are regular languages then there are DFAs that recognize L and each of the Lx_k's. Call these DFAs M (for L) and Mx_k (for each Lx_k). To construct an NFA with $\varepsilon$ transitions for Subst(L), do as follows.

• Make a copy of M called M'
• For each transition in M' from state q_i to q_j on input symbol x_k, splice in the DFA for Lx_k, by
  • make a copy of each Mx_k, call it Mx_k'
  • add an $\varepsilon$ transition from q_i to the start state of Mx_k'
  • add an $\varepsilon$ transition from each accepting state of Mx_k' to q_j.

The resulting NFA recognizes Subst(L) and thus Subst(L) is a regular language.

Decision Properties of Regular Languages

The decision properties of the regular languages include

• equivalence test of languages
• test for emptiness of a language
• test for all strings over an alphabet

Equivalence test of two regular languages is decidable

Theorem: If L₁ is a regular language and L₂ is a regular language then there is an algorithm that determines whether L₁ and L₂ are the same language.

We described the proof sketch above under Kinds_of_properties/Decision_properties and do not repeat that here.

Test of whether a regular language is empty is decidable

Theorem: If L is a regular language then there is an algorithm that determines whether L is the empty language ({ } or $\phi$).

There is a unique minimal-state DFA over an alphabet, Σ, that accepts the empty language -- it is a DFA with only one state, which is a non-accepting state, and all transitions for all alphabet members loop back to that one state. Given a finite representation of a regular language use the same process as described earlier of translating the input to a DFA, minimize the DFA, and see if its identical to the single-state DFA just described. If the DFAs are identical then L is empty, else its not empty.

Test of whether a regular language is Σ* is decidable

Theorem: If L is a regular language then there is an algorithm that determines whether L is Σ*.

Do very much as described immediately above with one small change.

There is a unique minimal-state DFA over an alphabet, Σ, that accepts Σ* -- it is a DFA with only one state, which is an accepting state, and all transitions for all alphabet members loop back to that one state. Given a finite representation of a regular language translate the input to a DFA, minimize the DFA, and see if its identical to the single-state DFA just described. If the DFAs are identical then L is Σ*, else its not.

Properties of Deterministic Context Free Languages

Properties of Context Free Languages

Closure Properties of CFLs

The CFLs are closed under

• Union
• Concatenation
• Kleene Closure
• Substitution

In contrast to the regular languages, the CFLs are not closed under complementation and the CFLs are not closed under intersection.

CFLs are closed under Union

Theorem: If L₁ and L₂ are both CFLs, then L₁$\cup$ L₂ is a CFL.

If L₁ and L₂ are CFLs then each has an associated CFG, G_L1 and G_L2, that generates the respective languages. Assume that the names of the variables in the two CFGs are disjoint (so no possibility of confusion). To construct a CFG for L₁$\cup$ L₂, call it G_{L1$\cup$ L2}, create a new start symbol, S_{L1$\cup$ L2}, with two associated productions, one to the start symbol of G_L1 and one to the start symbol of G_L2 (i.e., add S_{L1$\cup$ L2} $\rightarrow$ S_L1 $\mid$ S_L2). G_{L1$\cup$ L2} is a CFG that generates L₁$\cup$ L₂, so L₁$\cup$ L₂ is a CFL.

CFLs are closed under Concatenation

Theorem: If L₁ and L₂ are both CFLs, then L₁L₂ is a CFL.

If L₁ and L₂ are CFLs then each has an associated CFG, G_L1 and G_L2, that generates the respective languages. Assume that the names of the variables in the two CFGs are disjoint (so no possibility of confusion). Assume the name of the start symbol for G_L1 is S_L1 and that the name of the start symbol for G_L2 is S_L2. To create a CFG for L₁L₂, create a start symbol S_L1L2 with a single production to S_L1S_L2 (i.e., add S_L1L2 $\rightarrow$ S_L1S_L2). G_L1L2 is a CFG that generates L₁L₂, so L₁L₂ is a CFL.

CFLs are closed under Kleene Closure

Theorem: If L is a CFLs, then L* is a CFL.

We've previously used the Kleene closure or repetition operator only in reference to regular languages, but the operation applies to languages of any class. L* is the set of strings w that are composed of 0 or more concatenated substrings, w_i, where each w_i is a string in L.

If L is a CFL then there is a CFG, G_L, that generates L, with a start symbol that we'll call S_L. To create a CFG for L*, create a new start symbol, call it S_L*, with two productions, one to $\varepsilon$ and one to S_LS_L*. (i.e., add S_L* $\rightarrow$ $\varepsilon$ $\mid$ S_LS_L*). G_L* is a CFG that generates L*, so L* is a CFL.

CFLs are closed under Substitution

Theorem: If L is a CFL over an alphabet Σ and for each symbol, x_k in Σ, there is an associated CFL Lx_k, then Subst(L) is a CFL.

If L is a CFL then there is a CFG that generates L, call it G_L. If all Lx_k's are CFLs then there are CFGs that generate each, call them G_Lxk respectively. To create a CFG that generates Subst(L), G_S(L), replace every instance of an alphabet/terminal symbol in the productions of G_L with the start symbol for the grammar of the language corresponding to that symbol, and make the productions of G_S(L) be the union of all the revised productions of G_L and all the productions of all the G_Lxk's. G_S(L) is a CFG that generates Subst(L), so Subst(L) is a CFL.

CFLs are not closed under complementation

Intuitively, you might think that given a PDA for a language, we can just invert the accepting and non-accepting states as we did with FAs, but the added complexity of the stack makes this insufficient for showing the CFLs are closed under complement.

To say that a language class is not closed under an operation, is to say that there exists at least one language (for a unary operation such as complementation) or at least two languages for a binary operation such as intersection, that don't result in a language of the specified class. So, finding such a counterexample is sufficient for showing the CFLs are not closed under complementation, for example. But finding such a counterexample can be nontrivial. How do we show that the complement of a particular CFL is not a CFL? We would have to show. that there is no CFG or PDA for it.

Consider the language L = {aⁱb^jc^k | i,j,k $\geq$ 0 and i $\neq$ j or j $\neq$ k}. CFG Exercise 2 in chapter "Context Free (Type 2) Grammars and Languages" asked you to give a CFG for this language, thus demonstrating that it is a CFL. The complement of L is {anbncⁿ | n $\geq$ 0}, which is not a CFL because ...

Properties of Context Sensitive Languages

Closure Properties of CSLs

The CSLs are closed under

• Complement
• Union
• Intersection
• Concatenation
• Kleene Closure

However, the CSLs are not closed under substitution.

The CSLs are closed under Complement

If L is a CSL then its complement, L^c, is a CSL. If L is. a CSL then there is a linear bounded TM, M_L, that recognizes L, and that halts on all inputs. A linear bounded TM for L^c can be created that calls M_L as a subroutine and that accepts if M_L rejects, and that rejects if M_L accepts.

The CSLs are closed under Union

If L₁ and L₂ are CSLs then L₁ $\cup$ L₂ is a CSL. If L1 and L2 are CSLs then there are CSGs, G_L1 and G_L2, that generate L₁ and L₂ respectively. To construct a CSG to generate L₁ $\cup$ L₂ copy all the productions G_L1 and G_L2 with variables renamed as necessary so as to not confuse variables from different grammars, and create a start symbol S_{L1 $\cup$ L2} for the new grammar, G_{L1 $\cup$ L2}, with two productions S_{L1 $\cup$ L2} $\rightarrow$ S_L1 and S_{L1 $\cup$ L2} $\rightarrow$ S_L2. This new grammar is a CSG since the new productions are all noncontracting, and it generates L₁ $\cup$ L₂.

The CSLs are closed under Intersection

If L₁ and L₂ are CSLs then L₁ $\cap$ L₂ is a CSL.

The CSLs are closed under Concatenation

If L₁ and L₂ are CSLs then L₁L₂ is a CSL.

The CSLs are closed under Kleene Closure

If L is a CSL then L^*, is a CSL. We can say instead that L⁺ = L* - $\varepsilon$ is a CSL if it is important to exclude $\varepsilon$.

The CSLs are not closed under Substitution

A table from the first edition of Hopcroft and Ullman on closure properties of languages in the Chomsky hierarchy show that the CSLs are not closed under substitution, but the table from the second edition show that the CSLs ARE closed under substitution.

Properties of Recursive Languages

As I have already noted under section "Turing Machines and Language Classes/Recursive languages", the definitional characteristic of the class of recursive languages is that there is a TM that recognizes the language and that is guaranteed to halt in both accept and reject cases. Because of this gaurantee, recognition of a recursive language is said to be decidable. We also say that the recursive languages are recognized by an algorithm. Unlike all the other language classes discussed so far, there is no class of grammar that precisely delimits the recursive languages, though of course there are grammars that generate a subset of the recursive languages, notably CSLs.

Closure Properties of Recursive Languages

The recursive languages are closed under

• Complement
• Union
• Intersection
• Concatenation
• Repetition or Kleene Closure

However, the recursive languages are not closed under substitution.

Since there is no equivalent class of grammars for the recursive languages, all our arguments about closure (or not) of recursive languages will be based on TMs.

The Recursive languages are closed under Complement

If L is a recursive language, then there is a TM, call it M_L, that recognizes L and that is guaranteed to halt for all accept cases and in all reject cases. Create a new TM, M_L', that calls M_L as a subroutine. If M_L returns accept for a input string, then M_L' returns reject. If M_L returns reject for a input string, then M_L' returns accept. M_L' accepts the complement of L, and always halts, so the complement of L is recursive.

The Recursive languages are closed under Union

If L₁ is a recursive language and L₂ is a recursive language, then L₁ $\cup$ L₂ is recursive. Let M_L1 and M_L2 be the TMs recognizing L₁ and L₂ respectively and each is gauranteed to halt. From M_L1 and M_L2 we construct an always halting TM, M_L1$\cup$L2 , for L₁ $\cup$ L₂. Since TMs and computers are equivalent in terms of what can be computed, we represent M_L1$\cup$L2 in programming language pseudocode with the understanding that this can be translated to a TM.

<M_L1$\cup$L2 , w> = BOOLEAN FUNCTION Union (M_L1, M_L2, w) { IF M_L1(w) == accept OR M_L2(w) == accept THEN RETURN accept ELSE RETURN reject}

Each of the component TMs for L₁ and L₂ are being used as subroutines. The construction for M_L1$\cup$L2's behavior covers all conditions and is gauranteed to halt.

The Recursive languages are closed under Intersection

If L₁ is a recursive language and L₂ is a recursive language, then L₁ $\cap$ L₂ is recursive. Let M_L1 and M_L2 be the TMs recognizing L₁ and L₂ respectively and each is gauranteed to halt.

<M_L1$\cap$L2 , w> = BOOLEAN FUNCTION Intersection (M_L1, M_L2, w) { IF M_L1(w) == accept AND M_L2(w) == accept THEN RETURN accept ELSE RETURN reject}

The Recursive languages are closed under Concatenation

If L₁ is a recursive language and L₂ is a recursive language, then L₁L₂ is recursive. Let M_L1 and M_L2 be the TMs recognizing L₁ and L₂ respectively and each is gauranteed to halt. At a high level,

<M_L1L2 , w> = BOOLEAN FUNCTION Concatenation (M_L1, M_L2, w) {

FOR each of the |w|+1 ways to partition w into xy

           IF M₁(x) == accept and M₂(y) == accept THEN RETURN accept

RETURN reject

}

The Recursive languages are closed under Kleene Closure

If L is a recursive language then L* is recursive. Let M_L be the TM recognizing L and that is gauranteed to halt.

<M_L*, w> = BOOLEAN FUNCTION Repetition (M_L, w) {

FOR each of the 2^|w|-1 ways to partition w into x₁x₂…x_k,

             IF M_L(x_i) == accept for all x_i in x₁x₂…x_k THEN RETURN accept // can implement as a loop

RETURN reject

}

The Recursive Languages are not closed under Substitution

If you are given a recursive language R, and each symbol in R’s alphabet corresponds to a recursive language too, then the language that results from applying the substitution to R is not necessarily recursive. See the end-of-chapter exercises below for more.

Runtime Complexity

Many students who are taking a class on formal languages, automata, and computation will have already studied algorithm efficiency, perhaps in the form of big-O notation. Runtime efficiency is typically regarded as a characteristic of recursive languages (i.e, membership algorithms defined by always-halting TMs or computer programs), which is why we address efficiency in this chapter on properties of the recursive languages. It would make less sense to talk about efficiency in the case of undecidable problems, but a project asks you to investigate the relevance of efficiency and undecidable problems.

Big-O notation is used to indicate an upper bound on runtime cost, or space requirements or some other resource, but we will focus on time initially. Precisely, if n is a measure of the size of the input to a procedure, and I say that the procedure is O(f(n)), then that means that for big enough values of n, the procedure’s actual runtime g(n) ≤ c*f(n), for n ≥ t. t is the value that tells us what value of n is “big enough”. In English, this tells us that the actual runtime of a procedure, g(n), never exceeds some constant c times f(n) for big enough n.

Where do the values of constants c and t come from? For practical purposes they could come from experiments with a procedure on different size n, or from analysis, but for theoretical purposes (at least to many theoreticians much of the time) we don’t care. Its enough to know that these constants exist, and that they depend on the algorithm’s implementation details (i.e., what is the language of implementation, the hardware the procedure is run on, etc), and this is precisely why we don’t care about their particular values from a theoretical standpoint. And so we typically don’t fret about the constants and simply say the procedure is O(f(n)), where f(n) is typically a member of some general and simply-stated class of functions, like n⁰ or 1 (constant), log n (logarithmic), n (linear), n log n, n² (quadratic), n³, 2ⁿ (exponential), and n! (combinatoric). I have listed these simply-stated function classes in order of increasing complexity or growth rate. That is, n log n will always be less than n² for sufficiently sized n, for example.

If I say that an algorithm runs in O(n³) time, then that means the actual run time, g(n), of the procedure will be bounded above for big enough n: g(n) ≤ c*n³, for n ≥ t. Notice that if a algorithm is O(n), for example, then it is also O(n²) and O(n³) and … and O(n!). Convince yourself that this is true given the formal definition of big-O notation. The problem, however, with saying that an algorithm’s runtime is O(n³) when it is also O(n²) is that the former is misleading because n³ is not as "tight" an upper bound as is possible. This concern with tightly characterizing the run time complexity of an algorithm is one reason that we also like to characterize algorithms by lower bounds. Ω(f(n)) means that for big enough values of n, the algorithm’s actual runtime g(n) ≥ c*f(n), for n ≥ t. The constants for a big-Omega characterization of an algorithm may be different than the constants for a big-O characterization of the same algorithm, but again, we don’t typically care about the constants. If an algorithm can be characterized by both O(f(n)) and Ω(f(n)) (i.e., upper and lower bounds for the same f(n)) then we consider f(n) as a tight characterization of the algorithm’s runtime, and we signify this with big-Theta notation Θ(f(n)) means c₁*f(n) ≥ g(n) ≥ c₂*f(n) for n ≥ t (t = max(t₁,t₂)).

It would be easy to dive still deeper into complexity theory, but under the assumption that you have or will look at this more deeply in an advanced course on algorithm analysis, I’ll sum up with three miscellaneous points. First, its common to say that if an algorithm is characterized by O(f(n)) behavior (or Omega or Theta), then the actual runtime, g(n) = O(f(n)). This may seem like an odd use of the equality symbol and it is indeed an odd convention (if I had my druthers I might have overloaded the membership symbol instead, so g(n) ∈ O(f(n))). Second, when using any of the notations it is appropriate to say “in the worst case” or “the best case” or the “average case”, though you might think that big-O naturally corresponds to the worst case, big-Omega to the best, and big-Theta to the average, and you wouldn’t be wrong in some sense. But imagine cases, in say AI, where there is a partial ordering on run times, and in one subset of instances performance ranges from best to worst for that subset, while a different subset has a different values for best, average, and worst. In any case, you’ll hear and read that worst case for insertion sort is O(n²) and best case is O(n), as but one example where O-notation serves double duty.

Thirdly, in theory settings, particularly in introductory texts like this one, worst case performance is taken to be of most importance – just how bad can this algorithm be!?! Worst case performance that is greater than polynomial (i.e., with growth rate greater than n^p for any positive value of p), notably O(2ⁿ) and O(n!), will determine whether a problem is "intractable".

In short, using big-O (or big-Omega or big-Theta) there is a hierarchy of language (problem) classes: O(1) $\subset$ O(log n) $\subset$ O(n) $\subset$ O(n log n) $\subset$ O(n²) $\subset$ O(n³) $\subset$ O(2ⁿ) $\subset$ O(n!). There are many other language classes defined in terms of runtime of course.

Intractability

A dictionary definition of an "intractable problem" is one that is extremely hard or impossible to solve. Problems that are in RE but not recursive are undecidable, and are intractable in a strong sense. Problems that don’t have solutions that are representable by Turing machines at all (i.e., non-RE) are intractable in the strongest sense.

But what we will usually mean by intractability are problems for which the only known solution procedures are greater than polynomial in time and/or space as a function of input size (e.g., exponential, combinatorial).

P and NP

P and NP are two broad classes of languages (problems). Any deterministic algorithm that runs in O(n^p) time, where p is any real number constant, belongs to class P(olynomial). Remember that O(n^p) will include other, smaller growth rate functions, like n log n, as well. An example of a problem in P is finding the minimum weight spanning tree (MWST) of a weighted graph. Kruskal’s algorithm is a polynomial time algorithm that finds the MWST.

Any algorithm that cannot be characterized by polynomial deterministic runtime is not in P.

Figure NPprocedure: A non-deterministic polynomial algorithm is one that pursues multiple paths (of instantaneous descriptions) “simultaneously” towards a solution (brute-force, breadth-first), where each path length is a polynomial function of input size.

NP, standing for Nondeterministic Polynomial, is the class of algorithms, which when run on a nondeterministic TM that is capable of simulating all possible solution paths in parallel, will run in time that is polynomial as a function of the input size. Of course, a NTM cannot simulate all paths in parallel, so a more practical expression of the NP class are algorithms where solution paths are a polynomial function of their input in length. NP problems have a hard to solve, "easy" to validate character. Finding a solution may require exploring a large number of paths, perhaps O(2ⁿ) or O(n!) paths, but each path is polynomial in length, and thus a given solution can be validated in polynomial time, as illustrated in Figure NPprocedure.

An example of an NP problem is the Traveling Sales Problem (TSP) with a weighted graph. That is, expressed as a language, the TSP asks whether there is a cycle of all nodes in a weighted graph with a total weight that is a specified maximum or less. If so, the encoded graph is a member of the language of graphs for which there is an acceptable tour, otherwise it is not. It is standard that a satisfying tour accompany a 'yes' answer. There are at least O(n!) number of paths (hard to find) of length n, where n is the number of vertices, so each solution is O(n) in length (easy to validate).

Every problem in P is also in NP, so P $\subseteq$ NP. What is strongly suspected, but not yet proved is that P is a proper subset of NP, P $\subset$ NP. Despite suspicions to the contrary, you will hear that demonstrating that P $=$ NP (or P $\neq$ NP) is one of the biggest open problems in computational theory. In light of all this, we will call a problem intractable if it is in NP, and not known to be in P.

The Satisfiability Problem is NP

The TSP is one example of an NP problem that is not known to be in P. A second, and especially important example of an NP problem, which is not known to be in P, is satisfiability, or SAT for short.

The SAT problem is

• Given: a Boolean expression over n variables, say in conjunctive normal form
• Find: an assignment of truth values to all n variables such that the entire expression is true.

For example, say we are given (¬x₀ ⋁ x₁ ⋁ x₂) $\bigwedge$ ( x₀ ⋁ ¬x₁ ⋁ x₂) $\bigwedge$ (¬x₀ ⋁ ¬x₁ ⋁ ¬x₂) $\bigwedge$ (¬x₀ ⋁ ¬x₁ ⋁ x₃).

Since there are 4 variables, x₀ through x₃, this is called a 4-SAT problem. There are 2⁴ combinations of assignments to the four variables. An assignment that renders the entire expression true is x₀ = false, x₁ = true, x₂ = true, x₃ = false: (¬false ⋁ true ⋁ true) $\bigwedge$ ( false ⋁ ¬true ⋁ true) $\bigwedge$ (¬false ⋁ ¬true ⋁ ¬true) $\bigwedge$ (¬false ⋁ ¬true ⋁ false) = (true ⋁ true ⋁ true) $\bigwedge$ ( false ⋁ false ⋁ true) $\bigwedge$ (true ⋁ false ⋁ false) $\bigwedge$ (true ⋁ false ⋁ false). Since there is at least one assignment that renders the entire expression true, the expression is satisfiable. If all assignments led to a true expression, then the expression would be a tautology, but that need not be the case for the expression to be satisfiable.

Figure SATisNP: In the worst case the algorithm at top may need to iterate through the FOR loop 2ⁿ times.

Consider this 2-SAT problem: (¬x₀ ⋁ ¬x₁) $\bigwedge$ ( x₀ ⋁ ¬x₁) $\bigwedge$ (¬x₀ ⋁ x₁) $\bigwedge$ (x₀ ⋁ x₁). There are 2² assignments. Confirm that none of the four assignments result in the entire expression being true. This expression in unsatisfiable (aka the expression is a contradiction).

Figure SAThillclimbing: Max_restarts and Max_tweeks are set by the user. "Tweeks" are small changes to truth assignment, such as flipping the truth value of one variable (e.g., flip the value of x_k from true to false). When this algorithm answers 'no' it will only be correct with some probability since the procedure will typically stop short of examining all possible assignments. Nonetheless, enough assignments will have been examined typically to insure high probability of correctness in the 'no' case (and certainty of correctness in the 'yes' case).

SAT is NP because there are an exponential number of possible solutions, 2ⁿ, for n variables, but each solution is size n. In the worst case, an algorithm like that shown in Figure SATisNP, might have to examine all the assignments, but in point of fact, it's not generally that bad. Even problems for which a solution is nondeterministic polynomial, and there is no known polynomial time solution, its very often the case that answers can be found quickly. The SATisfiability problem is NP, but a very simple procedure that works well in practice is hill-climbing in search of a value assignment that makes an entire Boolean expression true. In this approach, a solution is guessed randomly, checked for satisfaction of the expression, and revised or simply guessed again. Details of a procedure are shown in Figure SAThillclimbing. Hill climbing, btw, is a popular greedy search procedure that is used in many experimentally-oriented fields, like AI, which are often fast and yield satisfactory results. In general, hill-climbing is one of many ways of effectively dealing with intractability in practice.

Deterministic Polynomial Time Reductions

We have previously studied reductions of a language/problem Q to a language/problem R. Recall that if we say Q reduces to R then if we have a solution for R we can use it to create a solution for Q; R is at least as hard as Q (else a solution for R would not assure a solution for Q). As one implication of this hardness observation, to show that R has a certain hardness characteristic (i.e., undecidability, intractability), or something “worse”, then show a correct reduction from a procedure that we know has that hardness characteristic to R. Previously, this hardness characteristic was undecidability. Now, it can be intractability too.

We know that SATisfiability is in NP (with no known solution in P) – we constructed an algorithm for it that was clearly NP in Figure SATisNP. We can reduce SAT to another problem, say solving simultaneous integer linear inequalities, thereby showing that this latter problem is "at least" NP. Consider the earlier SAT problem: (¬x₀ ⋁ x₁ ⋁ x₂) $\bigwedge$ ( x₀ ⋁ ¬x₁ ⋁ x₂) $\bigwedge$ (¬x₀ ⋁ ¬x₁ ⋁ ¬x₂) $\bigwedge$ (¬x₀ ⋁ ¬x₁ ⋁ x₃). This is easily translated to an integer linear program (ILP) by replacing each Boolean variable x_k with an integer variable t_k, and replacing each negated variable ¬x_k with (1 - t_k). That's the reduction! So, the example SAT problem becomes the ILP:

(1-t₀) + t₁ + t₂ >= 1

t₀ + (1-t₁) + t₂ >= 1

(1-t₀) + (1-t₁) + (1-t₂) >= 1

(1-t₀) + (1-t₁) + t₃ >= 1

A solution to this ILP is

t₀ = 0

t₁ = 1

t₂ = 1

t₃ = 0

which can be mapped to a solution to the SAT problem, again through an easy substitution: x_k = false iff t_k = 0, and x_k = true iff t_k = 1. Confirm the correctness of this substitution to the SAT problem. The significance of all this is, again, that an algorithm for solving the ILP can be adapted to solving SAT. Moreover, the adaptation of the solution is easy in this case -- its O(n), where n is the number of source variables t_k, and also number of target variables x_k. So, if we should ever find an efficient, deterministic polynomial time algorithm, O(n^p), for solving ILPs, we will have a polyomial time algorithm for solving SAT, since O(n^p) + O(n) = O(n^p)!

In general, to the idea of reduction, we add a constraint that in cases where we care about algorithm complexity, the reduction must be polynomial in time using a deterministic algorithm, so that if efficient polynomial time algorithms are found for what are currently regarded as intractable problems, the cost of adapting the more efficient solutions to still other problems does not push the adaptation back into intractable territory.

In the case of SAT and ILP, we have a deterministic polynomial time (i.e., O(n)) reduction from SAT to ILP. Confirm that we can also construct a deterministic polynomial time reduction from ILP to SAT (also of deterministic O(n) time). So these problems are of comparable complexity. This need not always be the case, and in general the reduction in one direction may be more costly than the other direction, but still O(n^p) for it to be a deterministic polynomial time reduction.

NP Completeness

A problem Q is NP hard if every problem in NP deterministically polynomial reduces to Q (i.e., Q is at least as hard as every NP problem). Moreover, if (1) Q is also in the class NP, and (2) every problem in NP deterministic polynomial reduces to Q, then Q is said to be NP complete. Note that there are two conditions, as just stated, that have to be satisfied for a problem to be NP complete.

So that this is concrete, let’s say that Q is SAT. If we can show that every problem in NP reduces to SAT, then that says that a solution to SAT can be adapted to solve every other NP problem as well. And moreover, because the reductions from all NP problems to SAT will be polynomial time reductions, then if an efficient deterministic polynomial time solution is ever found for SAT (i.e., if SAT $\in$ P), then every problem in NP can be solved in deterministic polynomial time, and P $=$ NP. That's significant!

But how do we show that every problem in NP reduces to SAT in polynomial time? There are an infinite number of problems/languages in NP !

We know that every problem in NP is solved by a non-deterministic Turing Machine that always halts, and we can express a "generic" NDTM for any NP problem in terms of SAT. This is one insight of Cook's Theorem.

Cook's Theorem

Cook’s Theorem says that every problem in NP (i.e., a question of membership of an input w in the language of any non-deterministic Turing Machine, NTM, assured of halting) can be deterministically polynomial-time reduced to SAT (i.e., a question of whether a Boolean expression is satisfiable).

How can we reduce <NTM, w> to a Boolean expression, E_NTM,w, where E_NTM,w is judged satisfiable iff NTM accepts w?

Any NP problem, by the definition of NP, has paths of configurations or instantaneous descriptions (i.e., solution or nonsolution paths) that are each O(n^p) in length (i.e., a (non)solution is polynomial in the size of the input, n -- remember that this is why NP solutions are 'easy' to validate). Because each transition of NTM can move its read/write head at most cell on its tape, and can only write at most one symbol of its tape, the longest that a single instantaneous description (ID) can become is also O(n^p) since there is a maximum of O(n^p) moves along any path of IDs by NTM. Cook therefore posited a matrix of O(n^p) rows, each an ID, and O(n^p) columns, each corresponding to a tape cell in an ID. Thus, each cell of the matrix is an (ID, Tape Cell) pair. Moving down the rows correspond to making moves along a path of IDs, and making a change in a tape cell is the change to that cell in moving from one ID to the next. Without loss of generality, we assume that NTM uses a one-way infinite tape.

Figure Cook'sThmMatrix: A O(n^2p) matrix that is a schema for all possible trajectories of a nonderministic TM that represents an NP language, on an input of length n.

The size of this matrix is O(n^p) $\times$ O(n^p) = O(n^2p) as shown in Figure Cook'sThmMatrix.

Importantly, this matrix is strictly a theoretical construct, important because it puts bounds on the size of the problem to be reduced. The matrix does not represent an actual run of NTM along any one path -- it couldn't because if running NTM were part of the reduction, then the reduction would not necessaily be deterministic polynomial time! Rather, the matrix is a schema that represents the totality of the set of possible paths that can be pursued by NTM on w, just as the reduction to E_NTM,w will imply the set of of possible n-tuple truth value assignments to the n variables of the E_NTM,w. Also, recognize that the O(n^p) $\times$ O(n^p) matrix is an upperbound on the dimensions of a possible path followed by NTM. Some problems will require fewer rows/IDs than O(n^p) and/or fewer tape cells in an ID than O(n^p). But for convenience of demonstration, we think of the upperbounds as the actual dimensions, and we assume that every row is filled with blanks of unused rightmost tape cells within an ID up to the O(n^p) limit on columns, and we assume that the row/ID corresponding to entering an accepting state is duplicated up to the O(n^p) limit on rows.

Ask yourself, if you were given the definition of NTM, and an input w, how would you confirm that an arbitrary matrix of IDs, as described above, followed from the NTM definition and that NTM accepted w.

Your procedure for analyzing a matrix would necessarily have to look at the following:

1. Does the first row/ID of the matrix correspond to the initial ID, that is to NTM being in its start state, q₀, and NTM's read/write head being at the left end of the input w, followed by blanks?
2. Does the last row/ID of the matrix indicate that the NTM state is an accepting state, and if so this indicates acceptance, and non-acceptance otherwise?
3. For each pair of consecutive rows/IDs, does the second of the pair follow from the first given the definition of NTM's transitions, $\delta$?

You could define this as an automated procedure for taking NTM and w, and you could embed this in a loop to look at all possible matrices. If any one of those matrices indicated acceptance of the input, then your procedure would indicate that NTM accepted w, and if all matrices corresponded to non-acceptance, then your procedure would reject w as a member of L(NTM).

Presumably you recognize the analog between determining whether one of many NTM paths accepts and determining whether one assignment of truth values satisfies a Boolean expression. So, lets convert the algorithm into a SAT problem, E_NTM,w, which you can think of a "logic program" for those who have used Prolog or another logic programming language.

Figure Cook'sInitialConditions: A Boolean subexpression representing initial conditions that must be satisfied in a valid solution path by an NTM accepting w.

Step 1: To translate step 1 above into a Boolean subexpression, the first row/ID of the matrix corresponds to NTM being in its start state, q₀, and NTM's read/write head being at the left end of the input w, followed by blanks. Introduce Boolean variables corresponding to the following

• One Boolean condition is that the current state of ID 0 is the start state, q₀.
• One Boolean condition is that the read/write head of ID 0 is at tape location 0.
• For each of the symbols in the input, w, from i = 0 to i = $\mid$w$\mid$—1, create a Boolean condition that the value of the ith tape cell in ID 0 is the ith symbol of w.
• For each of the tape locations in ID 0 from $\mid$w$\mid$ to the end (i.e., O(n^p)) create a Boolean condition that the value of the cell location is the blank.

Conjoin these Boolean variables into one Boolean subexpression. Call it E_{NTM,w,initial}. This is illustrated in Figure Cook'sInitialConditions. Note that the cost of creating this subexpression is linear relative to the input size, $\mid w\mid$ = O(n).

Figure Cook'sFinalConditions: Boolean subexpression representing the final conditions that must be satisfied in a valid solution path by an NTM accepting w.

Step 2: To translate step 2 into a Boolean subexpression, that the last row/ID of the matrix indicates that the NTM state is an accepting state,

• For each accepting state in NTM's definition, create a Boolean variable that reflects whether the current state of the last ID in row O(n^2p) is that accepting state.

Disjoin these Boolean variables into one Boolean subexpression. Call it E_{NTM,accepting}. This is illustrated in Figure Cook'sFinalConditions. Note that this subexpression does not depend on a particular w, and the cost of creating this subexpression is therefore constant time relative to the input size, O(1).

Figure Cook'sIntermediateConditions: Each transition, such as that for $\delta$(q₃, a) in red, may have more than one outcome in a nondeterministic TM; of the two possible outcomes in the figure, one is reflected in the matrix, in green, and one is not reflected, in purple.

Step 3: To translate step 3, that for each pair of consecutive rows/IDs, the second of the pair should be immediately obtainable from the first of the pair given the definition of NTM's transitions, $\delta$. The subexpression that we write should specify conditions that must apply to each row/ID of the matrix (and its successor row/ID), except the last row, starting with row/ID 0.

The translation requires going through the transitions of NTM's $\delta$ functions and composing subexpressions for each. Figure Cook'sIntermediateConditions illustrates the translation of one transition for (q₃, a). For each possible outcome, say (q₅, b, R) for example, becomes a set of conjoined conditions, (cs_k+1= q₅ ∧ Loc_k+1 = j+1 ∧ Z_k+1,j = b). This must be repeated for each possible outcome of (q₃, a) listed in the transitions' function, as well as for each entry $\delta$(State, Input Symbol) pair listed in $\delta$. In the blue, the Figure additionally shows that for all cells other than the one under the read/write head, the values will remain the same between ID k and ID k+1.

Given what we have said so far, we would then have a general Boolean expression, of which Figure Cook'sIntermediateConditions only shows a small part, that stated conditions necessary to the validity between an ID k to ID k+1. Given a matrix we could then loop through the consecutive IDs and check them against this Boolean expression. But to fully reduce to SAT, we cannot use explicit looping, but must explicitely replicate the Boolean expression for each value of k, from ID 0 to the penultimate ID/row.

While the process of building the subexpression does not directly depend on a particular word, w, the number of terms we must write in the subexpression, call it E_{NTM,|w|,intermediate} depends on the size of w, i.e., the size of the matrix, O(n^2p).

Taking Steps 1-3 together, the Boolean expression representing the SAT problem can be written as

• E_NTM,w = E_{NTM,w,initial} $\bigwedge$ E_{NTM,accepting} $\bigwedge$ E_{NTM,|w|,intermediate}

There are factors that have not been directly addressed here, notably

• that rows after entering an accepting state can simply repeat in order to fill up to O(n^p) rows;
• that situations when the location of the R/W head is the leftmost location (i.e., so that there is no j-1 location) or rightmost cell (i.e., when there is no j+1 location);
• that there must be exactly one value (tape symbol) for each cell in the matrix, which precludes impossible states that could otherwise be considered by a SAT solver.

While important to the formal proof, these further details aren't needed to appreciate the genius of Cook's theorem, and for that matter the genius of conceiving of the concept of NP completeness generally. While the Boolean expression representing the SAT problem corresponding to an arbitrary NP problem is long and involved, it is so because it is general to an infinite number of NP problems. As we saw in relation to ILP and SAT, polynomial reductions between two specific problems are often much simpler.

Again, one consequence of demonstrating that SAT is NP complete is that if it is discovered that SAT has a deterministic polynomial time solution, and thus a member of P, then all NP problems have a polynomial time solution, if by no other means than using SAT as a subroutine, and thus P = NP.

Other NP Complete Problems

Knowing that SAT is NP complete, we can now show that other NP problems are NP complete by polynomial reducing SAT to these other problems. You’ll see that we are essentially reducing both ways. Cook’s theorem polynomial reduced from every NP problem to SAT, indicating that SAT was at least as hard as any other NP problem. This is illustrated in Figure AllNPsReducedtoSAT. And now, by polynomial reducing SAT is another NP problem, we are showing that the other problem is at least as hard as SAT. For example, we already showed that SAT polynomial reduces to ILP. With both directions of reduction demonstrated, we can say that the other problem (e.g., ILP) is comparable to SAT in complexity – it too is NP complete. In Figure ExtendingNPComplete, assume that ILP is L_k in row (1) column (a), and the two-way arrow indicates that SAT polynomial reduces to L_k, and vice versa. Since L_k has now been shown to be NP complete, all NP problems reduce to L_k as well, as shown in row (1) column (b).

Figure AllNPsReducedtoSAT: Cook's theorem shows that all NP problems polynomial reduced to SAT. Thus SAT is NP hard; all NP problems can use a procedure for solving SAT as a subroutine. And because SAT is itself NP, SAT is NP complete.

One important point to emphasize is that the other problem, L_k, can now be used in subsequent reductions to show that still other problems are NP complete, since the demonstrations of equivalent complexity are transitive. Furthermore, as illustrated in row (2) of Figure ExtendingNPComplete we can take another problem in NP, say Lj, and by showing that L_k reduces to Lj we have shown that every NP problem reduces to Lj as well, and so Lj is NP complete.

Figure ExtendingNPComplete: An explanation for expanding the known NP complete problems, as illustrated in this figure, is given in the main text.

By now a large number of problems have been shown to be NP complete. A question that you might be asking yourself is whether there is any problem in NP (and not known to be in P) that is not NP complete? Or not known to be NP complete? See the exercises on these questions.

Again, one consequence of demonstrating a large class of NP complete problems that are equivalent in terms of complexity is that if any one of them turns out to have a deterministic polynomial time solution, and thus a member of P, then they all have a deterministic polynomial time solution and P = NP.

Properties of Recursively Enumerable (or Unrestricted) Languages

The RE languages are the broadest class of languages that we will address, and the class of RE languages includes all other language classes that we have considered -- recursive languages, CSLs, CFLs, DCFLs, and regular languages. The RE languages are equivalently defined by unrestricted (Type 0) grammars and by TMs that may not halt on their input in the case where that input is not a member of the language defined by the TM.

We will start with the closure properties of RE languages, then talk about the inherent undecidability of other decision questions of RE languages. Because membership in RE languages that are not also recursive is undecidable, and therefore are not implementable by algorithms, we don't include issues of algorithmic runtime or space efficiency in this section.

Closure Properties of RE languages

The RE (aka unrestricted) languages are closed under

• Union
• Intersection
• Concatenation
• Repetition or Kleene Closure
• Substitution

However, the RE languages are not closed under Complement.

The RE languages are closed under Union

If L₁ is a RE language and L₂ is a RE language, then L₁ $\cup$ L₂ is RE. It is left as an exercise to show by construction of an unrestricted grammar or a TM for the language represented by L₁ $\cup$ L₂ that the RE languages are closed under union.

The RE languages are closed under Intersection

If L₁ is a RE language and L₂ is a RE language, then L₁ $\cap$ L₂ is RE. It is left as an exercise to show by construction of an unrestricted grammar or a TM for the language represented by L₁ $\cap$ L₂ that the RE languages are closed under intersection.

The RE languages are closed under Concatenation

If L₁ is a RE language and L₂ is a RE language, then L₁L₂ is RE. It is left as an exercise to show by construction of an unrestricted grammar or a TM for the language represented by L₁L₂ that the RE languages are closed under concatenation.

The RE languages are closed under Kleene Closure

If L is a RE language, then L* is RE. It is left as an exercise to show by construction of an unrestricted grammar or a TM for the language represented by L* that the RE languages are closed under Kleene Closure.

The RE languages are closed under Substitution

If L is a RE language and for each symbol, x_i, in the alphabet of L there is an associated RE language, then Subst(L) is RE. It is left as an exercise to show by construction of an unrestricted grammar or a TM for the language represented by Subst(L) that the RE languages are closed under substitution.

The RE languages are not closed under Complement

If L is a RE language then its complement, ${\bar {L}}$, is not necessarily RE. We can show this by example of an RE language RE with a complement that is definitely not RE. We have already given such an example earlier in the text. Its left as an exercise to find and understand the example.

Decision Properties of RE languages

We covered decidability and undecidability of selected computational problems, notably questions on the membership in recursively enumerable languages. The universal language, which we re-expressed as the halting problem (i.e., will the universal Turing machine always halt on its input) is undecidable (because M_U may not halt when its argument TM does not accept its input).

In general, undecidability can signify one of two conditions. Membership in L_u, for example, is undecidable in one sense, which is failure to say no and halt if a string is not in L_u. More broadly though undecidability could mean failure to answer at all and halt 'yes' cases and/or 'no' cases. This second, broader notion of undecidability would relate to languages outside of RE, so we don't deal with it here. We restrict ourselves to undecidability in the former case -- the 'no' case -- as relates to the RE languages.

Rice's Theorem

A yes/no question of the RE languages is trivial if the correct answer is either 'yes' in all cases (i.e., its a property of all the RE languages) or its 'no' in the case of all RE languages. Otherwise, its a non-trivial question or property. For example, the question of whether a given RE language is a regular language is a non-trivial question/property of the RE languages, since some RE languages are regular and some are not.

Rice's Theorem says that every non-trivial question of the RE languages is undecidable.

Suppose we have a yes/no question Q about the RE languages. Then L_Q is the set of RE languages for which Q=yes. Continuing our earlier example, if Q is "Is this language a regular language?" then L_Q is the set of regular languages. In fact, L_Q can be viewed as a language of languages, where you'll recall that each language in L_Q can be represented finitely by an automaton or grammar, and that each such finite representation can be expressed as a (binary) string. Because the questions Q vary widely, we'll always assume that each language in L_Q is a binary string representing a TM, regardless of whether it miight be represented in some other fashion (e.g., as a FA). Its also common to refer to L_Q as a property -- e.g., every member of L_Q has the property of being a regular language.

To phrase things differently, a non-trivial property, L_Q, of the RE

• is one for which { } $\subset$ L_Q $\subset$ L_RE, where L_RE is the language of binary encodings for all TMs (i.e., the RE languages);
• L_Q $\cap$ L_R = { }, where L_R is the language of binary encodings for all always-halting TMs (i.e., the recursive languages);

•A property of the RE languages is the subset of the RE languages with that property.

•For example

•the property of RE of being CFL is the set of CFLs.

•the property of being empty is the set {∅}.

•

•A property is trivial if it is either the set of all RE languages (universally true) or the empty set of languages (universally false). Otherwise the property is non-trivial.

•Note that the empty set (no languages at all), ∅, is different from {∅}, the set containing the empty language (which is accepted by a TM that accepts the empty language).

•Reminder: a set of languages can be represented by a set of strings, each representing a TM.

•Suppose L_P is the set of languages with non-trivial property P.

•

•Is the question of a language L’s membership in the L_P languages decidable or undecidable?

•

•More particularly, is the question of a Turing machine’s encoding of a language L’s membership in the Turing machine’s encodings of the L_P languages decidable or undecidable?

•

•Prove the question of a language L’s membership in the L_P languages is undecidable.

•Assume that membership in L_P is decidable. Then there is an algorithm, TM_P, that recognizes L_P.

•

•Regardless of non-trivial P, reduce L_U (the Universal Language aka the Halting Problem, known undecidable) to L_P, thus showing a contradiction with assumption that L_P is decidable.

Rice’s Theorem implies an infinite number of undecidable properties for recursively enumerable languages, and it does it in one fell swoop. Rice’s Theorem tells us that for sufficiently expressive languages undecidability is the norm rather than the exception.

Of the problems implied by Rice’s Theorem to be undecidable, there are different kinds. Its undecidable whether a TM accepts the empty set, or a non-empty set. Given intuitions about complementation, we might think of these questions as essentially the same, but in fact when dealing with RE languages that are not recursive our intuitions regarding complement may be misleading. In the case of the question of whether an arbitrary TM accepts the empty language is not RE – its not a property that can be tested by any TM. Whereas, the question of whether a TM accepts a non-empty language is RE (but not recursive).

Expanding the Classes of Languages

Any characteristic defines a set of languages for which the characteristic is true of all members. Any question defines a set of languages for which the answer to the question is 'yes'.

Exercises, Projects, and Discussions

RL Props Exercise 1: For each of the constructions described under Regular Languages are closed under Union, Concatenation, Kleene Closure, and Substitution, draw a visualization of the construction, choosing a way of visually representing the component DFAs in the construction, as well as the constructed NFA. Why do this exercise? Because many learners are visual learners, and undoubtedly all learners benefit from some visualization, be it mental imagery or manifest on 'paper'. An important skill for many or most in CS generally is an ability to visualize algorithms and data structures. This will undoubtedly continue to be a desirable skill even as AIs take over much of the software development burdon. As an aside, if you are interested in societal benefits of your efforts, consider and potentially act on the creation of educational materials in CS for the blind and hard of sight.

RL Props Exercise 2: For each of the constructions described under Regular Languages are closed under Union, Concatenation, Kleene Closure, and Substitution, give alternative arguments using regular expressions.

RL Props Exercise 3: For each of the constructions described under Regular Languages are closed under Union, Concatenation, Kleene Closure, and Substitution, give alternative arguments using regular grammars.

RL Props Exercise 4: Regular expressions were defined in terms of three operations -- concatenation, choice, and Kleene closure. Expand regular expressions based on closure properties for regular languages. The intent is not that you increase the representational power of REs, but that the expansion provides syntactic convenience and comprehensibility.

RL Props Exercise 5: Show that the regular languages are closed under reversal. That is, if L is a regular language then L^R is a regular language.

CFL Exercise 1: Show that the CFLs are not closed under intersection.

Project 1: Investigate the properties of the class of inherently ambiguous CFLs.

Project 2: Investigate NP problems that are not NP complete, or not known to be NP complete. Are there any such problems?

Project 3: Investigate superpolynmial algorithms that are subexponential.

Project 4: Investigate Closure properties of P, NP, and NP complete problems

Exercise RecursiveSubstition1: Give a demonstration that if you are given a recursive language R, and each symbol in R’s alphabet corresponds to a recursive language too, then the language that results from applying the substitution to R is not necessarily recursive.

Exercises (Closure Properties of RE languages) For each of the subsections above, demonstrate the truth value of the closure property as described.