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

Question

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

"Постройте базовый конечный автомат (DFA, NFA, NFA-лямбда) для языка в алфавите Sigma = {0,1,2}, где сумма элементов в строке четная И эта сумма больше 3"

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

(00 U 11 U 22 U 02 U 20)* - четные элементы

с этим

(22 U 1111 U 222 U 2222)* - те , сумма которых больше 3

Есть ли в этом какой-то смысл??Я думаю, что мои регулярные выражения дряблые.

Answer 1

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

• Я предполагаю, что * означает "0 или более раз".Однако должна встречаться одна из строк с sum >= 3.Допустим, вам нужно + ('1 или более раз').
• 112 и 211 отсутствуют в списке строк с sum >= 3.
• 222 и 2222 в этом списке являются лишними.
• Все эти строки могут произвольно перемежаться с 0s.
• Сумма 00 не более четна, чем сумма 0.

---

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

автомат http://student.science.uva.nl /~sschroev/so/885411.png

В государствах a и c сумма строк всегда нечетна.В государствах начать, b и асс сумма всегда четная.Кроме того, при начать сумма равна 0, при b это 2 и при d это >= 4.Это можно довольно легко доказать.Следовательно, принимающее состояние асс соответствует всем критериям.

Правка 2: Я бы сказал, что это регулярное выражение, которое принимает запрошенный язык:

0*(2|(1(0|2)*1))(0*(2|(1(0|2)*1))+

Answer 2

Не уверен, отвечает ли это на ваш вопрос, но:вам нужно отправить регулярное выражение?или подойдет FSM?

В любом случае, возможно, было бы полезно сначала нарисовать FSM, и я подумай это правильный DFA:

FSM http://img254.imageshack.us/img254/5324/fsm.png

Если это так, то при построении вашего регулярного выражения (которое, помните, имеет другой синтаксис, чем программирование "regex"):

0* указать "0 столько раз, сколько вы хотите".Это имеет смысл, поскольку 0 в вашей строке не изменяет состояние компьютера.(Видите ли, в FSM 0 просто возвращается к самому себе)

Вам нужно будет учитывать различные комбинации "112" или "22" и т.д. - пока ваша сумма не достигнет как минимум 4.

Если ваша сумма больше 3 и четна, то (0/2) * удержит вас в конечном состоянии.В противном случае (сумма > 3 и нечетная) вам понадобится что-то вроде 1 (0/2) *, чтобы перевести вас в принимающее состояние.

(не знаю, помогает ли это и правильно ли это, но это может быть началом!)

Answer 3

Каждое выражение, руководствуясь Стефаном, может быть:

(0*U 2* U 11)* - четные суммы

с этим

(22 U 11 U 222 U 112 U 211 U 121)+ - те, сумма которых больше 3

Я не знаю, можно ли это упростить еще больше, это помогло бы спроектировать автомат.

Answer 4

Мне легче просто мыслить в терминах состояний.Используйте пять состояний:0, 1, 2, ЧЕТНЫЙ, НЕЧЕТНЫЙ

Переходы:

State, Input -> New State

(0, 0) -> 0
(0, 1) -> 1
(0, 2) -> 2

(1, 0) -> 1
(1, 1) -> 2
(1, 2) -> ODD

(2, 0) -> 2
(2, 1) -> ODD
(2, 2) -> EVEN

(ODD, 0) -> ODD
(ODD, 1) -> EVEN
(ODD, 2) -> ODD

(EVEN, 0) -> EVEN
(EVEN, 1) -> ODD
(EVEN, 2) -> EVEN

Только ЧЕТНОСТЬ является принимающим состоянием.