graphs and trees

A graph is a picture of things and the connections between them: dots (called vertices or nodes) joined by lines (called edges). A subway map, a friendship network, a flowchart — all are graphs. When the connections have a direction (a one-way arrow), we have a directed graph. This is exactly the picture you draw for a finite automaton: each state is a node, and each transition is a labelled arrow from one node to another.

Formally a directed graph is a set of vertices V together with a set of edges, each edge an ordered pair (u, v) drawn as an arrow from u to v. A path is a sequence of edges you can walk in order following the arrows, and a cycle is a path that loops back to where it started. A tree is a special graph with no cycles and exactly one path between any two nodes: it has a single top node called the root, every other node has exactly one parent, and nodes with no children are leaves. A tree is the natural shape for anything that branches without ever rejoining — a family tree, a folder hierarchy, or the structure of a sentence.

These two pictures carry most of the diagrams in this subject. A state diagram of an automaton is a directed graph, and asking 'does this input drive the machine from the start state to an accept state?' is asking whether a particular path exists. A parse tree shows how a grammar derives a string, with the start symbol at the root, grammar rules branching downward, and the actual string read off the leaves left to right; structural induction, defined later, proves facts about all such trees by building up from the leaves.