# CST 8152 - Lexical Glossary

- We want to recognize a
**LANGUAGE**.
- We write a
**GRAMMAR** for the
language.
- The grammar is composed of
**PRODUCTIONS**
containing **TERMINAL** symbols and **NON-TERMINAL**
symbols.
- Terminal symbols are
**TOKENS**,
classified by a **LEXICAL ANALYSER** or **SCANNER**.
- The scanner reads the input and recognizes
character sequences called
**LEXEMES** and classifies
them into tokens.
- The structure of the lexemes is based on
**PATTERNS**.
- The patterns are often expressed using
**REGULAR
EXPRESSIONS** and **REGULAR** **DEFINITIONS**.
- Regular expressions are equivalent to
**FINITE
AUTOMATA**.
- Finite automata can be either
**DETERMINISTIC**
or **NON-DETERMINISTIC**.
- Deterministic finite automata can be
constructed from non-deterministic finite automata;
however, the construction may require an exponential
number of states.
*We can compile a regular expression
into a recognizer by constructing the finite automaton to
which it is equivalent*.
- Finite automata can be represented using
**STATE
MACHINES**.
- State machines may be
**DETERMINISTIC**
or **NON-DETERMINISTIC**.
- State machines may be expressed using
**TRANSITION
DIAGRAMS** (deterministic) and **TRANSITION GRAPHS**
(non-deterministic).
- From the transition diagrams and graphs we
can construct
**TRANSITION TABLES** that tell what the
next state is, based on the current state and the current
input character.
- Transition tables can be coded.