Bitfolgen mit count (1s) anzeigen = count (0s) ist nicht regulär

Question

Sei L die Sprache, die aus Zeichenfolgen über dem Alphabet {0,1} besteht, die eine gleiche Anzahl von 1en und 0en enthalten.

Beispielsweise:

000111
10010011
10
1010101010

Wie können Sie zeigen, dass L keine reguläre Sprache ist?

Answer 1

Ich denke, Sie können das genaue Argument verwenden, das verwendet wird, der zum Anzeigen von {0 ^ n 1 ^ n: n> 0} verwendet wird/ p>

nimmt an, dass l regelmäßig ist.Es muss also das Pumpen-Lemma für einige Ganzzahl n (die Pumplänge) erfüllen.Nehmen Sie den String S=0^n 1^n, der zu L. gemäß der Lemma gehört.Beobachten Sie, dass S=xyz nur aus Nullen bestehen muss.Jetzt pumpen|xy| <= n, und Sie fügen nur Nullen an die Saite hinzu, die nicht mehr zu L. gehört, sodass Sie einen Widerspruch haben.So ist ich nicht regelmäßig.

Answer 2

Ich weiß nicht über einen formalen Beweis, aber die Intuition ist, dass Sie nicht konstruieren können, dass ein DFA nicht bauen kann, um diese Sprache zu erkennen (berücksichtigen, dass es eine ungelistierte Anzahl von Staaten erfordern würde, um die Saiten des Formulars generationspflichtig zu verfolgen..

Answer 3

Der formale Beweis kann mit dem Pumping-Lemma für reguläre Sprachen wie folgt gegeben werden:

Angenommen, die Sprache ist regulär.Es muss also das Pumplemma für eine konstante ganze Zahl p erfüllen.Lassen s sei eine beliebige Zeichenfolge mit der gleichen Anzahl von 0 und 1.Dann kann s in 3 Teile x, y, z unterteilt werden, so dass |xy|<=p, |y|>0, dann x(y^i)z, wo i>=0sollte auch zu L gehören.

Lassen Sie mich die Zeichenfolge wie folgt teilen:

• y ist ein Teil einer Zeichenfolge mit einer ungleichen Anzahl von 0 und 1.
• x könnte der Teilstring von sein s vor y.
• z könnte der Teil danach sein y.

Nun, wenn ich die Saite "abpumpe", indem ich nehme i = 0, dann wäre die verbleibende Zeichenfolge nur xz das wird definitiv eine ungleiche Anzahl von 0 und 1 haben, die nicht zur Sprache L gehört.

Damit haben wir einen Widerspruch erreicht, da wir früher angenommen haben, dass L regelmäßig ist.

Daher ist es nicht regelmäßig.

Wenn es etwas schwierig war, den obigen Teil zu verstehen, betrachten Sie ein Beispiel.Sei p eine ganze Zahl 5.Lassen 0+1000+11101 sei eine Zeichenfolge in L.(+ zeigt Verkettung an) Lass mich x nehmen, um zu sein "0", und sein "1000", z sei der verbleibende Teil 11101.Dann, wenn wir durchführen x(y^i)z mit i=0, die verbleibende Zeichenfolge wäre 011101 was nicht Teil von L ist.Also unregelmäßig.

Beachten:das Beispiel war nur ein Beispiel, damit Sie die Logik verstehen.Man kann den Wert von p nicht zufällig bestimmen.