formale Sprache gesucht

[freakC++]

Hallo zusammen,

durch reguläre Ausdrücke kann ich reguläre Sprachen erzeugen. Beispiel eines regularen Ausdrucks: $r = ab*a$

Die Sprache L = L(r) beinhaltet alle Wörter, die mit einem a beginnen, dann beliebig viele b's hat und mit einem a aufhört. Soweit ist alles klar. Nun habe ich folgende Sprache:

$L_{1} = {a^nb^n : n \in \mathbb N}$

1.) Hierbei handelt es sich bekanntlicherweise um eine kontextfreie Sprache. Doch wie nenne ich diesen Ausdruck $a^nb^n$? Ein regulärer Ausdruck ist es ja nicht, aber spricht man hier von einem "kontextfreien Ausdruck"?

2.) Außerdem frage ich mich, wie man die Sprache über dem Alphabet {a,b}aufschreibt, die alle Wörter enthält, die gleich viele a's mit b's beinhaltet. Natürlich könnte ich schreiben:

$L_{2} = \{w \in \Sigma^*:$ Anzahl a = Anzahl b},

doch könnte ich das auch wie $L_{1}$ aufschreiben? Seht ihr eine Möglichkeit?

Vielen Dank
LG, freakC++

[Christoph]

freakC++ schrieb:

$L_{1} = {a^nb^n : n \in \mathbb N}$

1.) Hierbei handelt es sich bekanntlicherweise um eine kontextfreie Sprache. Doch wie nenne ich diesen Ausdruck $a^nb^n$? Ein regulärer Ausdruck ist es ja nicht, aber spricht man hier von einem "kontextfreien Ausdruck"?

Das ist einfach ein "Term" in der Metasprache, die hier benutzt wird. Um das genauer zu benennen, müsste man sich auf eine bestimmte formale Sprache festlegen. Wichtig sind aber die Mengenklammern:
$L_{1} = \{a^nb^n : n \in \mathbb N\}$

freakC++ schrieb:

2.) Außerdem frage ich mich, wie man die Sprache über dem Alphabet {a,b}aufschreibt, die alle Wörter enthält, die gleich viele a's mit b's beinhaltet. Natürlich könnte ich schreiben:

$L_{2} = \{w \in \Sigma^*:$ Anzahl a = Anzahl b},

doch könnte ich das auch wie $L_{1}$ aufschreiben?

Diese Sprachdefinition durch unnötige Formalismen zu verkomplizieren ist nicht besonders sinnvoll. In der Mathematik ist es üblich, Objekte mit Hilfe von Deutsch oder Englisch als Metasprache zu definieren, solange völlig eindeutig ist, was man meint.

L_2 würde ich zum Beispiel so definieren:
L_{2} = \{w \in \Sigma^*: \text{w$ enthält genau so viele $a$ wie $b$}}$.
In deiner Definition stand einfach nur "Anzahl a = Anzahl b". Da muss man genauer nachdenken, welche "Anzahl" denn nun gemeint ist. Wenn du die Anzahl der a im Wort w meinst, schreib das ruhig hin.

Man könnte natürlich eine neue Definition einführen:
Für ein Wort w und einen Buchstaben $x \in \Sigma$ sei $|w|_x$ die Anzahl von x in w.

Dann kann man L_2 definieren als
$L_{2} = \{w \in \Sigma^*: |w|\_a = |w|\_b\}$.
Ob das leichter zu verstehen ist als die erste Definition, muss man selber entscheiden.

[freakC++]

Alles klar! Vielen Dank für deine Erklärung und die Hilfe.

LG, freakC++

[knivil]

Scheint wohl Klausur- bzw. Nachklausurzeit zu sein.