Topic

Midterm Exam Review Notes—CS 465 Spring 2015

About the exam

the exam will be held Wednesday 18 March 2015 at 1:50 (usual class time) in the usual place (Ford 204)

the exam will be closed book, closed notes, closed computer/internet

the exam will consist of several kinds of questions; typically:

10-15 True-or-False questions at 1-2 points each

8-10 short answer questions at 4-6 points each

2-4 longer answer questions at 8-15 points each

selected, useful definitions from the Haskell Prelude will be supplied for you

study resources

the course home page, including diagrams, code and general links

the homework assignments and lab

Wikipedia articles linked from the home page

and, of course, your own lecture notes!

Discrete Math review

mathematics can be founded on set theory—but there are alternatives (e.g., type theory, category theory)

membership is all that matters for sets: a set consists of its members and nothing else (in particular, unlike a sequence or list, a set has no order and no repetitions)

we can write out some sets explicitly with braces and commas, and sometimes an ellipsis (…)

… but the ellipsis leaves a “gap” that is up to some interpretation

we can express some sets using operations on other sets (empty set, union, intersection, complement, cartesian product, discrete sum, power set) [you should know these operations!]

finally, we can express some sets using “set comprehension”: { x ∈ S | P(x) }

the set of x in S such that P of x (for some property P)

properties might make use of membership and subsets, as well as logical properties (and, or, not) and domain-specific ones (e.g., values of coins or card suits, etc.)

the cardinality of a set is the number of elements or members it has (sometimes generalized to various kinds of infinity rather than a specific finite number)

sets of the same cardinality can be put into one-to-one correspondence with one another

we can encode various concepts from math in terms of sets: natural numbers, functions, predicates and relations, pairs, sequences, etc.

Haskell review

Haskell coding skills will not be a big part of the exam, but just as in lecture, we will use Haskell as a conveniently executable meta-language

the review in this section is mainly to help remind you of some key Haskell concepts & notation we make significant use of in the course

expressions, values, and types (every expression must have a valid type)

basic types and their values (Bool, Int, Integer, Char)

pairs and tuples (like products) versus lists (more complex structure)

the Either and Maybe types (Either is like a sum)

functions, including higher-order functions

algebraic type definitions

defining functions using recursion and patterns (esp. “template style”)

common Prelude definitions

you will be supplied with an “appendix” of Prelude definitions, but it always helps to be familiar with some of them from the outset

some of the most common Prelude functions: arithmetic operators (+, *, –), length, head, tail, reverse, map, zip, unzip, zipWith, foldr, (++), concat, replicate, take, drop, elem, fst, snd, flip

Introduction to language and formalism

language exists in a spectrum, from very informal/unstructured (internal/personal language) through spoken, written and semi-formal (e.g., legal language), to formal languages proper

formal languages include logic, mathematics, programming languages, and things like HTML (for the web) and LaTEX (for producing math documents)

language presumably developed primarily for interpersonal communication, but also plays a role in consciousness (internal language), memory (e.g.. externalizing memory) and conceptual clarification

automated formal languages allow for the creation of static, active, reactive, and interactive “conceptual artifacts” (e.g., running programs)

the form or structure of language has dual nature: both a linear surface structure (strings), but also a recursive structure built from hierarchical phrases (terms or trees)

syntax is the structure (esp. hierarchical phrase structure) of language; semantics is meaning or interpretation of language

an object language is a language we study (speak of, write about, reason about, etc.); a meta-language is one we use to study (speak of, etc.) another

in this course we mainly study interpreted formal languages, consisting of finite/discrete structures (built from symbols) and various ways that they may understood to represent abstract concepts (their meanings)

traditional usage in computer science theory defines the phrase “formal language” to mean just a set of strings: we focus as much or more on the underlying phrase structures and their meanings

Sums, products and (finite) functions—the high school algebra axioms

high school axioms describe abstract behavior of sums, products, and functions

“Power Rings” chart of axioms

we can interpret these axioms as being about logic, arithmetic, or structures (finite sets, types)

for logic, equivalence is bi-implication (i.e., logical equivalence of formulas)

for arithmetic, it is the usual equality between numbers

for structures, it is isomorphism (the existence of mappings back and forth)

