2001-gre-vs-practice.pdf/Q50 — различия между версиями
Илья52 (обсуждение | вклад) |
Илья52 (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
Количестов единиц должно быть нечетным, для отслеживания четности, количества увиденных единиц, потребуется <m>2</m> состояния: <m>p_0, p_1</m> | Количестов единиц должно быть нечетным, для отслеживания четности, количества увиденных единиц, потребуется <m>2</m> состояния: <m>p_0, p_1</m> | ||
| − | Состояния в автомате, распознающим язык <m>L</m> будут представлены парами <m> | + | Состояния в автомате, распознающим язык <m>L</m> будут представлены парами <m>(q_i,p_j)</m>. Количество всевозможных пар равно <m>2k</m>. |
{{question-ok|}} | {{question-ok|}} | ||
[[Категория:Надо не забыть выбрать тему]] | [[Категория:Надо не забыть выбрать тему]] | ||
Версия 10:36, 7 января 2025
Задача зарезервирована: илья52 19:05, 22 декабря 2024 (UTC)
Пусть . Пусть - набор строк в , таких, что , тогда и только тогда, когда количество нулей в делится на , а число единиц в нечетно. Чему равно минимальное число состояний в детерминированном конечном автомате (DFA), который распознает язык ?
Ответы
- Правильный ответ:
- 2^k
Объяснение
Исходники — вопрос 50 на 38 странице книги «2001-gre-vs-practice.pdf»
Количество нулей должно делиться на . Для этого нам потребуется состояний, чтобы отслеживать остаток от деления количества нулей на : , где состояние соответствует тому, что мы увидели нулей по модулю .
Количестов единиц должно быть нечетным, для отслеживания четности, количества увиденных единиц, потребуется состояния:
Состояния в автомате, распознающим язык будут представлены парами . Количество всевозможных пар равно .