Der endliche Akzeptor A = (Z, z0, X, f , F) sei gegeben durch b

Question

1. Geben Sie die von A akzeptierte Sprache L(A) unter ausschließlicher Be- nutzung der formalen Sprachen {a}, {b} sowie {a,b}, des Konkatenati- onsabschlusses, des ε-freien Konkatenationsabschlusses und des Produkts formaler Sprachen an.

   Beispiel: {a, b}∗ · {a} · {b}

2. b)  Geben Sie graphisch einen endlichen Akzeptor B mit vier Zuständen an,

   der dieselbe formale Sprache wie A akzeptiert.

3. c)  Geben Sie graphisch einen endlichen Akzeptor C mit vier Zuständen an,

   von denen zwei akzeptierend sind, der die formale Sprache L(C) = {a}∗ · {b} · {a}∗ · {b}+ · {a, b}∗ akzeptiert.  

Answer 1

zu 2b)

Wenn man bei Zustand 1 einen Pfeil auf sich selbst mit der Beschriftung a anbringt,

ist es doch ok.  Dann kann 2 weggelassen werden.