A modern approach to AI · Appendix B

Notes on Languages and Algorithms

Formal grammars describe valid strings; pseudocode communicates procedures independently of a programming language.

Appendix guide

  1. B.1 Defining Languages with Backus–Naur Form (BNF)

    BNF uses production rules to define how nonterminal symbols expand into terminals and other nonterminals. Alternatives express choices.

  2. B.2 Describing Algorithms with Pseudocode

    Pseudocode makes control flow and data operations readable without fixing syntax to a particular implementation language.

  3. B.3 Online Supplemental Material

    Supplemental resources can provide updates, exercises, and materials beyond a printed edition; consult the book's official companion resources.

Interactive: expand a BNF grammar

Step through a derivation of “the robot sees a star.” Each action replaces the leftmost remaining nonterminal using a rule.

<sentence> ::= <np> <vp>
<np> ::= <det> <noun>
<vp> ::= <verb> <np>
<det> ::= the | a
<noun> ::= robot | star
<verb> ::= sees

Initial sentential form.

Grammar terms and derivation

A terminal is a literal token such as “robot”; a nonterminal names a category such as <np>; a production gives permitted replacements. BNF's ::= means “is defined as,” and | separates alternatives. For the worked sentence, <sentence> expands to <np> <vp>, then the subject becomes “the robot”; the verb phrase becomes “sees” plus the object noun phrase, yielding “the robot sees a star.” Each displayed step replaces the leftmost remaining nonterminal. A complete string of terminals is licensed by the grammar; it is not thereby guaranteed to be meaningful in context.

There are 4 noun phrases (2 determiners × 2 nouns) and 4 verb phrases (the single verb plus one noun phrase), so this tiny grammar licenses 16 sentence strings. It does not encode agreement, semantics, or open-ended vocabulary.

Derivation complexity

The interactive demo is a fixed, precomputed sequence of D=10 sentential forms: clicking Next advances an index in O(1) algorithm time; rendering the current string of length ℓ takes O(ℓ) time. Across a full trace the render cost is O(Σℓᵢ), bounded by O(D·L) when each form has at most L symbols. The precomputed forms take O(D·L) stored space and the current visible text takes O(L); the grammar is fixed-size. This is the cost of this scripted visualization, not a general parser or grammar-expansion engine. A generic implementation that searches and copies a sentential form at each replacement would depend on its chosen representation and could spend O(D·L) time for D steps of forms up to length L.