November 10 * Chomsky Hierarchy Chomsky numbered the four families of languages that make up the Chomsky hierarchy. Type 0 Recursively enumerable TM Phase-structured grammars Type 1 Context Sensitive LBA CSG Type 2 Context Free PDA CFG Type 3 Regular FSM RE Restrictions on the grammars increase with the type number. * Decidability A "decision problem" consists of a set of questions whose answers are either yes or no. A solution to a decision problem is a procedure that determines the yes/no answer for each question in the set. A decision problem is "undecidable" if there is no algorithm that solves the problem. The ability of Turing machines to return affirmative and negative responses makes them appropriate for constructing solutions to decision problems. The "Church-Turing thesis" asserts that a Turing machine can be designed to solve any decision problem that is solvable. To establish that a problem is unsolvable it thus suffices to show that there is no Turing machine solution. We are not yet looking at efficiency. Example The question "Is 8 a perfect square?" is an example of the type of question under consideration in a decision problem. A decision problem usually consists of an infinite number of related questions. Decision Problem: Determine whether an arbitrary natural number is a perfect square. Is 0 a perfect square? Is 1 a perfect square? Is 2 a perfect square? ... Every search problem (search for a solution) has a corresponding decision (yes/no answer) problem. Search Problem: Input = G, a context-free grammar Desired Output = shortest w such that w has two leftmost derivations (if G is ambiguous) or "not ambiguous" if G is unambiguous. Corresponding Decision Problem: Input = G, a context-free grammar Desired Output = "yes" if G is ambiguous "no" if G is not ambiguous Formally, a decision problem is a set. In this case, Assumeis the encoding in {0,1}* for grammar G, where we employ some reasonable encoding conventions. Then the decision problem above can be stated: L_ambiguous = { : G is a CFG that is ambiguous} If L_ambiguous is recursive, then we say the problem of determining whether a CFG is ambiguous is "decidable". If L_ambiguous ia not recursive, then the problem is "undecidable". In general, we have taken a search problem and perhaps made it easier by replacing it with a decision problem. If the decision problem is undecidable, then certainly no algorithm exists for the search problem. Example - Does there exist a substring of exactly 83 adjacent 7s in the decimal expansion of pi? This is decidable!!! There exists an algorithm to solve it. The algorithm is either M_yes or M_no, where M_yes says "yes", M_no says "no", regardless of input. We just don't know which algorithm is the correct algorithm, but we know the right one exists. Example - A more general problem is Does there exists a substring of exactly n consecutive 7s in the decimal expansion of pi? Language is {n: there exists substring of exactly n ... in pi}. This may or not be recursive (decidable). Example - L = {n: there exists substring of >=n consecutive 7s in the decimal expansion of pi}. This is recursive. In fact, it is regular! Optional Read book to see an example of a language that is not recursively enumerable. No machine can halt on acceptance of a string in this language. * Logic Instead of using languages to understand the theory of computation, we will now use languages to generate statements that have a true or false value. The "meaning" of a sentence (logically) is a mapping onto the "real world". This mapping is an "interpretation" (interpretation of C code, for example). A sentence is "valid" (necessarily true, tautology) iff it is true under all possible interpretations. A or not-A Interpretation of A could be: - Today is Monday - 2 + 3 = 5 The above statement is valid. These statements are not valid. A & not-A A v B The last statement is "satisfiable", meaning there exists at least one interpretation that makes the statement true. The previous statement is "unsatisfiable". - An "interpretation I" consists of An assignment of truth values to all proposition symbols I(S) - Models: worlds in which a particular sentence is true under at least one interpretation * Logics - Propositional logic Symbols represent entire facts Boolean connectives (&, v, ->, <=>, ~) Propositions (symbols, facts) are either TRUE or FALSE - First-order logic Extend propositional logic to include variables, quantifiers, functions, objects * Propositional Logic - Symbols represent entire facts Formulas in propositional calculus (the language of propositional logic) using symbols. P, Q, etc. An formula is an "atomic formula" if it follows one of these rules. 1. A single symbol with a T/F value is an atomic formula. 2. If f,g are atomic formulas, then f v g is an atomic formula (the disjunction of f and g). 2. If f,g are atomic formulas, then f & g is an atomic formula (the conjunction of f and g). 2. If f is an atomic formulas, then -f is an atomic formula (the negation of f). - A "truth assignment" is a function from a set of atomic formulas to the set {T, F} of "truth values". Let alpha be a truth assignment. The function alpha is defined as 1. alpha(f v g) = T if alpha(f) = T or alpha(g) = T F otherwise 2. alpha(f & g) = T if alpha(f) = T and alpha(g) = T F otherwise 3. alpha(-f) = T if alpha(f) = F F otherwise - The true/false value of propositions and combinations of propositions can be calculated using a truth table The first n columns are labeled with the atomic subformulas of f, subsequenct columns are labeled with the other subformulas of f that are constructed from the atomic formulas. The last column is labeled with f itself. The table has 2^n rows, one for each n-tuple of truth-values for the atomic formulas. The tables is filled with T and F as appropriate. The formula is valid when the rightmost column consists entirely of Ts. The formula is satisfiable when the rightmost column contains at least one T. The formula is unsatisfiable when the rightmost column contains all Fs. A row in the truth table is one interpretation of the symbols. Examples A B | A v B A | -A A B | A & B ----+------ --+--- ----+------ T T | T T | F T T | T T F | T F | T T F | F F T | T F T | F F F | F F F | F A B | A->B A B | A<->B ----+----- ----+------ T T | T T T | T T F | F T F | F F T | T F T | F F F | T F F | T