Рубрики

ВОРОТА | GATE-CS-2007 | Вопрос 7

Что из перечисленного правда?
(A) Каждое подмножество регулярного множества регулярно.
(B) Каждое конечное подмножество нерегулярного множества регулярно.
(C) Объединение двух нерегулярных множеств не является регулярным.
(D) Бесконечное объединение конечных множеств регулярно.

Ответ: (Б)
Объяснение:
Некоторые очки для регулярных наборов:

  • Множество всегда регулярно, если оно конечно.
  • Набор всегда регулярен, если для него можно нарисовать DFA / NFA.

Вариант A: Каждое подмножество регулярного набора является регулярным — False.
Для входных алфавитов a и b a * b * является регулярным. DFA можно нарисовать для a * b *, но anbn для n≥0, который является подмножеством a * b *, не является регулярным, поскольку мы не можем определить DFA для него.

Вариант B: Каждое конечное подмножество нерегулярного множества является регулярным, является Истиной.
Каждый конечный набор может иметь для него четко определенный DFA, поэтому независимо от того, является ли он подмножеством регулярного или нерегулярного набора, он всегда является регулярным.

Вариант C: объединение двух нерегулярных наборов не является регулярным и является ложным.
Для входных алфавитов a и b a n b n для всех n≥0 нерегулярно, а a n b m для n ≠ m также нерегулярно, но их объединение является a * b *, которое является регулярным.

Вариант D: TInfinite объединение конечных множеств регулярно является False.
Для входных алфавитов a и b множества {ab}, {aabb}, {aaabbb} …… .. являются регулярными, но их объединение {ab} U {aabb} U {aaabbb} U …………………… .. дает {anbn для n> 0}, который не является регулярным.

Это решение предоставлено Яшикой Арора .
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2007 | Вопрос 7

0.00 (0%) 0 votes