was passiert mit einem Wort der Form a^n b^n c^n ?

Question

Mir ist auch nicht klar, was mit einem Wort der Form a^n b^n c^n passiert.

Die Menge: (aaabbbccc, aaaabbbbcccc) wäre doch eine endliche Menge von Wörtern, oder nicht?
Ein KA kann doch diese Wörter aber nicht erkennen!?

Answer 1

Richtig, die von dir angegebene Menge ist eine endliche Menge von Wörtern. Diese Sprache, die nur aus zwei Wörtern besteht, kann von einem KA erkannt werden, indem man das oben beschriebene Verfahren nutzt.

Die Sprache a^n b^n c^n mit n element N ist aber keine endliche Menge und kann von einem Kellerautomaten nicht erkannt werden (Beweis PPL).

Sven (Tutor)