Minimale Pumplänge für die folgenden regulären Sprachen

8

Was ist die minimale Pumplänge für die folgenden Sprachen?

  1. Die leere Sprache
  2. (01)*
  3. 10(11*0)*0
  4. 1011
  5. 011 U 0*1*

Hier sind meine Lösungen. Bitte korrigieren Sie mich, wenn ich falsch liege.

  1. p = 0, weil die Sprache keine pumpbaren Strings hat
  2. p = 2, weil 01 die kürzeste Zeichenfolge ist, die gepumpt werden kann
  3. p = 5, weil 10100 die kürzeste Zeichenfolge ist, die gepumpt werden kann
  4. p = 0, da String nicht gepumpt werden kann
  5. p = 1, weil die Zeichenkette 0 gepumpt werden kann

Ich bin mir über meine Antworten nicht sicher, daher wird jede Hilfe geschätzt. Vielen Dank!

    
user2293062 09.10.2015, 00:36
quelle

2 Antworten

5

Ich denke, dass die Antwort von Simon vielleicht etwas daneben ist. Sie müssen in der Tat einen Zyklus irgendwo nehmen. Das Pumping-Lemma erfordert, dass der Pfad, der zum Erkennen der Zeichenkette benötigt wird, einen Zyklus umfasst (dies ist das "y" des Pump-Lemmas "xyz"). Wir können diesen Zyklus so oft machen, wie wir wollen, was die Kette pumpt.

  1. Dies sollte 1 sein. Die minimale Pumplänge muss immer größer als 0 sein, auch wenn es in der Sprache keine Strings gibt.
  2. Dies sollte 2 sein. Wenn p = 1 ist, können wir 01 nicht pumpen (weil y gleich 0 sein muss und 001 nicht in der Sprache ist).
  3. Dies sollte 5 sein.
  4. Dies sollte auch 5 sein. Wenn wir p = 4 setzen, dann behaupten wir, dass "1011" pumpbar ist (was es nicht ist, da es die einzige Zeichenfolge in der Sprache ist).
  5. p = 1.
Alec Brickner 04.06.2016 11:33
quelle
4

Laut Patrick87 ist die minimale Pumplänge definiert als die maximale Anzahl von Übergängen, die Sie in einem minimierten DFA ausführen können, ohne einen Status zweimal zu besuchen. Der Prozess wandelt dann Ihren regulären Ausdruck in einen NFA um, konvertiert den NFA in einen DFA, minimiert den DFA und zählt den längsten Pfad entlang der gerichteten Kanten, ohne denselben Status zweimal zu verwenden. Für eine Einführung in diese Umwandlung und Minimierung, siehe zum Beispiel Torben Mogensens freies Buch, Grundlagen des Compiler Designs Kapitel 2.6, 2.8.

Gemäß dieser Definition

  1. p = 0, da im minimierten DFA für die leere Sprache keine Übergänge vorhanden sind.
  2. p = 1. Ein minimierter DFA für (01)* hat zwei Zustände, und Sie können nur einen Übergang durchführen, ohne den ursprünglichen, akzeptierenden Zustand zu erreichen.
  3. p = 3. Ein minimierter DFA für 10(11*0)*0 hat einen Status, der zweimal besucht werden muss, damit der Unterausdruck (11*0)* Teil der Ableitung ist.
  4. p = 4. Ein minimierter DFA für 1011 hat genau 4 Kanten und keine Rekursion.
  5. p = 1. Die Sprache 011 ist eine Teilmenge der Sprache 0*1* , also 011 U 0*1* = 0*1* . Und da weder 0 noch 1 gepumpt werden können, kann man nur einer nicht-rekursiven Kante folgen.

    
Simon Shine 17.12.2015 16:57
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset npm Installation mit Pre-Release-Versionen