Date: Thu, 4 Jan 2001 16:03:10 +0100 (MET)
X-Mailer: ELM [version 2.4ME+ PL61 (25)]
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Content-Length:  1532
Status: RO

> Bei dem 2. Aufgabenteil dieser Aufgabe weiß ich allerdings noch nicht so
> richtig wie man nicht so intuitiv bzw. mit Vorstellung diesen Teil löst,

das ist ja ein durchschnitt einer kontextfreien mit einer regulären sprache.
das kommt ganz offiziell im skript seite 59 oben.

in unserem fall geht es aber einfacher so: 
es dürfen nur zeichen klammer auf, klammer zu, x vorkommen,
also keine operatoren (plus oder minus)
damit dürfen nur noch die regeln  E -> x, E -> ( E ) benutzt werden,
und die bauen  G' = {  (^n x )^n  |  n >= 0 }

> Die Begründung 'warum das G' keine reguläre Sprache ist' fällt mir auch
> ziemlich schwer

danach war ja nicht gefragt, sondern nach G:

wenn  G regulär, dann auch  G' =  G  geschnitten mit  {(,),x}^*
(schnitt-abgeschlossenheit, siehe sätze skript seite 21)
aber G' ist nicht, also G auch nicht.


> - Kann man diese (G') damit geben das die Sprache {a^n * b^n | n
> € N} auch keine reguläre Sprache ist

entweder direkt durch kontraposition des pumping-lemmas
(siehe aktuelle übungsaufgaben) oder durch homomorphismus 
(= substitution, seite 21)
  h :  x -> epsilon, ( -> a,  ) -> b
auf  h (G') =  { a^n b^n | n >= 0 }


mfg
-- 
-- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ --
-- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --