Конечный автомат не принимает строку

Question

Как конечный автомат над (0,1) не принимает ни одной строки? Я могу думать только о

s->a->q->F 

Где конечное состояние F пусто. Это правда, пожалуйста?

Answer 1

Ответ, скорее всего, да. Почему «скорее всего»? Что ж.

Математически FSA является 5-кортежем (Sigma, S, s0, delta, F), где

• Sigma является алфавитом,
• S этим множество состояний,
• s0 начального состояния,
• delta является функцией перехода состояния,
• F - это набор принимающих состояний.

Поскольку вы исправили Sigma, есть только четыре места, где это может пойти не так. Если вы создаете FSA вручную, вы, конечно, создать один

• , что не имеет состояний
• , что не имеет начального состояния
• , в котором не все государства доступны
• , что не имеет принимающие государства

Если предположить, хорошо сформированную FSA (то есть S не пусто и s0 in S, все государства доступны), что в случае, если вы создаете его, например, от регулярное выражение с библиотекой, например foma, тогда да: единственный способ для FSA не принимать любую строку - это не принимать принимающие состояния.