Entscheidungsverfahren (Kodierung)

Kodierung ist nötig,

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

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

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

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

• Kodierung eines Tupels: durch Stapeln

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

Beispiele: Automat oder reg. Ausdruck für

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