вопрос sigma = (1,2,3, $). Мне нужно нарисовать его диаграмму, которая выводит 1, когда сумма> _5. если он превышает 5, сумма будет перенесена.о состояниях конечного автомата
Im интересно, что было бы в этом случае. Могу ли я позволить A = ive видеть 1 B = ive видно 2, C = ive см. 3 и D = принято состояние?
Нет, вы не можете использовать только три состояния. Ваш FSM должен каким-то образом продолжать подсчитывать текущую сумму входных значений. Проблема в том, что FSM не имеет памяти (это был бы другой тип автоматов), поэтому он должен быть одним из состояний для каждой возможной комбинации чисел, которые оцениваются во всех возможных суммах.
То есть: вам нужно состояние, которое означает («текущая сумма равна 0»). Пусть это состояние будет состоять из 0. Это будет ваше начальное состояние. Другие состояния будут «текущая сумма равна 1» (состояние 1), «текущая сумма равна 2» (состояние 2), ...., «текущая сумма равна 5» (состояние 5), «текущая сумма равна 6 "(состояние 6) и т. Д. (Нет, вам не понадобится некоторое число состояний, например, из состояния 5, переход со значением 1 приведет вас снова к состоянию 1.
Из состояния 0 , переход с 1 приводит вас к состоянию 1. Переход с 2, к состоянию 2 и переход с 3 в состояние 3. Легко, не так ли?
Из состояния 3, например, переход с 1 ведет вас к переходу 4, переход с 2 в состояние 5, который является принимающим состоянием, и переход с 3 в состояние 6, что также является принятым состоянием.
Чтобы привести еще один пример: из состояния 6 переход с 1 приводит вас к состоянию 2. Это правильно: состояние 6 означает, что текущая сумма равна 6, что превышает 5 в 1. Таким образом, это похоже на переход 1, но это принятое состояние, поэтому переходы из состояния 6 переходят в те же места, что и переходы из состояния 1. Это поможет вам построить свой FSM.
Фактически, большее число состояний определяется наибольшим значением, которое вы можете суммировать с 1,2 и 3, которое переполняет 5 в первый раз. Это будет 1 + 1 + 1 + 1 + 3 = 7. Поэтому вам нужно определить из состояния 0 в состояние 7 и, конечно, конечное состояние при обнаружении $.
спасибо! Я нарисовал диаграмму, и на моей диаграмме слишком много стрел, плавающих вокруг и обратно, поэтому я не уверен, правильно ли я вас понимаю. На моей диаграмме, для состояния 1, я должен перейти в состояние 2,3,4,5,6 и для состояния 2, я должен перейти в состояние 3,4,5,6 и так далее. Из состояния 6 я должен перейти только к состоянию 2,3,4. И принятое государство будет состоять только из 5 и 6. Я прав? – oliver
Кроме того, у меня есть состояние 0 до состояния 6 и + конечное состояние. Я не уверен, почему мне нужно состояние 7. Я думал, что мне нужно только до 6, потому что 6 - это первое число, которое больше или равно 5. Мне все еще нужно состояние 7 ?? Я нарисовал его с состоянием 0, чтобы указать 7, и в этом случае состояние 5,6,7 станет моим принятым состоянием. – oliver
№ Из состояния 1, если «1» означает, что текущая сумма равна 1, у вас есть три перехода (не считая перехода к окончательному состоянию, если sumbol «$»): один, если символ равен 1, что соответствует в состояние 2. Еще один, если символ равен 2, который переходит в состояние 3, а другой, если символ равен 3, который перейдет в состояние 4, так как это единственные возможные символы на вашем входе. –
Вам не нужно отслеживать текущую сумму. Вам просто нужно отслеживать общую сумму по модулю 5.
Один из способов сделать это, чтобы ваше пространство состояний было A0, A1, A2, A3, A4 и B0, B1, B2. Если вы входите в состояние «A», вы выводите 0, и если вы входите в состояние «B», вы выходите на экран.
Переходы состояния зависят от следующей цифры, которую вы видите. Например:
В общем, предположим, что вы находитесь в состоянии XY, w здесь X является либо A, либо B, а Y равно 0, 1, 2, 3 или 4. Пусть D - следующая цифра, которую вы видите. Следующее состояние вы войдете будет Им, где:
В вашем вопросе говорится «когда текущая сумма больше или равна 5». Поэтому вам нужно будет отслеживать, какова текущая сумма; поэтому вам понадобится другое состояние для каждой возможной суммы, и вам понадобится переход состояния для каждой комбинации «Я только что видел X и сумму того, что я видел с момента последнего выхода a 1 - Y ". Начните рисовать их на листе бумаги, и все должно стать ясным. – moonshadow
Благодарим вас за комментарий: D. Я думал об этом несколько минут, но я не могу понять, как отслеживать текущую сумму. Единственный инструмент, который у меня есть для этого вопроса, - «вход/выход». Можете ли вы привести мне пример такой диаграммы? – oliver
Подождите! Вы только что изменили вопрос, и теперь ваши принятые состояния - это те, в которых сумма меньше 5? –