Myślę o językach jednoargumentowych , gdzie jest zbiorem wszystkich słów, których długość jest sumą kwadraty. Formalnie:
Łatwo to pokazać nie jest regularny (np. z Pumping-Lemma).
Ponadto wiemy, że każda liczba naturalna jest sumą czterech kwadratów, co implikuje, że dla wszystkie języki są regularne od .
Teraz interesują mnie sprawy i :
, .
Niestety nie jestem w stanie wykazać, czy te języki są prawidłowe, czy nie (nawet przy pomocy twierdzenia Legendre'a o trzech kwadratach lub twierdzenia Fermata o sumach dwóch kwadratów ).
Przynajmniej jestem tego pewien nie jest regularne, ale nieszczęśliwe myślenie nie jest dowodem. Jakaś pomoc?
Odpowiedzi:
ZacznijmyL.2) . Wiadomo, że górna gęstość liczb całkowitych, które są sumą dwóch kwadratów, wynosi 0. IfL.2) były regularne, to ostatecznie będzie okresowe, a zatem, ponieważ jego górna gęstość wynosi 0, skończona. Ale wiemy, że istnieją dowolnie duże liczby całkowiteL.2) , tak że L.2) nie może być regularny.
Jeżeli chodzi oL.3) rozważ słowa wk=14k7 . Twierdzę, że zak < ℓ , słowa wk,wℓ są nierówne. W rzeczy samej,wk14k8∉L.3) podczas wℓ14k7∈L.3) . Kryterium Myhill – Nerode to pokazujeL.3) jest nieregularny.
źródło
PrzypuszczaćL.3) jest regularny. Tak samo jest z jego dopełnieniem, którym jest twierdzenie Legendre'a o trzech kwadratach{zan | n= 4k(8l+7),k,l∈N} . Według twierdzenia Parikha oznaczałoby to, że zbiór długościS={4k(8l+7) | k,l∈N} jest półliniowy, tj. skończony związek ⋃Ni=1Si zbiorów liniowych Si={ai+rbi | r∈N} .
Rozważ dwa elementys1=4k1(8l1+7),s2=4k2(8l2+7)∈S z k1>k2 , i pozwól r:=k1−k2 . Gdybys1,s2 oba są w tym samym Si , to też jest albo 2s1−s2 lub 2s2−s1 (w zależności od tego, czy s1<s2 lub s1>s2 ). Ale
Żadnego z nich nie maS , więc s1,s2 musieliby należeć do różnych członków związku. Ale to niemożliweS jest skończonym związkiem i istnieje nieskończenie wiele różnych k .
W związku z tym,L3 nie jest regularny.
źródło