Beweisen, dass eine Sprache regulär ist

[Kirby.exe]

Also um dies zu beweisen, muss man ja zwei Dinge tun:

• Eine Grammatik aufstellen welcher nur Wörter der Sprache erstellen kann
• Einen Automaten konstruieren welcher nur Wörter dieser Grammatik akzeptiert

Nun zu meinem Problem:

Ich habe die nachfolgende Sprache gegeben --> {a^nb^{2n} | 1 <= n <= 10}. Ich verstehe nicht wie ich es bewerkstelligen soll, das man wirklich nur maximal das Wort mit folgender Anzahl an Buchstaben erstellen kann: a^{10}b^{20}.

 

[httpdigest]

Beispiel einer regulären Grammatik, die Wörter der genannten Sprache generieren kann:

A1 -> a A2 bb
A2 -> ε
A2 -> a A3 bb
A3 -> ε
A3 -> a A4 bb
...
A10 -> ε
A10 -> abb

Diese Grammatik ist regulär, da die linke Seite jeder Produktionsregel nur ein Nichtterminalsymbol ist und die rechte Seite jeder Regel nur aus höchsten einem Nichtterminalsymbol besteht.

Wenn die Längeneinschränkung bis max. n=10 nicht wäre, würde die Grammatik einfacher sein. Da die Beschränkung aber besteht, benötigen wir 10 Produktionsregeln.

 

[Gelöschtes Mitglied 65838]

Beispiel einer regulären Grammatik, die Wörter der genannten Sprache generieren kann:

A1 -> a A2 bb
A2 -> ε
A2 -> a A3 bb
A3 -> ε
A3 -> a A4 bb
...
A10 -> ε
A10 -> abb

Diese Grammatik ist regulär, da die linke Seite jeder Produktionsregel nur ein Nichtterminalsymbol ist und die rechte Seite jeder Regel nur aus höchsten einem Nichtterminalsymbol besteht.

Wenn die Längeneinschränkung bis max. n=10 nicht wäre, würde die Grammatik einfacher sein. Da die Beschränkung aber besteht, benötigen wir 10 Produktionsregeln.

du musst nicht jeden Fall abdecken da man durch die Regel 1 <= n <= 10} sowieso nichts größeres als 10 einsetzen darf

Ausserdem müsstest du noch beweisen dass das pumping lemma gegeben ist


ein Wort das n = 11 braucht wird einfach shcon von der Definition der Grammatik nicht akzeptiert und ist halt kein Wort der Sprache

 

[httpdigest]

du musst nicht jeden Fall abdecken da man durch die Regel 1 <= n <= 10} sowieso nichts größeres als 10 einsetzen darf

Gemäss der Definition der Sprache benötigen wir 10 Produktionsregeln, um eben genau die Bedingung 1 <= n <= 10 abzudecken.
Es wird also nicht jeder Fall abgedeckt, sondern genau die erlaubten Fälle mit 1 <= n <= 10.

 

[fhoffmann]

Diese Grammatik ist regulär, da die linke Seite jeder Produktionsregel nur ein Nichtterminalsymbol ist und die rechte Seite jeder Regel nur aus höchsten einem Nichtterminalsymbol besteht.

Dies genügt aber nicht für eine reguläre Grammatik!

 

[Kirby.exe]

Ausserdem müsstest du noch beweisen dass das pumping lemma gegeben ist

Naja eigentlich nicht, da nur weil das Pumping Lema gilt, heißt es nicht dass die Sprache regulär ist oder etwa nicht?

Ich weiß dass man mit dem Lema beweisen kann, dass eine Sprache nicht regulär ist und zwar mittels Wiederspruchsbeweises

 

[Gelöschtes Mitglied 65838]

Naja eigentlich nicht, da nur weil das Pumping Lema gilt, heißt es nicht dass die Sprache regulär ist oder etwa nicht?

Ich weiß dass man mit dem Lema beweisen kann, dass eine Sprache nicht regulär ist und zwar mittels Wiederspruchsbeweises

die menge von n ist so klein dass man das pumping Lemma für alle beweisen kann um da schon mal sicher zu sein, wenn man dann noch die Definierte Sprache hat die rechts oder links regulär ist , dann hat man ja schon mal mehr

 

[Gelöschtes Mitglied 65838]

Beispiel einer regulären Grammatik, die Wörter der genannten Sprache generieren kann:

A1 -> a A2 bb
A2 -> ε
A2 -> a A3 bb
A3 -> ε
A3 -> a A4 bb
...
A10 -> ε
A10 -> abb

Diese Grammatik ist regulär, da die linke Seite jeder Produktionsregel nur ein Nichtterminalsymbol ist und die rechte Seite jeder Regel nur aus höchsten einem Nichtterminalsymbol besteht.

Wenn die Längeneinschränkung bis max. n=10 nicht wäre, würde die Grammatik einfacher sein. Da die Beschränkung aber besteht, benötigen wir 10 Produktionsregeln.

ausserdem ist das keine Reguläre Sprache die du gegeben hast das ist eine CH2 Sprache
da sie weder links noch rechtsregulär ist

EDIT: Also wenn man schon mal links oder rechts regulär ist, und auf anhieb keinen pumping lemma widerspruch findet ist man shcon gut dabei