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