Sponsor-Board.de

Hey,

da ich am Montag mündliche Prüfungen habe für mein Abitur sitze ich fest im Lernen. Ein Prüfungsthema beinhaltet die reguläre Grammatik, sprich rechts- und linksreguläre Sprachen.

Falls sich hier der ein oder andere Informatiker finden lässt, bitte ich um eine Erklärung, wie man von im untenstehenden Fall von der rechtsregulären Sprache eine äquivalente linksreguläre Sprache herleiten kann.

Fall: [Link: Registrierung erforderlich]
Ich habe versucht zum A^n B^n Problem einen Endlichen Automaten zu entwerfen, ebenso eine dazugehörigende rechtsreguläre Sprache. Ich habe aber, selbst nach stundenlangen Recherchen und etlichen Links von Unis usw. keine gute Erklärung gefunden, wie man nun diese linksreguläre Grammatik herleiten kann.

Falls sich jemand für solche theoretischen Sachen intressiert:
Ein Dank schonmal im Voraus für eure PM

Was bedeutet denn rechts- bzw. linksreguläre Sprache? Das hab ich noch nicht gehört.
Hat das was mit (nicht) deterministisch zu tun?

Für A^n B^n benötigst du auf jedenfall einen Kellerautomaten, aus der Zeichnung werde ich nicht wirklich schlau.

Das was du da siehst, ist rechtsreguläre Sprache, weil die zu ersetzenden Nichtterminale rechts stehen.

Bei der linksregulären Sprache stehen die zu ersetzenden Nichtterminale dementsprechend links, nur habe ich das Problem, dass ich nicht wirklich schlau wurde, ob man diese linksreguläre Sprache anders herleiten muss oder ob einfach nur die Nichtterminalen vertauscht wurden.