Extrem einfache Regex Expression Klarstellung (10) *

Question

Ich fühle mich schlecht über eine Frage so einfach zu fragen, aber ich kann diese für das Leben von mir nicht herausgefunden. Ich brauche einen NFA zu konstruieren, basierend auf einigen Sprachen, und das einzige, was ich kann nicht herausfinden, ist diese:

L = (10)*

Beachten Sie, dass ich nicht für jede Hilfe bin bitten die FSM über, aber nur einige Klärung, was die Sprache darstellt. Die meisten anderen Sprachen wurden in einer verständlichen Art und Weise mir vorgestellt:

L = {w | w contains an even number of 0's } 

Ich denke, es ist nur ein regulärer Ausdruck, und nach einigen Durchlesen des Regex Spickzettels, meine einzige Vermutung ist, dass es für die Gruppe 10 0 oder mehrmals übereinstimmt, aber das scheint offensichtlich nicht richtig, weil alles würde Spiel.

Jede Hilfe sehr geschätzt.

Answer 1

Ihr Glaube über die Bedeutung ist grundsätzlich richtig, aber es ist nicht alles, was passen würde.

Im Gegensatz zu Ihren üblichen Regex-Bibliotheken, wenn wir es zu tun mit der Sprache der Theorie wie diesen, ein regulärer Ausdruck muss den gesamte Match string. Also, e (leere Zeichenkette) ist in der Sprache, 10 in der Sprache ist, 1010 ist in der Sprache, und so weiter -. Alles, was besteht vollständig aus der Zeichenfolge „10“ wiederholt 0 oder mehrmals

01, jedoch ist nicht in der Sprache; die Zeichenfolge besteht nicht aus der Zeichenfolge „10“ wiederholt 0 oder mehrmals. 1 ist auch nicht in der Sprache, du bist die letzte 0 fehlt.

Ich weiß nicht, wenn Sie diesen Teil noch behandelt haben, aber wenn Sie diese Regex auf einen NFA konvertieren (oder einem DFA, Nicht-Determinismus ist nicht für diese erforderlich) Sie grundsätzlich diese bekommen würde (leicht vereinfacht, wenn ich richtig mein Konvertierungsalgorithmus erinnern, aber es ist vom Algorithmus dies eine ziemlich trivial ändern):

  1
 ┌─┐
 │ ↓
→a b
 ↑ │
 └─┘
  0

wo a ist ein akzeptierende Zustand und b nicht.

Ist diese Hilfe Sie sehen, warum es nicht alles passt?

Answer 2

Diese Strings sind in der Sprache (10) *:

<empty string>
10
1010
101010
10101010
(etc.)

Diese Strings sind nicht in der Sprache (10) *:

0
1
01
11
010
01010
101
10101
(etc.)

Enthält das helfen?

Answer 3

Könnte dies von Nutzen sein? http://xenon.stanford.edu/~xusch/regexp/analyzer.html