text:
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, 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 (L1 $$\in$$ CFLs ∧ L2 $$\in$$ CFLs) → R(L1, L2), where L1 and L2 are languages and R is a property, such as union: if L1 and L2 are CFLs then L1 $$\cup$$ L2 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 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 L1 and L2 are both regular languages, then L1$$\cup$$ L2 is a regular language.

Since L1 and L2 are each regular languages, there are DFAs M1 and M2, respectively, that recognize each. Construct an NFA with $$\varepsilon$$ transitions, M1$\cup$2, for L1 $$\cup$$ L2 as follows.

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

M1$\cup$2 is an NFA that recognizes L1 $$\cup$$ L2 and thus L1 $$\cup$$ L2 is a regular language.

Regular Languages are closed under Intersection
Theorem: If L1 and L2 are both regular languages, then L1 $$\cap$$ L2 is a regular language.

Suppose L1 and L2 are regular languages over alphabet Σ. Then L1 $$\cap$$ L2 is regular. This must be so since L1 $$\cap$$ L2 = ~(~L1 $$\cup$$ ~L2) and the regular languages are closed under complement and union. But we can also directly construct a DFA that accepts L1 $$\cap$$ L2 from the DFAs that must exist for L1 (M1 = (Q1, Σ, $$\delta$$1, q1, F1)) and L2 (M2 = (Q2, Σ , $$\delta$$2, q2, F2)), respectively. The following is adapted from (pp. 59-60, ; p. 137, ).

M1∩2 = (Q1×Q2, Σ, $$\delta$$, [q1, q2 ], F1×F2) that accepts L1 $$\cap$$ L2. For each pair of states from M1 and M2 respectively, define a state in M1∩2. For each of these pairs of states, on each symbol a in Σ, define a transition in M1∩2

$$\delta$$([q1i, q2k ], a) = [$$\delta$$1(q1i, a), $$\delta$$2(q2k, a)]

