Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 52

GATE

Сопоставьте следующие NFA с регулярными выражениями, которым они соответствуют

 1. ϵ + 0(01*1 + 00) * 01*
 2. ϵ + 0(10 *1 + 00) * 0
 3. ϵ + 0(10 *1 + 10) *1
 4. ϵ + 0(10 *1 + 10) *10 *


(A) P — 2, Q — 1, R — 3, S — 4
(B) P — 1, Q — 3, R — 2, S — 4
(C) P — 1, Q — 2, R — 3, S — 4
(D) P — 3, Q — 2, R — 1, S — 4

Ответ: (с)
Объяснение: Трюк: Здесь мы видим на всех приведенных рисунках, что второе состояние имеет цикл над входными алфавитами. В таких случаях мы должны разрешить цикл в этом состоянии и преобразовать NFA в более простой, чтобы получить регулярное выражение для NFA.
Для разрешения цикла сначала достигните состояния, в котором должен быть разрешен цикл, затем нарисуйте все циклы над этим состоянием и все возможные перемещения, чтобы перейти в конечное состояние.

Figure P: (when loop resolved at middle state)

Цикл в среднем состоянии либо на 00, либо на 01 * 1.

Отсюда регулярное выражение: € + 0 (00 + 01 * 1) * 01 *

Figure Q: (when loop resolved at middle state)

Цикл в среднем состоянии либо на 00, либо на 10 * 1.

Отсюда и регулярное выражение: € + 0 (00 + 10 * 1) * 0.

Figure R: (when loop resolved at middle state)

Петля в среднем состоянии либо на 10, либо на 10 * 1.

Отсюда регулярное выражение: € + 0 (10 + 10 * 1) * 1.

Figure S: (when loop resolved at middle state)

Петля в среднем состоянии либо на 10, либо на 10 * 1.

Отсюда и регулярное выражение: € + 0 (10 + 10 * 1) * 10 *.

Сопоставление регулярных выражений с приведенным выше дает подходящее совпадение как P-1, Q-2, R-3, S-4

Это объяснение было внесено Яшикой Арора.

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

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

ВОРОТА | GATE CS 2008 | Вопрос 52

0.00 (0%) 0 votes