2001-gre-vs-practice.pdf/Q50 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 1: Строка 1:
{{reserve-task|[[Участник:Илья52|илья52]] 19:05, 22 декабря 2024 (UTC)}}
+
Пусть <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> - набор строк в <m>\{0,1\}^{*}</m>, таких, что <m>x \in L</m>, тогда и только тогда, когда количество нулей в <m>x</m> делится на <m>k</m>, а число единиц в <m>x</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>.
{{checkme|[[Участник:Илья52|илья52]] 10:37, 7 января 2025 (UTC)}}
 
{{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»

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

Количестов единиц должно быть нечетным, для отслеживания четности, количества увиденных единиц, потребуется состояния:

Состояния в автомате, распознающим язык будут представлены парами . Количество всевозможных пар равно .