CHAPTER 10

Automata, Grammars and Languages

10.1. Finite State Machines

A finite-state machine consists of the following:

1. A finite set of states S.

2. A finite set of input symbols I.

3. A finite set of output symbols O.

4. A next-state or transition function f : S × I -> S.

5. An output function g : S × I -> O.

6. An initial state S.

10.1.2. Finite-State Automata.

A finite-state automaton is similar to a finite-state machine but with no output, and with a set of states called accepting or final states. More specifically, finite-state automaton

consists of:

1. A finite set of states S.

2. A finite set of input symbols I.

3. A next-state or transition function f : S × I -> S.

4. An initial state S..

5. A subset F S of accepting or final states.

10.2. Languages and Grammars

10.2.1. Formal Languages.

In general, given a finite set A (the alphabet), a (formal) language over A is a subset of A* (set of strings of A).

10.2.2. Grammars.

A way to determine the structure of a language is with a grammar. In order to define a grammar we need two kinds of symbols: non-terminal, used to represent given subsets of the language, and terminal, the final symbols that occur in the strings of the language.

In general a phrase-structure grammar (or simply, grammar) G consists of

1. A finite set V of symbols called vocabulary or alphabet.

2. A subset T V of terminal symbols. The elements of N = V − T are called nonterminal symbols or nonterminals.

3. A start symbol N.

4. A finite subset P of (V* −T*)×V* called the set of productions.

We write G = (V, T, , P).

10.2.3. Backus Normal Form.

The Backus Normal Form or BNF is an alternative way to represent productions. The production S -> T is written S ::= T. Productions of the form S ::= T1, S ::= T2,

. . . , S ::= Tn, can be combined as S ::= T1 | T2 | • • • | Tn .

So, for instance, the grammar of algebraic expressions defined above can be written in BNF as follows:

E ::= T | E + T

T ::= F | T _ F

F ::= (E) | x | y | z