[informatik-bonn] Frage

  • From: Lutz Oberst <oberst@xxxxxxxxxxx>
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: Sat, 21 Jun 2003 11:48:23 +0200

Hallo,

folgene Überlegung zu 1:

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.

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.



Ist an der Überlegung was falsch, oder ist das richtig?

Bye, Lutz
-- 
signature intentionally left blank


Other related posts: