Ist die Sprache der Wörter mit der gleichen Anzahl von 001 und 100 regulär?

Ich fragte mich, wann Sprachen, die die gleiche Anzahl von Instanzen von zwei Teilzeichenfolgen enthielten, regelmäßig sein würden. Ich weiß, dass die Sprache mit der gleichen Anzahl von Einsen und Nullen nicht regulär ist, sondern eine Sprache wie , wobei = Anzahl der Instanzen der Teilzeichenfolge "001" gleich der Anzahl der Instanzen der Teilzeichenfolge "100" ist. regelmäßig? Beachten Sie, dass die Zeichenfolge "00100" akzeptiert würde. $L$ $L$ $\{ w \mid$ $\}$

Meine Intuition sagt mir, dass dies nicht der Fall ist, aber ich kann das nicht beweisen. Ich kann es nicht in eine Form umwandeln, die über das pumpfähige Lemma gepumpt werden kann. Wie kann ich das beweisen? Andererseits habe ich versucht, einen DFA oder einen NFA oder einen regulären Ausdruck zu erstellen, und bin auch an diesen Fronten gescheitert. Wie soll ich also vorgehen? Ich möchte dies allgemein verstehen, nicht nur für die vorgeschlagene Sprache.

formal-languages regular-languages pumping-lemma Ben Elgar
quelle

Hast du gesehen, wie man beweist, dass eine Sprache nicht regelmäßig ist ?

Juho

Warum können Sie Ihre eigene Lösung nicht beantworten?

Yuval Filmus

@YuvalFilmus Es gibt eine Verzögerung für Benutzer mit geringer Reputation, um ihre eigene Frage zu beantworten (8 Stunden, wenn rep <100).

Gilles 'SO- hör auf böse zu sein'

Wahrscheinlich sollte es bei

eine zusätzliche

Schleife geben ?

0

$0$

q 5

$q5$

Hendrik Jan

Ein ähnliches Beispiel für dieses Phänomen, jedoch für die Teilzeichenfolgen "01" und "10", wurde auf unserer Schwestersite besprochen. Das Prüfen einer Sprache ist regelmäßig oder unregelmäßig . Die Antwort hat eine ähnliche Bemerkung wie in seinem Kommentar: "Das heißt, auf einen 01-Übergang kann kein weiterer

Übergang folgen, ohne einen dazwischenliegenden

Übergang."

01

$01$

10

$10$

Hendrik Jan

Antworten:

Eine Antwort aus der Frage.

Wie Hendrik Jan betonte, sollte es bei q5 eine zusätzliche 0-Selbstschleife geben.

Automat

Juho
quelle

Dies ist eine Konstruktion, kein Beweis

vzn

In CS-Klassen werden für einfache Probleme manchmal nur DFAs angegeben, aber es beweist nicht, dass es die Sprache genau akzeptiert. du musst [irgendwie] für jeden eingabestring anzeigen, dass er richtig funktioniert. "wie funktioniert es?"

VZN

q_{5}

$q_5$

q_{2}

$q_2$

Es ist eine Trickfrage. Versuchen Sie, einen String zu konstruieren, der zwei 001 enthält und keine 100 enthält, und sehen Sie, warum Sie das nicht können. Wenn X = "Anzahl von 001" und Y = "Anzahl von 100", dann ist X = Y oder X = Y ± 1.

Sobald Sie den Trick erkannt haben, wird es höchst unwahrscheinlich, dass die Sprache unregelmäßig ist, und dann ist das Erstellen eines DFA recht einfach. Es gibt nur 8 Zustände mit ihren Übergängen, wenn das nächste Symbol 0/1 ist:

State S0: Input is empty. -> S1/C0

State S1: Input is 0. -> C2/C0

State A: Y = X + 1, input ends in 00. -> A/C0

State B0: X = Y + 1, input ends in 1. -> B1/B0

State B1: X = Y + 1, input ends in 10. -> C2/B0

State C0: X = Y, input ends in 1. -> C1/C0

State C1: X = Y, input ends in 10. -> A/C0

State C2: X = Y, input ends in 00. -> C2/B0

Der Anfangszustand ist S0, und S0, S1, C0, C1, C2 akzeptieren Zustände.

gnasher729
quelle