Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 53

Рассмотрим машину М:

Язык, распознаваемый М:
(A) {w ∈ {a, b} * / за каждым a в w следует ровно два b}
(B) {w ∈ {a, b} * за каждым a в w следует не менее двух b '}
(C) {w ∈ {a, b} * w содержит подстроку 'abb'}
(D) {w ∈ {a, b} * w не содержит «aa» в качестве подстроки}

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

Здесь w ∈ {a, b} * означает, что w может быть любой строкой из набора {a, b} *, а {a, b} * — набором всех строк, состоящих из a и b (любая строка из a и b, которая вы можете думать о) как ноль, а, б, ааа, аббааа, ббббб, ааааа, ааааббббааббабабаб и т. д.

Этот тип вопросов часто задают в GATE, где его просят выбрать наиболее подходящий язык среди вариантов. Чтобы решить вопрос, подобный этому, есть лучший способ, мы пытаемся устранить неправильные варианты, разумно выбирая строки тестирования до тех пор, пока у нас не останется один правильный вариант. Что касается вопроса, давайте попробуем исключить параметр (A), он распознает только Thos е строка (состоит из а и б) , в котором всякое а в ш следует ровно два б, так что если мы возьмем строку abbb (три б), то оно принимается машиной, так что эта опция не так. Теперь мы пытаемся исключить опцию (C), она распознает только те строки (составленные из a и b), в которых w содержит подстроку 'abb', поэтому, если мы возьмем строку abbaa (имеет подстроку abb), то она не будет принята машина, поэтому этот вариант тоже неверен. Теперь мы пытаемся исключить опцию (D), она распознает только те строки (состоящие из a и b), в которых w не содержит «aa» в качестве подстроки, поэтому, если мы примем строку abbaba («aa» не как подстроку) , то это не принимается машиной, поэтому этот вариант тоже неверен. Единственный вариант, с которым мы остались, — это вариант (b), в котором за каждым a в w следует, по крайней мере, два b ', это правильно. Так что ответом является вариант (B).

Это решение предоставлено N irmal Bharadwaj.

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

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

ВОРОТА | GATE-CS-2005 | Вопрос 53

0.00 (0%) 0 votes