2001-gre-vs-practice.pdf/Q50 — различия между версиями
Материал из DISCOPAL
Илья52 (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
− | + | Пусть <m>k \geq 2</m>. Пусть <m>L</m> — набор строк в <m>\{0,1\}^{*}</m>, таких, что <m>x \in L</m>, тогда и только тогда, когда количество нулей в <m>x</m> делится на <m>k</m>, а число единиц в <m>x</m> нечетно. Чему равно минимальное число состояний в детерминированном конечном | |
− | + | ||
− | Пусть <m>k \geq 2</m>. Пусть <m>L</m> | + | |
автомате (DFA), который распознает язык <m>L</m>? | автомате (DFA), который распознает язык <m>L</m>? | ||
Строка 19: | Строка 17: | ||
Состояния в автомате, распознающим язык <m>L</m> будут представлены парами <m>(q_i,p_j)</m>. Количество всевозможных пар равно <m>2k</m>. | Состояния в автомате, распознающим язык <m>L</m> будут представлены парами <m>(q_i,p_j)</m>. Количество всевозможных пар равно <m>2k</m>. | ||
− | |||
− | |||
− | [[Категория: | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 14:49, 7 января 2025 (UTC)}} |
+ | |||
+ | [[Категория:Формальные языки]] |
Текущая версия на 14:49, 7 января 2025
Пусть . Пусть — набор строк в , таких, что , тогда и только тогда, когда количество нулей в делится на , а число единиц в нечетно. Чему равно минимальное число состояний в детерминированном конечном автомате (DFA), который распознает язык ?
Ответы
- Правильный ответ:
- 2^k
Объяснение
Исходники — вопрос 50 на 38 странице книги «2001-gre-vs-practice.pdf»
Количество нулей должно делиться на . Для этого нам потребуется состояний, чтобы отслеживать остаток от деления количества нулей на : , где состояние соответствует тому, что мы увидели нулей по модулю .
Количестов единиц должно быть нечетным, для отслеживания четности, количества увиденных единиц, потребуется состояния:
Состояния в автомате, распознающим язык будут представлены парами . Количество всевозможных пар равно .