Entscheidungsverfahren (Kodierung)

Kodierung ist nötig,

denn Mod(F)⊆$\mathbb {N}$^k, aber Lang(A)⊆Σ^*.

wählen Σ = {0, 1}^k, benutze Ideen:

• Kodierung einer Zahl: binär (LSB links)

  c(3) = 11, c(13) = 1011

• Kodierung eines Tupels: durch Stapeln

  c(3, 13) = (1, 1)(1, 0)(0, 1)(0, 1)

Beispiele: Automat oder reg. Ausdruck für

• {c(x) | $x$ ist gerade}, {c(x) | $x$ ist durch $3$ teilbar},
• {c(x, y) | x + x = y}, {c(x, y, z) | x + y = z},
• {c(x, y) | x≤y}, {c(x, y) | x < y}