we also interpret the operations and constants

for logic, we have true/false, disjunction (or), conjunction (and), and implication (if-then)

note, however, that x^y is interpreted as “y implies x”

for arithmetic, we have the usual interpretation

for structures,

in addition, there are relations between the levels

for arithmetic, we can map 0 to false and everything else (n>0) to true

for structures, we can consider the size (cardinality) of structures to be numbers

for structures, we can consider the existence of any structure (at least one) to be “true”, else false

we can thus use the same axioms, familiar from school arithmetic, to reason about logic and structure

Haskell types are almost like those of type theory, except for the existence of “bottom” (unfettered recursion, with no “value”)

in category theory, sums and products are “opposites” of each other (duals)

intuitively, sums = choice, products = combinations, functions/exponents = connections

Symbols, sequences, and strings

symbols are basic pieces of syntax which we use to communicate in speech, writing, data transmission, etc.

examples include phonemes (distinct sounds), words, letters, ASCII codes, Unicode sequences (e.g., UTF-8)

we think of symbols as relatively atomic: in some situations, there is further structure to them (letters in words, bits in codes), but the structure is not semantically significant in itself

a set of symbols used in some linguistic context as a kind of global vocabulary of symbols is called an alphabet; often the symbol (!) Σ (sigma) is used as a meta-variable for alphabets

usually we intend alphabets to be finite, so we will not specify this overtly, but rather in those few cases when we want to discuss infinite alphabets, we will say so explicitly

although the connotations of specific symbols are important, for finite alphabets we could always code the symbols as natural numbers, given some (perhaps arbitrary) ordering

if numbers coding symbols are themselves written as numerals in some base (e.g., base 2), then we essentially have one alphabet (the original symbols) expressed via coding in another (the digits of a particular base)

for example, when we view ASCII characters as represented by their 7-bit binary codes

when multiple alphabets are involved, we also usually intend them to be non-overlapping to avoid confusion (confusion is especially likely between object and meta-language)

sequences can be thought of abstractly, or encoded/defined in various ways

abstractly, we could define various operations and properties

mathematically, we see them as functions from a limited range of naturals to the element type

computationally (in Haskell), we see them as lists, defined inductively via sums and products

you should be familiar with the view of lists as defined in terms of sums, products, and recursion

sequences of symbols are called strings: they may be communicated over time (as in speech) or over space (as in writing), but in constituting the surface structure of language, they have an essentially linear form

we usually intend individual strings to be finite, even if they occur as part of an infinite language

the cardinality of a language of finite but indefinite-length strings over a finite alphabet is still countable, even if infinite (for uncountable sets, such as the real numbers, we would need infinite-length strings)

a set of strings (typically a subset of the set of all strings over some alphabet) is called a formal language (this is the older terminology for uninterpreted languages, viewed just as sets)

more abstractly, we can consider strings as an algebra of values under a binary operation (concatenation) with a unit (the empty string)

concatenation is associative, but not in general commutative

associative: x·(y·z) = (x·y)·z

commutative: x·y = y·x

a (linear) ordering on an alphabet can be naturally extended to strings lexicographically:

the empty string is less than any non-empty one

two strings with different initial letters are ordered according to their initial letters

two strings with the same initial letter are ordered according to the remainders (tails) of the strings

Regular languages (reg. exprs. and DFAs)

we want to describe patterns over strings, i.e., sets of strings which we say match the pattern

a given description or representation will thus describe a(n uninterpreted) formal language

we explore several different classes of languages: regular, context-free, etc. of increasing complexity

the visual metaphor used in lectures is of a “cut” through a set, leaving some strings in and some out

for each language class, we will consider several different (but equivalent) representations, or general ways of describing specific languages

for regular languages we will study:

regular expressions

DFAs (deterministic finite automata)

NFAs (non-deterministic finite automata)

GNFAs (generalized NFAs)—not on the exam!

regular expressions are terms of one of 6 forms: null, epsilon, literals, unions (|), concatenations (·) and Kleene stars (*)

a context-free grammar for REs (!): R ::= ∅ | ε | a | (R | S) | (R · S) | R*

(notice that one of those ‘|’ is an object symbol, not a meta-symbol!)

