Рубрики

ВОРОТА | GATE IT 2006 | Вопрос 82

Пусть L обычный язык. Рассмотрим конструкции на L ниже:
repeat (L) = {ww | w ∊ L}
префикс (L) = {u | ∃v: uv ∊ L}
суффикс (L) = {v | Uu uv ∊ L}
половина (L) = {u | :V: | V | = | ты | и уф ∊ L}
Какой вариант L лучше всего подходит для поддержки вашего ответа выше?
(А) (а + б) *
(B) {ϵ, a, ab, bab}
(С) (ab) *
(D) {a n b n | n ≥ 0}

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

Контрпример, который подтверждает все выводы последнего вопроса за один раз, должен иметь следующие свойства:

  • L должно быть регулярным в связи с требованием вопроса
  • L должен быть бесконечным множеством строк, иначе половина (L) будет правильной
  • В грамматике L должно быть более одного алфавита, в противном случае повтор (L) будет регулярным.

Следовательно,

  1. (a + b) * является идеальным примером для поддержки выводов последнего вопроса. Он регулярный, имеет более одного алфавита и представляет собой бесконечное множество.
  2. {ϵ, a, ab, bab} — конечное множество, следовательно, неверное.
  3. (ab) * эквивалентно c ∗, который является одним алфавитным языком, следовательно, неверен.
  4. {a n b n | n ≥ 0} даже не является обычным языком, следовательно, неверным.

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

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

ВОРОТА | GATE IT 2006 | Вопрос 82

0.00 (0%) 0 votes