детерминированный конечный автомат (ДКА) Экзамен Q

Вопрос заключается в том:детерминированный конечный автомат (ДКА) Экзамен Q

Разработайте детерминированный конечный автомат (ДКА) в соответствии со следующей спецификации:

 Его алфавитом {0, 1}.

 Его язык состоит из всех слов с нечетным числом 1s.

 0 не принимаются (даже если они являются частью алфавита).

Итак, это я уверен, что это означает, что он будет принимать только в качестве примера «111» и отказаться от «11»

Моей первой попытки, хотя она работала (принимаю 111 отклоняет 11) он принимает на 0-х

моей вторая попытка я попытался создать таблицу переходов первой, то диаграммы, но q1 не имела стадии q2, если я не сделал мой стол неправильно

моей последнюю попытку it..worked я думаю? Но я не уверен, если эта схема действует

Может кто-нибудь дать мне некоторое представление о том, на какой из 3-х диаграмм является правильным/заголовком правильного пути и как именно бы я решить эту проблему/сделать таблицу переходов

Update: вы имеете в виду, как это @Pavel PAJA Halbich

источник

2016-12-22 Anonymous

«Его язык состоит из всех слов с нечетным числом 1s., 0s не принимаются (даже если они являются частью алфавита)». - означает ли это, что вам нужно создать FSM, принимающий слова 1^(2n + 1), где n> = 0? –

Я считаю, что это означает, что ваша строка не может содержать 0 в ней, хотя она является частью алфавита, но машина не позволяет 0. Если количество 0 и ODD равно 1. он все равно должен его отвергнуть. Состояние accept должно содержать только 1 и нечетное количество. –

Это странно с 0s. Они не принимаются в любом случае (благодаря даже количеству 1 с), и вы не можете отклонить символ - вы принимаете или отклоняете весь ввод, который является словом. –

Ваша окончательная схема хороша (но не действует). Для того, чтобы получить его в силе, необходимо добавить переходы:

q1 -> q2, используя 0
q2 -> q2 с использованием 0,1 (это классический провал состояние)

Тогда вы будете имеют 3 состояния и для каждого состояния определяют переход в другое состояние, одно начальное состояние (q0) и набор принимающих состояний ({q1}).

источник

2016-12-22 13:43:13

Я вижу, но тогда, хотя у нас есть q1 -> q2, как вы получаете от q2 -> q1? –

Я обновил главный пост в конце, вы имеете в виду вот так? –

@godlypython Если вы говорите, что если слово на входе содержит по крайней мере на 0, вы отклоняете это слово, тогда вам нужно создать состояние отказа, где вы получите использование любого 0 на входе. Тогда вы никогда не должны возвращаться к исходным состояниям (поскольку вы находитесь в состоянии сбоя) –

детерминированный конечный автомат (ДКА) Экзамен Q

ответ

Смежные вопросы