Применение Клин Стар в FSM

Question

Во всех примерах, которые я видел при применении Kleene star к существующему FSM, я вижу, что создается новое принимающее и стартовое состояние, и существует эпсилон-переход из всех принимающих состояний в это состояние и эпсилон-переход из нового состоянияв исходное начальное состояние.Мой вопрос: зачем нам новое государство?Разве мы не можем просто сделать исходное начальное состояние принимающим (если оно еще не принимает) и связать с ним все принимающие состояния через эпсилон-переход?

Спасибо!

Гил

Answer 1

Поскольку исходное начальное состояние могло иметь самопереход.Рассмотрим язык L = a*b с DFA

A -a-> A
A -b-> B

С B в качестве принимающего состояния.

Если вы сделали состояние A принимающим и добавили переход B -ε-> A, теперьязык принимает слово a.a не является членом L*, поэтому этот новый DFA не является L*, это что-то другое.

Вместо этого мы добавляем новое начальное, принимающее состояние C:

C -ε-> A
A -a-> A
A -b-> B
B -ε-> C

a больше не является словом, принятым этим εNDFA.Этот язык L*.