As an example, consider {0m | 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 L1 and L2 are both regular languages, then L1L2 is a regular language.

The concatenation of languages L1 and L2, written L1L2, is {w1w2 | w1j $$\in$$ L1 and w2k $$\in$$ L2}. That is, any word from L1 followed immediately by any word of L2, is a string in the language of the concatenation.

Since L1 and L2 are each regular languages, there are DFAs M1 and M2, respectively, that recognize each. Construct an NFA M12 with $$\varepsilon$$ transitions by

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

M12 is an NFA that recognizes L1L2 and thus L1L2 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 L1L2...Lm = {w1w2...wm | w1j $$\in$$ L1 and w2k $$\in$$ L2 and ... and wmi $$\in$$ Lm}.

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 {w1w2w3...wm | for all m $$\geq$$ 0 and each wk $$\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 Σ, xk, we associate a language Lxk. 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 xk is a symbol in Σ then Subst(xk) is the strings in Lxk, i.e., simply Lxk itself. If w = a1a2...am is a string in L, then Subst(w) = Subst(a1)Subst(a2)...Subst(am), 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 Lxk's don't have too be the same. The alphabet for the language Subst(L) is the union of the alphabets of all the Lxk 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 L0 = {w $$\mid$$ w matches ($$\S$$+$$\aleph$$)+} and L1 = {$$\varepsilon$$, a, ba} then Subst(0) = L0 = {w $$\mid$$ w matches ($$\S$$+$$\aleph$$)+} and Subst(1) = L1 = {$$\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 L1, i.e., {$$\varepsilon$$, a, ba}, followed by two draws from L0 = {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, xk in Σ, there is an associated regular language Lxk, then Subst(L) is a regular language.

If L and all Lxk's are regular languages then there are DFAs that recognize L and each of the Lxk's. Call these DFAs M (for L) and Mxk (for each Lxk). 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 qi to qj on input symbol xk, splice in the DFA for Lxk, by
 * make a copy of each Mxk, call it Mxk'
 * add an $$\varepsilon$$ transition from qi to the start state of Mxk'
 * add an $$\varepsilon$$ transition from each accepting state of Mxk' to qj.

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 L1 is a regular language and L2 is a regular language then there is an algorithm that determines whether L1 and L2 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.

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 L1 and L2 are both CFLs, then L1$$\cup$$ L2 is a CFL.

If L1 and L2 are CFLs then each has an associated CFG, GL1 and GL2, 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 L1$$\cup$$ L2, call it GL1$\cup$ L2, create a new start symbol, SL1$\cup$ L2, with two associated productions, one to the start symbol of GL1 and one to the start symbol of GL2 (i.e., add SL1$\cup$ L2 $$\rightarrow$$ SL1 $$\mid$$ SL2). GL1$\cup$ L2 is a CFG that generates L1$$\cup$$ L2, so L1$$\cup$$ L2 is a CFL.

CFLs are closed under Concatenation
Theorem: If L1 and L2 are both CFLs, then L1L2 is a CFL.

If L1 and L2 are CFLs then each has an associated CFG, GL1 and GL2, 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 GL1 is SL1 and that the name of the start symbol for GL2 is SL2. To create a CFG for L1L2, create a start symbol SL1L2 with a single production to SL1SL2 (i.e., add SL1L2 $$\rightarrow$$ SL1SL2). GL1L2 is a CFG that generates L1L2, so L1L2 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, wi, where each wi is a string in L.

If L is a CFL then there is a CFG, GL, that generates L, with a start symbol that we'll call SL. To create a CFG for L*, create a new start symbol, call it SL*, with two productions, one to $$\varepsilon$$ and one to SLSL*. (i.e., add SL* $$\rightarrow$$ $$\varepsilon$$ $$\mid$$ SLSL*). GL* 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, xk in Σ, there is an associated CFL Lxk, then Subst(L) is a CFL.

If L is a CFL then there is a CFG that generates L, call it GL. If all Lxk's are CFLs then there are CFGs that generate each, call them GLxk respectively. To create a CFG that generates Subst(L), GS(L), replace every instance of an alphabet/terminal symbol in the productions of GL with the start symbol for the grammar of the language corresponding to that symbol, and make the productions of GS(L) be the union of all the revised productions of GL and all the productions of all the GLxk's. GS(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 = {aibjck | 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 {anbncn | n $$\geq$$ 0}, which is not a CFL because ...

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, Lc, is a CSL. If L is. a CSL then there is a linear bounded TM, ML, that recognizes L, and that halts on all inputs. A linear bounded TM for Lc can be created that calls ML as a subroutine and that accepts if ML rejects, and that rejects if ML accepts.

The CSLs are closed under Union
If L1 and L2 are CSLs then L1 $$\cup$$ L2 is a CSL. If L1 and L2 are CSLs then there are CSGs, GL1 and GL2, that generate L1 and L2 respectively. To construct a CSG to generate L1 $$\cup$$ L2 copy all the productions GL1 and GL2 with variables renamed as necessary so as to not confuse variables from different grammars, and create a start symbol SL1 $\cup$ L2 for the new grammar, GL1 $\cup$ L2, with two productions SL1 $\cup$ L2 $$\rightarrow$$ SL1 and SL1 $\cup$ L2 $$\rightarrow$$ SL2. This new grammar is a CSG since the new productions are all noncontracting, and it generates L1 $$\cup$$ L2.

The CSLs are closed under Intersection
If L1 and L2 are CSLs then L1 $$\cap$$ L2 is a CSL.

The CSLs are closed under Concatenation
If L1 and L2 are CSLs then L1L2 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 ML, that recognizes L and that is guaranteed to halt for all accept cases and in all reject cases. Create a new TM, ML', that calls ML as a subroutine. If ML returns accept for a input string, then ML' returns reject. If ML returns reject for a input string, then ML' returns accept. ML' accepts the complement of L, and always halts, so the complement of L is recursive.

The Recursive languages are closed under Union
If L1 is a recursive language and L2 is a recursive language, then L1 $$\cup$$ L2 is recursive. Let ML1 and ML2 be the TMs recognizing L1 and L2 respectively and each is gauranteed to halt. From ML1 and ML2 we construct an always halting TM, ML1$\cup$L2, for L1 $$\cup$$ L2. Since TMs and computers are equivalent in terms of what can be computed, we represent ML1$\cup$L2 in programming language pseudocode with the understanding that this can be translated to a TM.

 = BOOLEAN FUNCTION Union (ML1, ML2, w) { IF ML1(w) == accept OR ML2(w) == accept THEN RETURN accept ELSE RETURN reject}

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

The Recursive languages are closed under Intersection
If L1 is a recursive language and L2 is a recursive language, then L1 $$\cap$$ L2 is recursive. Let ML1 and ML2 be the TMs recognizing L1 and L2 respectively and each is gauranteed to halt.

 = BOOLEAN FUNCTION Intersection (ML1, ML2, w) { IF ML1(w) == accept AND ML2(w) == accept THEN RETURN accept ELSE RETURN reject}

The Recursive languages are closed under Concatenation
If L1 is a recursive language and L2 is a recursive language, then L1L2 is recursive. Let ML1 and ML2 be the TMs recognizing L1 and L2 respectively and each is gauranteed to halt. At a high level,

 = BOOLEAN FUNCTION Concatenation (ML1, ML2, w) {

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

IF M1(x) == accept and M2(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 ML be the TM recognizing L and that is gauranteed to halt.

 = BOOLEAN FUNCTION Repetition (ML, w) {

FOR each of the 2undefined ways to partition w into x1x2…xk,

IF ML(xi) == accept for all xi in x1x2…xk 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 n0 or 1 (constant), log n (logarithmic), n (linear), n log n, n2 (quadratic), n3, 2n (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 n2 for sufficiently sized n, for example.

If I say that an algorithm runs in O(n3) time, then that means the actual run time, g(n), of the procedure will be bounded above for big enough n: g(n) ≤ c*n3, for n ≥ t. Notice that if a algorithm is O(n), for example, then it is also O(n2) and O(n3) 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(n3) when it is also O(n2) is that the former is misleading because n3 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 c1*f(n) ≥ g(n) ≥ c2*f(n) for n ≥ t (t = max(t1,t2)).

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(n2) 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 np for any positive value of p), notably O(2n) 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(n2) $$\subset$$ O(n3) $$\subset$$ O(2n) $$\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(np) time, where p is any real number constant, belongs to class P(olynomial). Remember that O(np) 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(2n) 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 (¬x0 ⋁ x1 ⋁ x2) $$\bigwedge$$ ( x0 ⋁ ¬x1 ⋁ x2) $$\bigwedge$$ (¬x0 ⋁ ¬x1 ⋁ ¬x2) $$\bigwedge$$ (¬x0 ⋁ ¬x1 ⋁ x3).

Since there are 4 variables, x0 through x3, this is called a 4-SAT problem. There are 24 combinations of assignments to the four variables. An assignment that renders the entire expression true is x0 = false, x1 = true, x2 = true, x3 = 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: (¬x0 ⋁ ¬x1) $$\bigwedge$$ ( x0 ⋁ ¬x1) $$\bigwedge$$ (¬x0 ⋁ x1) $$\bigwedge$$ (x0 ⋁ x1). There are 22 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, 2n, 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: (¬x0 ⋁ x1 ⋁ x2) $$\bigwedge$$ ( x0 ⋁ ¬x1 ⋁ x2) $$\bigwedge$$ (¬x0 ⋁ ¬x1 ⋁ ¬x2) $$\bigwedge$$ (¬x0 ⋁ ¬x1 ⋁ x3). This is easily translated to an integer linear program (ILP) by replacing each Boolean variable xk with an integer variable tk, and replacing each negated variable ¬xk with (1 - tk). That's the reduction! So, the example SAT problem becomes the ILP:

(1-t0) + t1 + t2 >= 1

t0 + (1-t1) + t2 >= 1

(1-t0) + (1-t1) + (1-t2) >= 1

(1-t0) + (1-t1) + t3 >= 1

A solution to this ILP is

t0 = 0

t1 = 1

t2 = 1

t3 = 0

which can be mapped to a solution to the SAT problem, again through an easy substitution: xk = false iff tk = 0, and xk = true iff tk = 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 tk, and also number of target variables xk. So, if we should ever find an efficient, deterministic polynomial time algorithm, O(np), for solving ILPs, we will have a polyomial time algorithm for solving SAT, since O(np) + O(n) = O(np)!

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(np) 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  to a Boolean expression, ENTM,w, where ENTM,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(np) 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(np) since there is a maximum of O(np) moves along any path of IDs by NTM. Cook therefore posited a matrix of O(np) rows, each an ID, and O(np) 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(np) $$\times$$ O(np) = O(n2p) 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 ENTM,w will imply the set of of possible n-tuple truth value assignments to the n variables of the ENTM,w. Also, recognize that the O(np) $$\times$$ O(np) matrix is an upperbound on the dimensions of a possible path followed by NTM. Some problems will require fewer rows/IDs than O(np) and/or fewer tape cells in an ID than O(np). 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(np) limit on columns, and we assume that the row/ID corresponding to entering an accepting state is duplicated up to the O(np) 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, q0, 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, ENTM,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, q0, 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, q0.
 * 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(np)) create a Boolean condition that the value of the cell location is the blank.

Conjoin these Boolean variables into one Boolean subexpression. Call it ENTM,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(n2p) is that accepting state.

Disjoin these Boolean variables into one Boolean subexpression. Call it ENTM,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 (q3, a). For each possible outcome, say (q5, b, R) for example, becomes a set of conjoined conditions,  (csk+1= q5 ∧ Lock+1 = j+1 ∧ Zk+1,j = b). This must be repeated for each possible outcome of (q3, 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 ENTM, depends on the size of w, i.e., the size of the matrix, O(n2p).

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

 * ENTM,w = ENTM,w,initial $$\bigwedge$$ ENTM,accepting $$\bigwedge$$ ENTM,

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(np) 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 Lk in row (1) column (a), and the two-way arrow indicates that SAT polynomial reduces to Lk, and vice versa. Since Lk has now been shown to be NP complete, all NP problems reduce to Lk as well, as shown in row (1) column (b). One important point to emphasize is that the other problem, Lk, 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 Lk 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 L1 is a RE language and L2 is a RE language, then L1 $$\cup$$ L2 is RE. It is left as an exercise to show by construction of an unrestricted grammar or a TM for the language represented by L1 $$\cup$$ L2 that the RE languages are closed under union.

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

The RE languages are closed under Concatenation
If L1 is a RE language and L2 is a RE language, then L1L2 is RE. It is left as an exercise to show by construction of an unrestricted grammar or a TM for the language represented by L1L2 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, xi, 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 MU may not halt when its argument TM does not accept its input).

In general, undecidability can signify one of two conditions. Membership in Lu, for example, is undecidable in one sense, which is failure to say no and halt if a string is not in Lu. 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 LQ is the set of RE languages for which Q=yes. Continuing our earlier example, if Q is "Is this language a regular language?" then LQ is the set of regular languages. In fact, LQ can be viewed as a language of languages, where you'll recall that each language in LQ 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 LQ 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 LQ as a property -- e.g., every member of LQ has the property of being a regular language.

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

 * is one for which { } $$\subset$$ LQ $$\subset$$ LRE, where LRE is the language of binary encodings for all TMs (i.e., the RE languages);
 * LQ $$\cap$$ LR = { }, where LR 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 LP is the set of languages with non-trivial property P.

•

•Is the question of a language L’s membership in the LP 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 LP languages decidable or undecidable?

•

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

•Assume that membership in LP is decidable. Then there is an algorithm, TMP, that recognizes LP.

•

•Regardless of non-trivial P, reduce LU (the Universal Language aka the Halting Problem, known undecidable) to LP, thus showing a contradiction with assumption that LP 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 LR 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.


text:
Theory of Formal Languages, Automata, and Computation/Applications of Language Classes

Recursive Descent Parsing and Translation
CFGs have been used for some time in defining the syntax of programming languages, starting with Algol. Ideally, we can directly translate a grammar into mutually recursive procedures for parsing a computer program, and ultimately for compiling it. Consider the grammars of Figure ExpressionGrammars. The first of these grammars for arithmetic expressions is simple, yet ambiguous, since id + id * id (and other strings) can be generated by two (or more) distinct leftmost derivations or distinct parse trees. So, that is unsuitable as the basis foor automated parsing. The second grammar is not ambiguous, having enforced operator precedence rules to ensure desirable, single parse trees for every string. This is as far as we got when introducing this CFL of arithmentic expressions. As it turns out, grammar (b) presents another prooblem for the recursive procedures we have in mind. This grammar is a left recursive. When this grammar is translated into mutually recursive procedures, we have a function such as Expression (i.e., E) potentially calling itself, as indicated in E $$\rightarrow$$ E + T, with no change in the argument that is passed. This can lead to infinite recursion. Figure AlgolGrammar shows a simplified CFG for the Algol-60 programming language. Algol-60, as in the year 1960, was the first programming language with syntax defined by a context free grammar. The variables in the grammar translate rather directly into mutually recursive functions in a recursive descent parser. Figure AlgolTranslator shows the parsing routines corresponding to the grammar variables of expression, term, and factor. From parse_expression, a term is what is first expected, and so parse_term is called to identify a portion of code that was generated by the term part of the grammar. Parse_term then calls parse-factor to identify the Algol code that was derived from the factor variable of the grammar.

In parse_factor actual symbols in the program are scanned by the part of the parser called the lexical analyzer, which is concerned with identifying basic tokens, such as constants, variables, operators, and punctuation in the Algol code. In the sample translator code, the match function is highlighted in bold blue, and this function contains a call to the next_token function, which is essentially the lexical analyzer and performs the recognition procedures associated with the parts of the grammar in Figure AlgolGrammar that are highlighted in bold blue. Those productions, in bold blue, correspond to a regular grammar (almost), and you should confirm that productions not conforming exactly to the regular grammar constraints of A $$\rightarrow$$ aB or A $$\rightarrow$$ a can be easily translated to productions that do adhere to the constraints (though its a bit unwieldy to do so because of the space it would require). Though the next_token code is not shown in this illustration, it is an important part of a parser implementation since the lexical analyzer is what actually scans the input string/program.

In Figure AlgolTranslator, the generation of machine code is shown on bold purple. The machine code language assumes that arguments are pushed (loaded) onto a stack, and binary operations such as addition and multiply pop the top two items on the stack, apply the operation, and push the result back on the stack. So in the illustration of Figure AlgolTranslator the machine code translation of the Algol expression '1.2 + Var21 * 3' reads as follows and would execute as indicated in comments when it was run.

 * 1) LOAD_CONST 1.2
 * 2) LOAD_VAR Var21    // (i.e., push the value of Var21)
 * 3) LOAD_CONST 3
 * 4) MULTIPLY               // pop 3 and pop value of Var21, compute 3 * value of Var21, and push the result, P, onto the runtime stack
 * 5) ADD                        // pop P and pop 1.2, compute P + 1.2, and push the result, R, onto the runtime stack

If I had asked chatGPT to show more code for the parser, then it would include parser code for other grammar variables such as 'assignment statement' and included additional code generation commands such as STORE_VAR for storing the top of the runtime stack in a relative memory address associated with an Algol program variable name. There are other important parts of a translator, such as the symbol table for associating Algol program identifiers with computer memory (relative) addresses, that are not tied to any underlying grammar.

In sum, a recursive descent parser and translator follows elegantly from the specification of a programming language grammar. The recursive routines, as with any function calls, will push records onto the parser's runtime stack (not to be confused with the runtime stack that is assumed by the assembly code above), and this reliance on a stack by the parser makes it comprable to a PDA.

Relationships to Artificial Intelligence
There are many informal and formal connections between AI and formal languages, automata, and computation. This chapter delves into these connections, as well as the requisite and optional AI material. Notes embedded in the main text indicate how I often present the material over a semester. While this material is at the end of the textbook, it is typically scattered in my lectures throughout the semester.

Probabilistic Grammars and Automata
In AI, non-determinism is prevalent, but cannot always be removed entirely while guaranteeing the same results because (a) operations/productions/transitions are uncertain, and (b) because the world/IDs are not typically complete or correct (i.e., the AI doesn’t know some things or it is wrong).

Measures of uncertainty are used in AI, most notably probabilities or fuzzy membership.

Probabilistic grammars are a type of formal grammar where each production rule has a probability associated with it.

These probabilities represent the likelihood that a particular rule will be used to generate a string.

Natural Language Processing: Probabilistic grammars can be used to model the probability distribution of sentences in a natural language, making it useful for tasks such as speech recognition and machine translation.

Information Retrieval: Probabilistic grammars can be used to generate queries that match documents in a database, allowing for more accurate search results.

DNA Sequencing: Probabilistic grammars can be used to model the probability distribution of DNA sequences, making it useful for tasks such as genome assembly and alignment.

NFA-to-DFA translation and speedup learning
The first point of inspiration is in the elimination of nondeterminism when translating an NFA to a DFA (or a nondeterministic PDA to a deterministic PDA, if the latter exists). I’ve said that NFAs and nondeterminism generally can lead to simpler and more elegant solutions, and be much easier to specify by a human, but these automata will require enumeration (depth first or breadth first or some heuristic approach) when they are actually used (to see whether a string reaches an accepting configuration along at least one path of the machine), and that is computational costly. So ideally, we can imagine that in the case of a complex problem, someone can specify an NFA solution, but then use automated translation to acquire a more efficient-to-execute deterministic recognizer. The same can be said about AI and machine learning generally. I regard it as definitional of AI that an AI system explore alternatives, requiring enumeration or search – that is nondeterminism. Machine learning can then be used to eliminate nondeterminism, and thus “speedup” problem solving, planning, and other processes by the AI.

Its rarely, if ever, the case that all sources of nondeterminism can be eliminated in an AI program, however. The reasons are several. One, operators or “transitions” in AI often do not have perfectly predictable outcomes. A robot may try to pick up a cup, for example, and the cup slips from the robot’s grasp – there may always be at least two outcomes, I’ve got the cup or I don’t, and probably more outcomes if there can be liquid in the cup or not, hot versus cold liquid, etc. While some outcomes may be rare, we still want the robot to be able to respond to them – this possibility of multiple outcomes is the clear manifestation of nondeterminism. Another source of nondeterminism that is related to the first is that the AI may not know with certainty about all relevant aspects of the environment. For example, an intelligent vehicle may not know that a pedestrian is skateboarding behind a building but is about to abruptly enter traffic, and the AI had better anticipate that possibility, as well as mundane circumstances. Nondeterminism again.

Even though its unlikely that machine learning can get rid of all nondeterminism, it can “reduce” the nondeterminism. In a real AI application we might measure the extent that the nondeterminism is reduced by the expected number of states that an AI system has to enumerate, both before learning and after learning, and while learning. The expected number of states generated during an enumeration or search is the sum of the states generated across all possible problems, weighted by the probability of each problem. So an expected number is a weighted average.

DFA-to-RE Translation and Macro Learning
The second learning task that I want to relate is called macro learning, which is used in AI learning to solve problems more effectively. In particular, if an AI observes that transitions are repeatedly sequenced together, or it discovers that certain transitions that are sequenced together lead to solutions, then the AI might form a macro operator (or macro transition) that concatenates the transitions together so that they can be applied as a single packet, or macro. This process of macro formation will both reduce the nondeterminism found in enumeration by taking large steps in individual paths or derivations, but it also adds to nondeterminism by creating additional choice points in an enumeration or search for a string’s derivation, since the macro is added to, rather than replacing, the operators (or transitions) that are used in its composition. The management of the tradeoffs in macro learning led to a good deal of research on learning choice preferences or biases as well that involved probabilities that are placed on choices. I don’t get into probabilities here, but the slides do touch on their use in probabilistic grammars which are related to AI approaches to solving problems or analogously in deriving strings.

AI Planning
While the implication operator in logic theorem proving looks the same as the production symbol, $$\rightarrow$$, theorem proving is additive. When making an inference, nothing in the current world model is overwritten.

In contrast, in AI planning a “mental” model of the current world state is maintained and changed through the application of operators (or productions). A common representation of operators show PREconditions, which have to be true before the operator can be applied, and EFFects, which are the conditions that are true after the operator is applied. For our purposes we can think of an operator as a production, as in a grammar, PRE $$\rightarrow$$ EFF, where effects rewrite preconditions. There is more nuance to it than that, but the details are left to an AI course.

The slides show two examples of the derivations of single plans, analogous to a single derivation of a string, but as with languages, there is a search for the derivation (plan), which requires an enumeration of many paths, most of which are unsuccessful derivations (and that’s ok – we are looking for just one plan/derivation).

Generating a plan can be modeled as generating a string with a grammar. The operators can be regarded as skeletal productions, that is productions with variables, as illustrated in the blocks-world operators of the slides – Pickup(?X), Putdown(?X), Unstack(?X, ?Y), Stack (?X, ?Y). The last slides of Friday’s lecture give a brief glimpse at this equivalence, though AI planning will generally operate with additional pattern matching capabilities than we have seen with respect to strings. The equivalence also makes reference to ridiculous computational (storage and runtime) requirements in the case where we are interpreting AI states as strings and AI operators as productions, but computational cost is not an issue we are concerned with at this point, and similar equivalence arguments that are not concerned with costs are made by Hopcroft, Motwani, and Ullman 3rd Edition (2007) when comparing Turing Machines and computers (e.g., breakout boxes on pp., 322, 346, 364).

The grammars that are equivalent to AI planning problems would typically be context sensitive, but a general or universal AI planning system is unrestricted. I don’t show this, but have a chat with chatGPT to learn more. Here are some handy references too, not just to AI planning but to other material at the intersection of CS 3252 and AI, notably forms of machine learning that have fallen out of favor, but still very interesting – these references are optional material.

Solomonoff, R. J. (1964). “A Formal Theory of Inductive Inference, Part 1”, Information and Control, Vol. 7.

Biermann, A.W. (1972). “On the Inference of Turing machines from sample computations”, Artificial Intelligence, Vol 3.

Angluin, D. (1980). “Inductive Inference of Formal Languages from Positive Data”, Information and Control, Vol. 45.

Moore, R.C. (1984). “A Formal Theory of Knowledge and Action” Technical Report 320, SRI.

Tate, Alan AI Planning MOOC.

Also, plenty of other references online (search for ‘AI Planning’) or take the AI course.

Exercises, Projects, and Discussions
Project 1: Build a compiler for a non-trivial subset of a programming language of choice.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Kitchen Remodel/Appliance and sink installation

Appliance and sink installation must strictly follow the manufacturer's instructions. In this chapter, I will just add a few remarks, in piecemeal fashion, that may be helpful in some cases.

General
The probably best advice that I can give for appliance installation is to think ahead while you do it: is there a chance that you will move the appliance out of its position, like for a check or a repair or simply because you still need to install floor tiles under it? Make sure the electrical and water connections are long enough to pull it out of its recess and even further (you may want to be able to crawl behind it).

We almost overlooked that necessity when we installed our refrigerator, because it doesn't stand against a wall, but we could conveniently access it from behind (see image), for most of the time during our kitchen installation. After the installation of the back row of cabinets, we would have lost that access and run into severe doo doo.

Microwave oven
The installation of a microwave oven into a Sektion cabinet frame requires a trim kit which needs to be purchased in addition to the appliance. That those are two separate products, was the case at least in 2022, when I ordered my kitchen. Due to its weight, a microwave oven must not sit on a regular shelf, but on a "reinforced ventilated shelf". Both this shelf and the set of black Nyttig support brackets which are needed for the attachment of the cover frame are separate products which need to be ordered in addition to the cabinet frame and to the trim kit.

Although we are very happy with that appliance now, initially I would have preferred not to purchase the Ikea products, namely their rather pricey trim kit. But I didn't dare to because I didn't know at that time if a product of another manufacturer would fit into my cabinet configuration.

If you have a similar conflict, maybe the following images can help you a little to decide what you are going to do: Notice that it will be necessary to cut some openings into the cabinet's back panel for the electrical connections (see first image). Ikea give detailed instructions. But if your cabinet configuration deviates from what they suggest or if you disagree with their recommendation, you may also use common sense and only cut what you think is necessary under your special circumstances. However, since those cut-outs won't be visible anyway, there isn't too much to worry to begin with.

Oven
The most important thing to consider when installing an oven is that, depending on where you live and on the product, it may require a special electrical connection with higher voltage. In the U. S., that means, too, that you may have to deal with a supply cable that is thicker and stiffer than for most other appliances and therefore will need more place.

If you have a built-in oven, the second most important thing is that it will probably be the heaviest appliance which you don't only need to move around in your space, but also to lift into a relatively high position. Our own oven weighs 260 lbs (118 kg). We found it extremely helpful that we, at that point of time, had a team of contractors in our home anyway, who were friendly enough to contribute elbow grease. Like a microwave oven, a oven must be installed on a "reinforced ventilated shelf".

If you have an Ikea kitchen designer helping you with your order list, they will add everything you need for your oven installation. This includes elements which will reinforce the shelf on which the oven will sit. They will also give you two Nyttig filler pieces which will cover the two gaps above and below the oven (first image).

By the way: On their web site, Ikea give the impression that there are only two possible heights on which a built-in oven can be installed. Don't get mislead: as long as you have a plan what to do with the rest of that cabinet frame (including drawer fronts or doors that fit into you design), you can actually place an oven and/or a microwave oven at any height that works best for you. The installation of an oven and a microwave uses up 50" of height. So in our 80" high cabinet, we still had 30" of height left, which we decided to use for two 15" high front elements. It could also have been done differently; but considering our body heights, this layout is what worked best for us.

Cooktop
Depending on where you live and on the chosen appliance, an induction or electric cooktop may require a special electrical connection with higher voltage.

Otherwise, the installation of a cooktop is pretty straightforward. The product's instructions include information about the dimensions and exact position of the rectangular pit that needs to be cut into the plywood countertop base (if such a base is required) and that will contain the appliance. In our case, this very information was somewhat ambiguous, so we decided to use common sense and that the cut-out needs to be just large enough to fit the lower part of the cooktop, while the edge of the glass ceramic part will lie on top of the countertop. The overlap between the wide top part of the cooktop and the countertop should be as large as possible (or to put it the other way around: the cut-out should be as small as possible), because that countertop will bear the load of the appliance.

I would not want to attempt to sink the cooktop deeper in and to make it flush with the countertop, because this will make the installation more difficult and more fault-prone, and it will also create a groove around the cooktop which will be hard to keep clean. I don't know about you, but in my kitchen there is no other place where so often an inadvertent spill occurs as on my cooktop.

Sink
Our kitchen sink is not an Ikea product, but a Kräus. As I mentioned in a earlier chapter, we had planned on an undermount, with the sink's top side partially being covered by countertop.

Although Ikea don't give instructions on how to install a sink of a different manufacturer, the installation was not too difficult. The overall width of our sink matches exactly that of its 30" base cabinet. So in order to install it, we had to cut the cabinet's side panels and the back panel to size. This required very careful measuring and calculating, since the upper edge of the sink had to sit exactly at the right height: aligned with the top side of the plywood that would cover all our base cabinets as a foundation for the future countertop.

One of the best advices that I can give for kitchen sink installation is to be really meticulous when you decide about the exact positions of your faucet and and of your soap dispensers. An ill-placed faucet may have a control lever that cannot be properly operated because it hits a windowsill or some other obstacle. An ill-placed soap dispenser may be of limited use if its spout doesn't reach the sink's basin; a soap dispenser should, as a general rule, be installed as close to the sink as possible.


text:
User:SangLayman5

Hello! I am Jim. I smile that I could unify to the entire globe. I live in Switzerland, in the NA region. I dream to see the various countries, to look for familiarized with fascinating people.

title: User:SangLayman5


text:
Planet Earth/Introduction

Every moment of your life will be from the perspective of a single planet—Planet Earth. You were born here and you will die here. This textbook is a guide to your home, to your place in the universe. By taking this course, you will learn about your home planet: how it works and how we know it works this way. This course is a user's manual for planet Earth, with direct recommendations for future generations, such as yourself, to maintain its health and natural wonders. As an astute student, you will be introduced to the theoretical principles of science and of how to defend yourself from the spread of ignorance. You will learn about Earth’s dimensions and motions, as well as how to navigate its surface. You will learn how energy originates from the closest star (the Sun), its Moon, and other sources of energy in the Earth’s active core, as well as how this energy can be used and stored. You will learn basic scientific principles of matter, the makeup of substances that form the field of chemistry. You will examine the planet’s atmosphere, the air that you are breathing as you read this, and how that air is slowly changing. You will explore the vast abundance of Earth’s water, covering the planet in enormous oceans, abundant lakes, and rivers, as well as frozen water locked within snow and ice. You will learn how to predict wind and storms and how climates shift. You will lead your own exploration of the solid interior of the Earth, the composition of mountains, rocks, and dirt. You will learn about life, the most unique feature of the planet. You will explore theories of how life arose and how it has evolved and changed over time, learning that you are of Earth and the story of your own origin on this planet. You will undertake an examination of the great biomes of jungles, forests, and deserts and the life that exists within them. You will survey the important field of biology as you learn about life and its interactions with the planet. In the end, you will come to face the ominous future of your own planet, of the changes that are now occurring. Your planet is not the same as that of your ancestors, nor of your grandparents, nor even of your parents at your age—Earth today is quickly being altered, and you will need to adapt to this change. This course will teach you how to prepare for this change and how to protect the planet from further alteration to the point that it becomes lifeless. This class will be challenging, but with enough dedication and commitment, you will succeed in learning the material cherish the knowledge presented in this class for the rest of your life.

title: Planet Earth/Introduction


text:
Planet Earth/About the Book

About this Textbook
This book was written with the support of a grant offered by Utah State University Libraries, Academic & Instructional Services, and the College of Science to support faculty and instructors at Utah State University Statewide Campuses to create Open Educational Resources to support their online courses in the United States of America. These grants are made to reduce barriers to student success as well as to encourage faculty and instructors to try new, high-quality, and lower-cost ways to deliver learning materials to students through open educational resources.

The majority of the first edition of the textbook was written between 2019 and 2020 with the intention that the textbook would be offered free of charge to all participants in GEO 1360 Planet Earth, an online course offered at Utah State University. This textbook is offered for any faculty, instructor, or teacher to adopt for their own courses they teach, and it is distributed under a Creative Commons License. If you notice any errors or mistakes, please contact the author.

About the Author
Benjamin J. Burger is a geologist who earned his masters of science degree in 1999 at Stony Brook University in New York and his Doctorate in 2009 at the University of Colorado in Boulder, and he spent five years working at the American Museum of Natural History in New York City. He has also worked as a professional geologist in the states of Utah, Colorado, and Wyoming. He joined the Utah State University faculty in 2011 and continues to teach and conduct research as an Associate Professor in the Department of Geoscience at the Uintah Basin – Vernal Campus of Utah State University located in northeastern corner of Utah. Many of his course lectures and educational content can be found on YouTube or on his website at www.benjamin-burger.org

Intended Audience
This textbook is written for an audience of introductory college students in a nonscience degree program. It is intended to provide a detailed comprehensive knowledge of Planet Earth, including basic aspects of physics, chemistry, geology, and biology. As a major scientific overview of the entirety of planet Earth, the intention is to only present key concepts that will enhance, enrich, and engage the readers interest in Earth sciences. It is intended to make any reader, such as yourself, at least a little more knowledgeable of the amazing place that we all live within.

Open Text and What That Means
All of the text and modules of the Planet Earth course are offered under a Creative Commons with Attributions license, which means that you are free to share and redistribute the material in any medium or format, and to adapt remix, transform, and build upon the material for any purpose, even commercially. Just be sure to attribute the text with the author's name and course name, and indicate where you found the information. The purpose of making this text free to disseminate is that it contains valuable information that you should feel free to share and discuss as widely as possible. Science adapts to new knowledge, and as such this text can be updated and modified as new discoveries are made. An open text also ensures that the knowledge remains affordable to the average student, such as yourself. Feel free to pass on the information that you learn in this course and you are free to make printed copies. The referenced text is available as a Wikibook on the Wikipedia website.

Digging Deeper
Hyperlinks will be referenced throughout the text to encourage further reading on any particular topic, most of these will point toward a Wikipedia article or an original scientific publication. These referenced resources will follow a similar style and format as seen on the popular Wikipedia website, where sources of specific information can be referenced and verified with a simple link. Every attempt was made to ensure the external links that you will find within the modules are verified in print and online sources, including peer-reviewed scientific papers, publications of scientific societies, government organizations, and mainstream news organizations. There is no guarantee these external links will remain available online or whether they will be archived for future electronic access. Furthermore, there is no guarantee that your university or college will have a subscription to the article to view online. However, most of these external references should be accessible to you if you wish to explore a topic more in-depth than provided in the text, especially many of the Wikipedia entries. Only information covered within the text of this course will be used on quizzes and exams, as the reference hyperlinks serve to support statements and data within the main body of this course. You are not responsible for information that exists outside of this course on external webpages.

Vocabulary and Glossary of Terms
Important scientific terms will be in bold print and may have a hyperlink to a clear definition of that term. These terms should be defined in your notes, as they will likely be referenced in quiz and exam questions. Use of flashcards with the term and its definition might be an important study tool for the exams.

title: Planet Earth/About the Book


text:
Talk:The Computer Revolution/Internet/Hackers

https://en.m.wikibooks.org/wiki/The_Computer_Revolution/Internet/Hackers
The Computer Revolution/Internet/Hackers Btaintap (discuss • contribs) 21:23, 24 February 2024 (UTC)


text:
Debates in Digital Culture 2019/Preamble

As the title suggests, this is a book which seeks to record contributions to the understanding of a specific set of topics, loosely grouped under the subject area of "Digital Culture", of particular salience to 2019.

It is put together through the combined talents and efforts of a cohort of students taking the undergraduate module FMSU9A4 during the Spring Semester 2019 at the University of Stirling in Scotland, UK. It is an assessed educational project. We would like to thank the Wikibooks community for assistance given in the course of this project, and also encourage leniency in dealing with our work - we are all beginners in the world of wiki here, but are keen to learn!

The aim of this educational project is, firstly, for students to record the content of their learning and their contributions to this book will reflect their studies on one of the featured themes. This will appear in the form of a series of Collaborative Essays, and therefore this Wikibook is a sort of edited collection or anthology, much like examples found in academic publishing. However, secondly and most importantly, the hope is that students will learn the values associated with working at different levels as individual researchers, as research teams, and as part of a research community on Wikimedia and other open knowledge platforms. That is to say: producing knowledge; collaboration and sharing; and peer-reviewing the work of others for the good of the community throughout Wikimedia, but in particular on Wikibooks.

Students will thus gain hands-on experience of a wiki environment, and what it is like to be part of a knowledge-building community, within the auspices of one of Wikimedia's large projects (i.e. Wikibooks) and make something that adds to currents in the academic field of digital media and society.

Note that while this is a class project, anyone may contribute as Wikibooks does not permit "ownership" of material.


text: Category:Cheddar recipes

title: Category:Cheddar recipes