# Beweisen, dass eine Sprache regulär ist



## Kirby.exe (12. Mai 2021)

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 (12. Mai 2021)

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 (12. Mai 2021)

httpdigest hat gesagt.:


> Beispiel einer regulären Grammatik, die Wörter der genannten Sprache generieren kann:
> 
> ```
> A1 -> a A2 bb
> ...





> 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 (12. Mai 2021)

Joreyk hat gesagt.:


> 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 (12. Mai 2021)

httpdigest hat gesagt.:


> 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 (12. Mai 2021)

Joreyk hat gesagt.:


> 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 (12. Mai 2021)

Kirby.exe hat gesagt.:


> 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 (12. Mai 2021)

httpdigest hat gesagt.:


> Beispiel einer regulären Grammatik, die Wörter der genannten Sprache generieren kann:
> 
> ```
> A1 -> a A2 bb
> ...


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


----------

