een taal van alle strings over sigma = {a, b, c} die geen enkel aa, bb, of cc bevatten

Grammatica

G = (V, T, S, P) met

S empty string

S goes to a NOTA

S goes to b NOTB

S goes to c NOTC

NOTA goes to empty string

NOTA goes to b NOTB

NOTA goes to c NOTC

NOTB goes to empty string

NOTB goes to a NOTA

NOTB goes to c NOTC

NOTC goes toempty string

NOTC goes to a NOTA

NOTC goes to b NOTB

Voorbeeld: S directly derives a NOTA directly derives a b NOTB directly derives a b a NOTA directly derives a b a c NOTC directly derives a b a c.

 

NFA - Non-deterministic Finite Automaton

 

nfa

 

Regular expression

 X a Y a Y a Y a ... Y a Z

(X a (Y a)* Z)|X

X = (bc)*(b|empty string)|(cb)*(c|empty string)

idem voor Z.

Y = ((bc)*b|(cb)*c)

((bc)*(b|empty string)|(cb)*(c|empty string) a (((bc)*b|(cb)*c) a)* (bc)*(b|empty string)|(cb)*(c|empty string))|(bc)*(b|empty string)|(cb)*(c|empty string)

 

Ontleend aan Theory of Computation