Исключительно простое уточнение выражения регулярного выражения (10) *

Question

Мне плохо задавать вопрос так просто, но я не могу понять это ради своей жизни.Мне нужно создать NFA на основе некоторых языков, и я не могу понять только один:

L = (10)*

Обратите внимание, что я не прошу никакой помощи в отношении FSM, но только некоторыеразъяснение того, что представляет язык.Большинство других языков были представлены мне в более понятной форме:

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

Я думаю, что это просто регулярное выражение, и после некоторого изучения листа шпаргалки регулярных выражений, мое единственное предположение, что этосоответствует группе 10 0 или более раз, но это явно не так, потому что все будет совпадать.

Любая помощь очень ценится.

Answer 1

Эти строки на языке (10) *:

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

Эти строки не на языке (10) *:

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

Помогает ли это?

Answer 2

Ваше мнение о значении в основном верно, но это не все, что соответствует.

В отличие от ваших обычных библиотек регулярных выражений, когда мы имеем дело с такой теорией языка, регулярное выражение должно соответствовать строке всей . Итак, ε (пустая строка) на языке, 10 на языке, 1010 на языке и т. Д. - все, что полностью состоит из строки «10», повторенной 0 или более раз.

01, однако, не в языке; строка не состоит из строки «10», повторенной 0 или более раз. 1 также не на языке, вы пропустите окончательный 0.

Я не знаю, рассматривали ли вы эту часть еще, но если вы конвертируете это регулярное выражение в NFA (или DFA, для него не требуется детерминизм), вы в основном получите это (немного упрощенно, если я правильно помню свой алгоритм преобразования, но это довольно тривиальное изменение от алгоритма к этому):

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

, где a - это принимающее состояние, а b - нет.

Помогает ли это вам понять, почему оно не соответствует всему?

Answer 3

Может ли это быть полезным? http://xenon.stanford.edu/~xusch/regexp/analyzer.html