# 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.

## 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 (e.g., the regular languages are those generated by regular grammars).

### 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$_1$ $\in$ CFLs ∧ L$_2$ $\in$ CFLs) → R(L$_1$, L$_2$), where L$_1$ and L$_2$ are languages and R is a property, such as union: if L$_1$ and L$_2$ are CFLs then L$_1$ $\cup$ L$_2$ is a CFL; the CFLs are closed under union.
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 those languages that are not also 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 correctly answers the question for which the TM was designed to answer, and halts, in all cases. 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.
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, 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 across all CFLs.
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$_1$ and L$_2$ are both regular languages, then L$_1$$\cup$ L$_2$ is a regular language.
Since L$_1$ and L$_2$ are each regular languages, there are DFAs M$_1$ and M$_2$, respectively, that recognize each. Construct an NFA with $\varepsilon$ transitions, M$_{1∪{\displaystyle\cup}2}$, for L$_1$ $\cup$ L$_2$ as follows.
* Create copies of M$_1$ and M$_2$, call the copies M$_1$' and M$_2$'.
* Create a start state for M$_{1∪{\displaystyle\cup}2}$, and add $\varepsilon$ transitions from that start state to each of the start states of M$_1$' and M$_2$'.
* Create a single accepting state for M$_{1∪{\displaystyle\cup}2}$, and add an $\varepsilon$ transition for each of the accepting states of M$_1$' and of M$_2$' to the accepting state of M$_{1∪{\displaystyle\cup}2}$.
* Change the accepting states of M$_1$' and M$_2$' to non-accepting states.
M$_{1∪{\displaystyle\cup}2}$ is an NFA that recognizes L$_1$ $\cup$ L$_2$ and thus L$_1$ $\cup$ L$_2$ is a regular language.

#### Regular Languages are closed under Intersection

