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

Question

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

"Построить базовый конечный автомат (DFA, NFA, NFA-lambda) для языка в алфавите 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 или более раз». Однако одна из строк с суммой> = 3 должна появиться. Говорят, вам нужен + («1 или более раз»).
• 112 и 211 отсутствуют в списке строк с суммой> = 3.
• 222 и 2222 в этом списке излишни.
• Все эти строки могут произвольно чередоваться с нулями.
• Сумма 00 не больше, чем сумма 0.

---

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

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

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

Редактировать 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, 1, 2, ДАЖЕ, ODD

Переходы:

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

Только ДАЖЕ является принимающим состоянием.

Answer 4

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

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

с этим

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

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