Теория вычислений GATE 2012

Question

4) Рассмотрим набор строк на {0,1}, в котором каждая подстрока из 3 символов имеет не более двух нулей. Например, 001110 и 011001 находятся на языке, но 100010 - нет. Все строки длиной менее 3 также находятся на языке. Частично завершенный DFA, который принимает этот язык, показан ниже.

Отсутствующие дуги в DFA являются

Я готовлю для GATE в следующем году именно поэтому я взял на GATE вопрос так что любая помощь в отношении вопроса будет appreciated.Thank вы !

Answer 1

Ответ является опцией (D). Сначала начните с языка, который не должен иметь трех последовательных 0. поэтому 0 вход в состояние 00 должен перейти в мертвое состояние (q). и он определяется только в параметрах (C) и (D). теперь у нас осталось только два варианта. теперь вы видите состояние 10. в опции (C) 0 вход в состояние 10 он переходит только в 10, это цикл и любое число от 0 до 10, оно остается только на 10, а 10 также является окончательным, так что он принимает язык с любым отсутствием последовательных 0, и этого не должно быть. так что теперь мы ушли с опцией (D) и с (D) 0 входом до 10, он переходит в состояние 00, а еще один от 0 до 00 он переходит в мертвое состояние, поэтому он не будет принимать три последовательных 0, и он будет делать то, что наш язык want.and ваш DFA должен понравиться.

и это делается только в варианте (D) .sorry за мой плохой английский.