Theorem: If L$_1$ and L$_2$ are both regular languages, then L$_1$ $\cap$ L$_2$ is a regular language.
Suppose L$_1$ and L$_2$ are regular languages over alphabet Σ. Then L$_1$ $\cap$ L$_2$ is regular. This must be so since L$_1$ $\cap$ L$_2$ = ~(~L$_1$ $\cup$ ~L$_2$) and the regular languages are closed under complement and union. But we can also directly construct a DFA that accepts L$_1$ $\cap$ L$_2$ from the DFAs that must exist for L$_1$ (M$_1$ = (Q$_1$, Σ , $\delta$$_1$, q$_1$, F$_1$)) and L$_2$ (M$_2$ = (Q$_2$, Σ , $\delta$$_2$, q$_2$, F$_2$)), respectively. The following is adapted from (pp. 59-60,; p. 137,).
M$_{1∩2}$ = (Q$_1$×Q$_2$, Σ, $\delta$ , [q$_{1,}$ q$_2$ ], F$_1$×F$_2$) that accepts L$_1$ $\cap$ L$_2$. For each pair of states from M$_1$ and M$_2$ 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$$_1$(q$_{1i}$, a), $\delta$$_2$(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$_1$ and L$_2$ are both regular languages, then L$_1$L$_2$ is a regular language.
The concatenation of languages L$_1$ and L$_2$, written L$_1$L$_2$, is {w$_1$w$_2$ | w$_{1j}$ $\in$ L$_1$ and w$_{2k}$ $\in$ L$_2$}. That is, any word from L$_1$ followed immediately by any word of L$_2$, is a string in the language of the concatenation.
Since L$_1$ and L$_2$ are each regular languages, there are DFAs M$_1$ and M$_2$, respectively, that recognize each. Construct an NFA M$_{12}$ with $\varepsilon$ transitions by
* copying M$_1$ and M$_2$ , call them M$_1$' and M$_2$',
* make the start state of M$_{12}$ be the start state of M$_1$',
* make the accepting states of M$_{12}$ be the accepting states of M$_2$',
* connect M$_1$' and M$_2$' by adding an $\varepsilon$ transition from each accepting state of M$_1$' to the start state of M$_2$', and
* change every accepting state in M$_1$' to be a non-accepting state.
M$_{12}$ is an NFA that recognizes L$_1$L$_2$ and thus L$_1$L$_2$ 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$_1$L$_2$...L$_m$ = {w$_1$w$_2$...w$_m$ | w$_{1j}$ $\in$ L$_1$ and w$_{2k}$ $\in$ L$_2$ 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$_1$w$_2$w$_3$...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. Subst is an overloaded function, much as that term is applied in certain programming languages. 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$_1$a$_2$...a$_m$ is a string in L, then Subst(w) = Subst(a$_1$)Subst(a$_2$)...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$_0$ = {w $\mid$ w matches ($\S$+$\aleph$)$^+$} and L$_1$ = {$\varepsilon$, a, ba} then Subst(0) = L$_0$ = {w $\mid$ w matches ($\S$+$\aleph$)$^+$} and Subst(1) = L$_1$ = {$\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$_1$, i.e., {$\varepsilon$, a, ba}, followed by two draws from L$_0$ = {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$_1$ is a regular language and L$_2$ is a regular language then there is an algorithm that determines whether L$_1$ and L$_2$ 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
### Closure Properties of DCFLs

The deterministic context free languages are not closed under union, concatenation, Kleene Closure, intersection, or substitution. Hopcroft and Ullman provide the following arguments.
   "Let L$_1$ = {0$^i$1$^i$2$^k$ | i,k >= 0} and L$_2$ = {0$^i$1$^k$2$^k$ | i, k >= 0}
   It is easy to show that L$_1$,and L$_2$ are DCFL's. However, L$_1$ $\cup$ L$_2$ is the CFL shown not to be a DCFL in Example10.1. Thus, the DCFL's are not closed under union.
   For concatenation, let L$_3$ = aL$_1$ $\cup$ L$_2$. Then L$_3$ is a DCFL, because the presence or absence of symbol a tells us whether to look for a word in L$_1$ or a word in L$_2$. Surely a* is a DCFL. However a*L$_3$ is not a DCFL. If it were, then L$_4$ = a*L$_3$ $\cap$ a0*l*2* would be a DCFL by Theorem 10.4. But L$_4$ = aL$_1$ $\cup$ aL$_2$. If L$_4$ is a DCFL, accepted by DPDA M, then we could recognize L$_1$ $\cup$ L$_2$ by simulating M on (imaginary) input a and then on the real input. As L$_1$ $\cup$ L$_2$ is not a DCFL, neither is L$_4$, and therefore the DCFL's are not closed under concatenation.
   The proof for <Kleene --DF> closure is similar, if we let L$_5$ = {a} $\cup$ L$_3$. L$_5$ is a DCFL,but L$_5$* is not, by a proof similar to the above.
   For homomorphism <a special case of substitution --DF>, let L$_6$ = aL$_1$ $\cup$ bL$_2$, which is a DCFL. Let L be the homomorphism that maps b to a and maps other symbols to themselves.Then h(L$_6$)=L$_4$, so the DCFL's are not closed under homomorphism <and thus they are not closed under substitution --DF>." Hopcroft and Ullman, pp. 265-266.

#### The DCFLs are closed under Complement

If L is a DCFL, then its complement, L$^c$, is a DCFL, because from a DPDA for L we can construct a DPDA for L$^c$ by swapping accepting and non-accepting states.

### Decision Properties of DCFLs

The deterministic context free languages are decidable on questions of membership of a string in the language, on whether the language is empty or not, on the equivalence of a DCFL to Σ*, and on the equivalence, or not, of two DCFLs.

#### Test of whether a DCFL is empty is decidable

Theorem: If L is a DCFL then there is an algorithm that determines whether L is the empty language ({ } or $\phi$).
The proof follows from the fact that decidability of the emptiness test is true of the class of CFLs. See that proof sketch for the wider class of CFLs.

#### Test of whether two DCFLs are equivalent is decidable

"Géraud Sénizergues (1997) proved that the equivalence problem for deterministic PDA (i.e. given two deterministic PDA A and B, is L(A)=L(B)?) is decidable, a proof that earned him the 2002 Gödel Prize. For nondeterministic PDA, equivalence is undecidable." deterministic_pushdown_automata

## 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$_1$ and L$_2$ are both CFLs, then L$_1$$\cup$ L$_2$ is a CFL.
If L$_1$ and L$_2$ 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$_1$$\cup$ L$_2$, call it G$_{L1∪{\displaystyle\cup}L2}$, create a new start symbol, S$_{L1∪{\displaystyle\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∪{\displaystyle\cup}L2}$ $\rightarrow$ S$_{L1}$ $\mid$ S$_{L2}$). G$_{L1∪{\displaystyle\cup}L2}$ is a CFG that generates L$_1$$\cup$ L$_2$, so L$_1$$\cup$ L$_2$ is a CFL.

#### CFLs are closed under Concatenation

Theorem: If L$_1$ and L$_2$ are both CFLs, then L$_1$L$_2$ is a CFL.
If L$_1$ and L$_2$ 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$_1$L$_2$, create a start symbol S$_{L1L2}$ with a single production to S$_{L1}$S$_{L2}$ (i.e., add S$_{L1L2}$ $\rightarrow$ S$_{L1}$S$_{L2}$). G$_{L1L2}$ is a CFG that generates L$_1$L$_2$, so L$_1$L$_2$ 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$_L$S$_{L*}$. (i.e., add S$_{L*}$ $\rightarrow$ $\varepsilon$ $\mid$ S$_L$S$_{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$^i$b$^j$c$^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 {a$^n$b$^n$c$^n$ | n $\geq$ 0}, that is ¬ (i $\neq$ j $\lor$ j $\neq$ k) ≡ (i = j $\land$ j = k) which is not a CFL because there is no CFG that can generate ${\bar {L}}$. We don't prove this formally, but intuitively a memory of n would have to exist across two boundaries, both between 'a's and 'b's, as well as 'b's and 'c's, which cannot be done simultaneously with a CFG (or a PDA).

### Decision Properties of CFLs

The context free languages are decidable on questions of membership of a string in the language, on whether the language is empty or not, but NOT on the equivalence of a CFL to Σ*, and on the equivalence, or not, of two CFLs.

#### Test of whether a CFL is empty is decidable

Theorem: If L is a CFL then there is an algorithm that determines whether L is the empty language ({ } or $\phi$).
If L is a CFL, then there is a CFG that generates L. In fact, it can be shown that there is a CFG generating L that has no unreachable symbols (i.e., all variables and terminals can be generated as part of sentential forms from the start symbol of the CFG), and there are no useless symbols (i.e., substrings of terminals can be generated by all variables). Do a breadth-first enumeration of sentential forms from such a grammar, and if after an "adequate" number of generations a string is not found, then L is empty, else its not empty. If a variable is repeated along a path along a sentential form, E, with the first instance of the variable, to a sentential form, F, with the second instance of the same variable, then the path can be pruned at E, because there are other paths that include E but without the repeated variable in a later sentential form. If no paths exist without repeated variables, then the language is empty.

## Properties of Context Sensitive Languages
### Closure Properties of CSLs

The CSLs are closed under
* Complement
* Union
* Intersection
* Concatenation
* Kleene Closure
* 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$_1$ and L$_2$ are CSLs then L$_1$ $\cup$ L$_2$ is a CSL. If L1 and L2 are CSLs then there are CSGs, G$_{L1}$ and G$_{L2}$, that generate L$_1$ and L$_2$ respectively. To construct a CSG to generate L$_1$ $\cup$ L$_2$ 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∪{\displaystyle\cup}L2}$ for the new grammar, G$_{L1∪{\displaystyle\cup}L2}$, with two productions S$_{L1∪{\displaystyle\cup}L2}$ $\rightarrow$ S$_{L1}$ and S$_{L1∪{\displaystyle\cup}L2}$ $\rightarrow$ S$_{L2}$. This new grammar is a CSG since the new productions are all noncontracting, and it generates L$_1$ $\cup$ L$_2$.

#### The CSLs are closed under Intersection

If L$_1$ and L$_2$ are CSLs then L$_1$ $\cap$ L$_2$ is a CSL.

#### The CSLs are closed under Concatenation

If L$_1$ and L$_2$ are CSLs then L$_1$L$_2$ 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 closed under Substitution

The CSLs are closed under substitution. The proof sketch is much like the argument for CFLs. The closure under substitution, however, depends on the fact that a CSL, strictly speaking, does not include the empty string, $\varepsilon$. We will elaborate on the significance of this when discussing substitution for recursive languages.

### Decision Properties of CSLs
## 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$_1$ is a recursive language and L$_2$ is a recursive language, then L$_1$ $\cup$ L$_2$ is recursive. Let M$_{L1}$ and M$_{L2}$ be the TMs recognizing L$_1$ and L$_2$ respectively and each is gauranteed to halt. From M$_{L1}$ and M$_{L2}$ we construct an always halting TM, M$_{L1∪{\displaystyle\cup}L2}$ , for L$_1$ $\cup$ L$_2$. Since TMs and computers are equivalent in terms of what can be computed, we represent M$_{L1∪{\displaystyle\cup}L2}$ in programming language pseudocode with the understanding that this can be translated to a TM.
<M$_{L1∪{\displaystyle\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$_1$ and L$_2$ are being used as subroutines. The construction for M$_{L1∪{\displaystyle\cup}L2}$'s behavior covers all conditions and is gauranteed to halt.

#### The Recursive languages are closed under Intersection

If L$_1$ is a recursive language and L$_2$ is a recursive language, then L$_1$ $\cap$ L$_2$ is recursive. Let M$_{L1}$ and M$_{L2}$ be the TMs recognizing L$_1$ and L$_2$ respectively and each is gauranteed to halt.
<M$_{L1∩{\displaystyle\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$_1$ is a recursive language and L$_2$ is a recursive language, then L$_1$L$_2$ is recursive. Let M$_{L1}$ and M$_{L2}$ be the TMs recognizing L$_1$ and L$_2$ 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$_1$(x) == accept and M$_2$(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$_1$x$_2$…x$_k$,
IF M$_L$(x$_i$) == accept for all x$_i$ in x$_1$x$_2$…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. Why should the recursive languages be different from the other language classes that are subsets of the recursive languages -- CSLs, CFLs, regular languages? Whereas these distinguished subsets cannot include $\varepsilon$ (i.e., their grammars cannot include productions of the form $\alpha \rightarrow \varepsilon$), a arbitrary recursive language can include $\varepsilon$, and the possibility of 'erasing' symbols from strings are what introduces the possibility of a substitution yielding a language that is outside the recursive class.
Consider a proof sketch that the recursive languages are not closed under substitution from Ullman. That is, if L ⊆ Σ* is a recursive language, and for each symbol a ∈Σ, subst(a) = L$_a$ is a recursive language, then subst(L) is not necessarily a recursive language.
   “To see why, consider the particular language L consisting of strings of the form (M,w,c$^i$), where M is a coded Turing machine with binary input alphabet, w is a binary string, and c is a symbol not appearing elsewhere. The string is in L if and only if M accepts w after making at most i moves. Clearly L is recursive; we may simulate M on w for i moves and then decide whether or not to accept. However, if we apply to L the homomorphism" (i.e., a restricted type of substitution), "that maps the symbols other than c to themselves, and maps c to ε, we find that h(L)" (i.e., subst(L)), "is the universal language, which we called L$_u$. We know that L$_u$ is not recursive. “ Ullman (http://infolab.stanford.edu/~ullman/ialcsols/sol9.html, Exercise 9.2.6(e))
Homomorphism, a special case of substitution, is when each L$_a$, for 'a' in Σ, is a singleton set – that is, each L$_a$ contains a single string, including possibly the empty string. So, for example if L is defined over Σ = {c, d, e}, and subst(c) = {01}, subst(d) = {rq23t}, and subst(e) = {𝜀}, then if w = ‘ceed’ then subst(w) = {01rq23t}.
Ullman's construction illustrates a very general way of dealing with languages/problems that are not recursive and therefore may not halt without an additional constraint. To make a recursive language from the original -- that is, to guarantee halting -- put a definite upper-bound on the number of steps that the procedure can run, and if one hits that upper-bound before a string is accepted by the procedure, M, then halt (and say 'no', or perhaps 'do not know'). That is, suppose that M is a procedure, which is equivalent to a Turing machine, and we can execute M one step at a time by appropriately instrumenting M. Then a procedure, M' , can be expressed this way:
<M', wc$^n$> = BOOLEAN FUNCTION Bounded-M (M, w, n) {
i = n
DO {
* Execute next step of M
* Decrement i by 1
} UNTIL (i = 0 OR M halts)
IF M accepted THEN RETURN(yes) ELSE RETURN(no)
In Ullman's contradicting case of closure under substitution -- (M,w,c$^n$) or (M,wc$^n$) -- where 'n' now is the upperbound (because we are using 'i' as the counter) -- subst((M,wc$^n$)) = (M,w), which as Ullman notes is the universal language, and which is known to be undecidable, that is, not recursive.
This may seem a bit mind-bending, and it does leave some of us with hesitation, as expressed by some users on reddit who wanted, to their credit, a deeper understanding. Shouldn't the result of the substitution above be interpreted as "The string is in L if and only if M accepts w after making at most ZERO moves", since all the 'c' characters have all been erased?
To better understand the solution, its easier to use the pseudo-code formulation above, which I've carefully constructed, where "no 'c' characters" corresponds to the case where n=0 in the pseudocode. In that case entering the DO loop for the first time will cause i to be decremented to -1 and the DO loop can never, thereafter, be exited because of the 'i=0' case; the only way to exit the loop is if M accepts, and if M never accepts then M' doesn't halt. M' can take any M and w as arguments -- M' is equivalent to a bounded universal TM, but in the case where n is initially 0, it is equivalent the universal TM.
Again, the recursive languages are not closed under general substitution because of the possibility of erasure caused by the substitution with the possibility of 𝜀. However, the recursive languages are closed under 𝜀-free substitutions, where 𝜀 in a substituting language is disallowed. In some sources you may see that the CSLs are closed under 𝜀-free substitutions as well, because of the possibility of 𝜀 in a CSL, or not, is left as a technicality that is glossed over; strictly speaking, however, 𝜀, cannot be in a CSL, because a CSG is is a normal form of a non-contracting grammar, so by the strict assumptions that L is a CSL, there can be no production to 𝜀 and therefore the 𝜀-free qualifier is not needed. A demonstration that the recursive languages are closed under 𝜀-free substitutions can include the same kind of argument for testing different segmentations of strings that we made for closure under concatenation and Kleene closure.

### 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$^0$ or 1 (constant), log n (logarithmic), n (linear), n log n, n$^2$ (quadratic), n$^3$, 2$^n$ (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$^2$ for sufficiently sized n, for example.
If I say that an algorithm runs in O(n$^3$) 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$^3$, for n ≥ t. Notice that if a algorithm is O(n), for example, then it is also O(n$^2$) and O(n$^3$) 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$^3$) when it is also O(n$^2$) is that the former is misleading because n$^3$ 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$_1$*f(n) ≥ g(n) ≥ c$_2$*f(n) for n ≥ t (t = max(t$_1$,t$_2$)).
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$^2$) 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$^n$) 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$^2$) $\subset$ O(n$^3$) $\subset$ O(2$^n$) $\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.
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$^n$) 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$_0$ ⋁ x$_1$ ⋁ x$_2$) $\bigwedge$ ( x$_0$ ⋁ ¬x$_1$ ⋁ x$_2$) $\bigwedge$ (¬x$_0$ ⋁ ¬x$_1$ ⋁ ¬x$_2$) $\bigwedge$ (¬x$_0$ ⋁ ¬x$_1$ ⋁ x$_3$).
Since there are 4 variables, x$_0$ through x$_3$, this is called a 4-SAT problem. There are 2$^4$ combinations of assignments to the four variables. An assignment that renders the entire expression true is x$_0$ = false, x$_1$ = true, x$_2$ = true, x$_3$ = 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.
Consider this 2-SAT problem: (¬x$_0$ ⋁ ¬x$_1$) $\bigwedge$ ( x$_0$ ⋁ ¬x$_1$) $\bigwedge$ (¬x$_0$ ⋁ x$_1$) $\bigwedge$ (x$_0$ ⋁ x$_1$). There are 2$^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).
SAT is NP because there are an exponential number of possible solutions, 2$^n$, 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$_0$ ⋁ x$_1$ ⋁ x$_2$) $\bigwedge$ ( x$_0$ ⋁ ¬x$_1$ ⋁ x$_2$) $\bigwedge$ (¬x$_0$ ⋁ ¬x$_1$ ⋁ ¬x$_2$) $\bigwedge$ (¬x$_0$ ⋁ ¬x$_1$ ⋁ x$_3$). 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$_0$) + t$_1$ + t$_2$ >= 1
t$_0$ + (1-t$_1$) + t$_2$ >= 1
(1-t$_0$) + (1-t$_1$) + (1-t$_2$) >= 1
(1-t$_0$) + (1-t$_1$) + t$_3$ >= 1
A solution to this ILP is
t$_0$ = 0
t$_1$ = 1
t$_2$ = 1
t$_3$ = 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.
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:
* Does the first row/ID of the matrix correspond to the initial ID, that is to NTM being in its start state, q$_0$, and NTM's read/write head being at the left end of the input w, followed by blanks?
* 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?
* 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.
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$_0$, 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$_0$.
* 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).
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).
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$_3$, a). For each possible outcome, say (q$_5$, b, R) for example, becomes a set of conjoined conditions, (cs$_{k+1}$= q$_5$ ∧ Loc$_{k+1}$ = j+1 ∧ Z$_{k+1,j}$ = b). This must be repeated for each possible outcome of (q$_3$, 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).
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.
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.

### Learnability Theory

Leslie Valiant, Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World, pp. 76-81

## 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$_1$ is a RE language and L$_2$ is a RE language, then L$_1$ $\cup$ L$_2$ 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$_1$ $\cup$ L$_2$ that the RE languages are closed under union.

#### The RE languages are closed under Intersection

If L$_1$ is a RE language and L$_2$ is a RE language, then L$_1$ $\cap$ L$_2$ 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$_1$ $\cap$ L$_2$ that the RE languages are closed under intersection.

#### The RE languages are closed under Concatenation

If L$_1$ is a RE language and L$_2$ is a RE language, then L$_1$L$_2$ 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$_1$L$_2$ 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 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);
•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.

## References

* ↑ Hopcroft, John E., Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company.
* ↑ Hopcroft, John E., Motwani, Rajeev, Ullman, Jeffrey D. (2007). Introduction to Automata Theory, Languages, and Computation 3rd Edition. Pearson Education, Inc/Addison-Wesley Publishing Company.