Как мне построить этот конечный автомат?
Я учусь на тест дискретной математики, и я нашел это упражнение, которое я не могу понять.
"Построить базовый конечный автомат (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
Есть ли в этом смысл?? Я думаю, что мои регулярные выражения дряблые.
4 ответа
Я нахожу вашу запись немного нечеткой, так что, возможно, я совершенно не понимаю. Если это так, не обращайте внимания на следующее. Кажется, ты еще не там
- Я предполагаю, что * означает "0 или более раз". Однако одна из строк с суммой>= 3 должна появиться. Это говорит, что вам нужен + ("1 или более раз").
- 112 и 211 отсутствуют в списке строк с суммой>= 3.
- 222 и 2222 в этом списке излишни.
- Все эти строки могут произвольно чередоваться с нулями.
- Сумма 00 не больше, чем сумма 0.
Изменить: как насчет этого (акк является единственным принимающим государством, точка-источник):
http://student.science.uva.nl/~sschroev/so/885411.png
В состояниях a и c сумма строк всегда нечетна. В начале состояний b и acc сумма всегда четна. Кроме того, в начале сумма равна 0, в точке b она равна 2, а в точке d она равна>= 4. Это легко доказать. Следовательно, принимающее государство соответствует всем критериям.
Изменить 2: Я бы сказал, что это регулярное выражение, которое принимает запрошенный язык:
0*(2|(1(0|2)*1))(0*(2|(1(0|2)*1))+
Не уверен, что это ответ на ваш вопрос, но: вам нужно отправить регулярное выражение? или будет делать FSM?
В любом случае, может быть полезно сначала нарисовать FSM, и я думаю, что это правильный DFA:
http://img254.imageshack.us/img254/5324/fsm.png
Если это так, то при создании вашего регулярного выражения (которое, помните, имеет другой синтаксис, чем программирование "regex"):
0* указать "0 столько раз, сколько вы хотите". Это имеет смысл, так как 0 в вашей строке не меняет состояние машины. (Смотрите, в FSM 0 просто возвращается к себе)
Вам нужно будет учитывать различные комбинации "112" или "22" и т. Д., Пока вы не наберете по крайней мере 4 в своей сумме.
Если ваша сумма больше 3 и даже, тогда (0|2)* будет держать вас в конечном состоянии. В противном случае (сумма> 3 и нечетное) вам понадобится что-то вроде 1(0|2)*, чтобы вы могли принять вас.
(не знаю, помогает ли это, или если это правильно - но это может быть началом!)
Мне проще просто думать в терминах состояний. Используйте пять состояний: 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
Только ДАЖЕ является принимающим государством.
Каждое выражение, руководствуясь Стефаном, может быть:
(0 * U 2 * U 11) * - четные суммы
с этим
(22 U 11 U 222 U 112 U 211 U 121)+ - те, чья сумма больше 3
Я не знаю, можно ли было бы упростить это больше, это помогло бы разработать автомат.