Pracuję nad zestawem problemów dla klasy i pomyślałem o pytaniu związanym z tym, nad czym pracowałem. Czy istnieje minimalna liczba stanów, które musi mieć automat skończony, aby zaakceptować ciągi binarne reprezentujące liczby podzielne przez liczbę całkowitą n? We wcześniejszym zestawie problemów udało mi się zbudować DFA, który akceptuje łańcuchy binarne podzielne przez 3 z 3 stanami. Czy to przypadek, czy może jest coś nieodłącznego od ogólnego problemu wykrywania ciągów podzielnych przez n, co sugeruje minimalną liczbę stanów?
Obiecuję, że to nie odpowie na pytanie dotyczące pracy domowej! :)
3
Witamy w cstheory, witrynie pytań i odpowiedzi na pytania na poziomie badawczym w teoretycznej informatyce (TCS). Twoje pytanie nie wydaje się być pytaniem na poziomie badawczym w TCS. Zapoznaj się z często zadawanymi pytaniami, aby uzyskać więcej informacji o tym, co to oznacza, oraz sugestie dotyczące witryn, które mogą przyjąć Twoje pytanie. Na koniec, jeśli twoje pytanie jest zamknięte z powodu braku zakresu i uważasz, że możesz je edytować, aby stało się pytaniem na poziomie badawczym, możesz to zrobić. Zamknięcie nie jest trwałe i pytania można ponownie otworzyć, sprawdź FAQ w celu uzyskania dalszych informacji.
—
Kaveh
@Kaveh: Myślę, że pytanie jest w porządku, zwłaszcza biorąc pod uwagę zwięzłą odpowiedź Davida.
—
Huck Bennett
@HuckBennett Zgadzam się z Kavehem, że to pytanie powinno zostać zamknięte w cstheory, głównie w celu zachowania spójności. Zgadzam się jednak z tobą: to zabawne pytanie i kiedy po raz pierwszy zobaczysz DFA, zdecydowanie powinieneś zadać sobie pytanie. Myślę, że OP powinien spróbować się zabawić, wypracowując odpowiedź dla siebie, a następnie skonsultuj się z math.SE, aby uzyskać więcej informacji.
—
Artem Kaznatcheev
To nie jest praca domowa (chociaż jest inspirowana pytaniem do pracy domowej), to ciekawe pytanie, nie sądzę, że jest to dobrze znany wynik, a odpowiedź na to pytanie pojawiła się w czasopiśmie badawczym. Nie rozumiem, dlaczego powinien być zamknięty. Górna granica była praca, i jest rzeczywiście łatwe, ale pytanie było o dolną granicę.
—
Peter Shor
@Janoma: Rzeczywiście. Koniec pytania sugeruje, że OP myli górne granice z dolnymi granicami.
—
Michael Blondin,