the meanings of regular expressions can be given by describing meanings recursively as sets of strings for each form of RE

see RegLangDefns.pdf

the denotational approach of describing sets of strings recursively does not give any direct means of deciding if any given string matches a certain RE

a DFA (deterministic finite automaton) is an abstract machine which can efficiently (in time proportional to the length of a string) determine if a string matches a pattern

DFAs have a finite control consisting of states which transition one to another upon the machine’s “seeing” the next character of the string

DFAs can also be represented as tables or diagrams (these are usually easiest for people to analyze)

we can show that for every RE there is an equivalent DFA and vice versa, in the sense that they recognize the same language

in the process of proving this fact, we introduce NFAs (non-deterministic finite automata) which allow moves without seeing a character (epsilon transitions) or which target multiple states

NFAs turn out to be equivalent to DFAs: we can convert an NFA into a DFA whose states are members of the power set of the original machine’s state set

this works because the original set is finite, and thus so is the power set

we also saw the product construction (or “two-finger” technique) for combining two DFAs: the product machine has states which are pairs of the original machines, and runs like the two original machines in “lock step” through the string

final states could be combined in a number of ways—we saw them combined with ‘OR’ so that the new machine accepts when either of the originals does

in proving that every DFA can be converted to an equivalent RE, we used an intermediary type of machine called a GNFA which assigns an RE to every pair of states, allowing a transition between them whenever a substring matching the RE is seen

the conversion algorithm proceeds by “ripping out” one state after another, decorating the transitions between states with revised REs that allow for behavior enforced by the ripped state

Numbers and numerals

perhaps the most basic of abstract concepts in mathematics are the counting numbers, also called the natural numbers (we will take them as starting at zero; some people start at one)

recent research suggests that writing itself arose from written numerals: first clay tokens were used to “record” quantities of goods, the tokens collected into clay envelopes, and the markings added to the envelopes eventually used by themselves to represent the quantities

we call the symbolic representations of numbers numerals (e.g., Roman numerals, “Arabic” numerals, etc.)

a simple system of tallies represents natural numbers using sequences of a single symbol: each occurrence of the symbol counts one more

tallies facilitate successive counting: just add one more symbol (if erasure is available, subtraction is easy, too)

addition of tally numerals is simply concatenation of the underlying strings

in Haskell we can use lists of some single-valued type (e.g., the unit type) as tallies

tallies are an inefficient representation: they use only one symbol and the length of the representation is proportional to the number being represented

the Roman numeral system uses various letters to represent different numbers, and combines them in somewhat irregular ways to represent larger numbers

the so-called “Arabic numerals” (really Hindi) use an ordered alphabet of digits to represent numbers as numerals so that numeral length is proportional to the logarithm of the number

in a positional place value system, the “value” of every digit is just its place in the alphabetic ordering, and its contribution to the whole is proportional to a power of the base, depending on its position within the numeral

mathematically:

formula for value of a numeral

Horner’s method for evaluating numerals proceeds from left to right (as they are read), adding each digit value to a running total, after multiplying the previous total by the base

we can “reverse” Horner’s method to obtain a numeral for any number by successively dividing by the base, using the remainder as the value of the next digit from right to left, and continuing with the quotient (the result of integer division)

in Haskell, we can succinctly represent the Horner and reverse Horner algorithms as a fold and an unfold

int b = foldl (sumProd b) 0 . map digitToInt

str b = map intToDigit . unfoldl (==0) (`divMod` b)

Giuseppe Peano described the natural numbers formally as an algebra consisting of a constant (zero) and a unary operation (successor)

Peano’s axioms include an induction axiom which states that any property which holds for zero and which is preserved by successor holds for all natural numbers

in Haskell, we can represent the naturals as an algebraic datatype

data Nat = Zero | Succ Nat

the generic fold (see below) over naturals represented this way defines a parameterized iteration scheme:

foldn z s  Zero    = z

foldn z s (Succ n) = s (foldn z s n)

at a more abstract level, we can consider an algebra of numbers with operations addition and multiplication (sometimes also exponentiation) and constants for zero and one

Algebraic terms

hierarchical nature of the syntax of realistic languages (i.e., not so trivial as numerals)

