[informatik-bonn] Re: Frage

  • From: Thorsten Horstmann <Thorsten.Horstmann@xxxxxx>
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: Sat, 21 Jun 2003 15:53:26 +0200

Lutz Oberst wrote:

Beh: Das Komplement einer nicht kfS, kann nicht kontextfrei sein.

Bew: Meine Überlegung basiert darauft, daß man ja zu einem
gegebenen Kellerautomat einfach das Komplement bilden kann
indem man F':= Q \ F und Q':= Q \ F' setzt.
KA die auf einen leeren Keller hin anhalten, lassen sich
zu KA die auf Endzustände hin stoppen umbauen.

das funktioniert nicht fuer alle Kellerautomaten, denn dann waere ja das Komplement einer kfS wieder kontextfrei. Das ist aber im allgemeinen nicht so.

Wenn es zum Komplement einer nicht kfS also einen Kellerautomaten
M gäbe, wäre das Komplement vom M weiterhin ein Kellerautomat,
aber L(M) wäre nicht kontextfrei. Wiederspruch.

s.o.


HTH,
  -Thorsten


Other related posts: