Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 30

Если конечные и неконечные состояния в DFA ниже взаимозаменяемы, то какой из следующих языков в алфавите {a, b} будет принят новым DFA?

(A) Набор всех строк, которые не заканчиваются на
(B) Набор всех строк, которые начинаются с a или ab
(C) Набор всех строк, которые не содержат подстроку ab,
(D) Множество, описываемое регулярным выражением b * aa * (ba) * b *

Ответ: (А)
Объяснение:

По-видимому, DFA, полученный путем обмена конечными и неконечными состояниями, будет дополнением данного регулярного языка. Итак, чтобы доказать, что семейство строк принято дополнением к L, мы в свою очередь докажем, что оно отвергнуто L.
(А) . Множество всех строк, которые не заканчиваются на ab. Это утверждение может быть доказано правильно, если взглянуть на b отмеченные инцидентные ребра в конечных состояниях и отмеченные ребра, предшествующие им. Дополнение данного DFA будет иметь первые два состояния в качестве конечных состояний. Первое состояние не имеет ребра с меткой b, перед которым стоит метка. Аналогично, второе конечное состояние не имеет такого обязательного b помеченного ребра. Точно так же можно доказать, что все строки, принятые данным DFA, заканчиваются на ab. Теперь, когда L ∪ дополнение (L) = (a + b) ∗, L должно быть множеством всех строк, оканчивающихся на ab, а дополнение (L) должно быть множеством всех строк, которые не оканчиваются на ab. [ВЕРНЫЙ]
(Б) Набор всех строк, которые начинаются с a или ab — это утверждение неверно. Чтобы доказать, что мы просто должны показать, что существует строка, начинающаяся с a или ab, которая принята данным DFA. Строка abaab принята данным DFA, следовательно, не будет принята его дополнением. [НЕПРАВИЛЬНЫЙ]
(С) . Набор всех строк, которые не содержат подстроку ab. Чтобы доказать, что это утверждение неверно, мы должны показать, что существует строка, которая не содержит подстроку ab и не принята текущим DFA. Следовательно, это будет принято его дополнением, делая это утверждение неверным. Строка aba не принимается этим DFA. [НЕПРАВИЛЬНЫЙ]
(D). Множество, описываемое регулярным выражением b ∗ aa ∗ (ba) ∗ b ∗ — строка abaaaba, не принимается данным DFA, следовательно, принимается его ком

Это решение предоставлено Винет Пурсвани .

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | Gate IT 2008 | Вопрос 30

0.00 (0%) 0 votes