in mathematics, we have a notion of algebra: a set with values, some operations on those values, and various relations on them (most important, equality)

algebraic terms are built hierarchically from constants or literals by way of application of operators to their arguments

constants: atomic terms interpreted as fixed values in the carrier (set of values) of the algebra

literals: not-quite atomic terms (but perhaps linear syntax) where the structure has meaning

because operators are often binary, these terms have a tree-like structure (as opposed to the list-like structure of numerals)

the semantics of terms is usually given as a function of their structure, in a compositional way: the meaning of a combined term is a function of the meanings of its parts

we can identify:

standard semantics: the usual, conventional meaning of the terms (e.g., numbers)

non-standard semantics (abstracted): a sparser space of meanings (e.g., parity or sign of numbers)

non-standard semantics (elaborated): a richer space of meanings

from a functional meta-language perspective:

terms can be represented as values of algebraic data types

compositional semantics can be realized in terms of folds over those types

recipe for fold-style semantics:

define the term structures via an (parameterized) algebraic data type

identify the semantic domain (set of values)

give meanings to each of the constant, literal, and operator-based forms of syntax

combine these (parametric) meanings into a fold over the data type

informally, we often flip back and forth between the concrete syntax (strings) and a more abstract structure (hierarchical term structure)

we can usefully view concrete syntax (the printed or pretty-printed form of a term) as a kind of non-standard semantics

from a computational perspective, we can define a number of useful tools “semantically”:

parsers

printers & pretty-printers

static analyzers

tracers

interactive calculators

compilers / translators

Free variables and (polynomial) functions

we can represent polynomial functions in an algebra with sums and products by including a single, distinguished variable (call it x)

we can either:

give semantics as a function of x: then our “target” type for the folds is a function (from N to N)

or we can compute the polynomial representation of the same function, providing perhaps better insight and opportunities for analysis

of course, we can always evaluate said polynomials at some x value … using folds! (Horner)

other operations, such as derivatives and substitution (= function composition) can be supported

there is in general a hierarchy of functions: finite, polynomial, computable (and many levels in between)

the structure looks just like that for algebraic expressions, but with a unit constructor (n argument) for the variable

we can extend semantics in a straightforward way (for various semantics) by including an extra fold clause

we can imagine several kinds of semantics for such expressions, of varying degrees of abstraction:

just the "syntactic semantics" of the abstract term structures (i.e. parsing from strings to terms)

a semantics in terms of (reversed) lists of coefficients as an efficient representation (use Horner!) of the polynomial

a pure Haskell function (no longer subject to printing or comparison)

Context-free grammars and languages

regular languages are not powerful enough to specify many patterns of interest

cannot express the language anbn

cannot express the language wwR (R for reverse)

cannot express the language of balanced parenthesis sequences

DFAs lacks the “memory” necessary to recognize these languages: because the DFA has no record of where it has been beyond the finite control, it cannot avoid certain repetitive or looping behaviors

a more powerful pair of concepts, CFGs (context-free grammars) and PDAs (push-down automata) can be used characterize a more complex class of context-free languages

a CFG is a set of rules which allow strings to be built up by successive replacement

see the Wikipedia page or your lecture notes for a specific set-theoretic definition

a start symbol and some other symbols are called variables or non-terminals: they comprise the left-hand sides of rules

the right-hand sides of rules are just strings of terminal symbols (ones which appear in the final strings) and other variables

define a set of trees as follows: label the root of the tree with the start symbol, then “expand” any variable-labelled node into children labelled, in order, by the symbols on the rich-hand side of a rule

generate trees by choosing any node with a variable to expand, and expand separately according to all rules with that variable on the left-hand side

the strings generated by a CFG are the fringes of terminal symbols associated with all such trees

OR, we can define a derivation as a sequence of strings related by expanding a variable symbol in one string according to a rule to produce the next string

these definitions provide no easy way to determine if any particular string can be generated by a given CFG

some strings have several derivations with respect to the same grammar

if they all correspond to structurally identical trees, this is not a problem, just an ambiguity in what order the variables are expanded

if some derivations correspond to different trees, the structure of the term and thus its meaning might be ambiguous (this is a bigger problem)

some languages are inherently ambiguous, in that any grammar that generates the language will have the structural sort of ambiguities