Język wartości funkcji afinicznej

Napisz $\bar n$ dla dziesiętnego rozszerzenia $n$ (bez wiodącego 0). Niech $a$ i $b$ będą liczbami całkowitymi o $a > 0$ . Rozważmy język rozwinięć dziesiętnych wielokrotności plus stałej:$a$

Czy $M$ regularne? bez kontekstu?

(Kontrast z językiem wykresu funkcji afinicznej )

_{Myślę, że byłoby to dobre pytanie o pracę domową, więc odpowiedzi, które zaczynają się od podpowiedzi lub dwóch i wyjaśniają nie tylko, jak rozwiązać pytanie, ale także jak zdecydować, jakie techniki zastosować.}

Bardzo proste: załóżmy, że liczby są zapisywane dziesiętnie (inne podstawy są obsługiwane przez trywialną modyfikację). Budowanie DFA z stanach 0, 1, ..., - 1 . Stan początkowy to 0, a od stanu q na wejściu cyfra d przechodzi do stanu ( 10 q + d ) mod a . Stanem akceptacji jest b mod a (może potrzebować poprawki, jeśli b > a ).$a$$a - 1$$q$$d$$(10 q + d) \bmod a$$b \bmod a$$b > a$

To jest normalne. Pierwsze prace Spójrzmy prawdzie w systemie binarnym, który będzie uogólnić do jakiejkolwiek podstawy> 1. Niech być dany język. Dla a = 1, b = 0 otrzymujemy$M_{a,b}$

$M_{1,0} = \{1, 10, 11, 100, 101, ...\}$

który zawiera wszystkie łańcuchy powyżej bez wiodących zer, który jest regularny (konstruuj dla niego wyrażenie regularne).$\{0,1\}$

Teraz dla każdego , b z jeszcze 0 otrzymujemy M a , 0 z M 1 , 0 , mnożąc przez numerycznie, czyli wykonując transformację ˉ x → ¯ x na każdy ciąg M a , 0 . Można to zrobić bitowo przez sekwencję przesunięć i dodatków x, które zależą od bitów ustalonego ciągu ˉ a . Dwie potrzebne nam transformacje to:$a$$M_{a,0}$$M_{1,0}$$\bar x \rightarrow \overline {ax}$$M_{a,0}$$x$$\bar a$

który ˉ x → ˉ x$\bar x \rightarrow \overline {2x}$$\bar x \rightarrow \bar x0$

i

$\bar x \rightarrow \overline {2x+x}$

Łączenie 0 po prawej stronie wyraźnie zachowuje regularność. Musimy zatem tylko udowodnić, że druga operacja zachowuje prawidłowość. Sposobem na to jest o skończonej stan pracy przetwornika na od prawej do lewej. To najtrudniejszy krok. Sugeruję robienie tego za pomocą programu pseudokodowego i pewnej skończonej pamięci pomocniczej (jak niektóre zmienne bitowe) zamiast używania stanów. Tak długo, jak pamięć ma stały rozmiar na wszystkich wejściach i skanujesz ściśle od prawej do lewej, jest to transdukcja stanu skończonego i zachowuje regularność.$\bar x$

Na koniec, aby dostać od M a , 0 musimy numerycznie dodać B do każdej struny, ale to się robi z podobnym przetwornik T b , która zależy od ustalonej liczby b.$M_{a,b}$$M_{a,0}$$b$$T_b$

Aby zrobić to samo w dowolnej bazie, pokaż dodatkowo, jak wykonać mnożenie przez pojedynczą cyfrę w tej bazie, używając przetwornika S d, który zależy od d. Dzięki temu możemy pomnożyć liczby wielocyfrowe i nadal pozostać w zwykłych językach. Lub możemy to wyrafinować, mówiąc, że mnożenie przez d jest po prostu powtarzanym dodawaniem.$d$$S_d$$d$

Chciałeś tylko podpowiedzi. Każdy z tych kroków zależy od dość złożonego twierdzenia / techniki, więc udowodnienie, że uzyskanie pełnego dowodu będzie dodatkową pracą.

Wskazówka 1 : najpierw rozwiąż bardziej popularny problem „napisz automat rozpoznający dziesiętne / binarne reprezentacje liczb podzielnych przez 3”, gdy najpierw pojawi się bit najmniej znaczący .

Pytanie pośrednie: udowodnij, że jest regularne.$\{ \overline{a\,x+b}\mid a\,x+b≥0 \quad x\in\mathbb{Z}\}$

Wskazówka 2 : Wykres funkcji $(n \mapsto 10n+d)$ „modulo ” jest skończony. Możesz to obliczyć dla każdego d w { 0 , … , 9 }, który jest zarówno zbiorem cyfr, jak i językiem twojego automatu.$a$$d$$\{0, \dots, 9\}$

Podpowiedź 3 : teraz wymienić z x ∈ N . Co to zmienia? Spróbuj wykorzystać fakt, że zwykłe języki są stabilne przez skrzyżowanie zamiast budować automat ad-hoc .$x∈\mathbb Z$$x∈\mathbb N$

Wskazówka 4 : teraz załóż, że $a$ jest liczbą pierwszą (tak, że to pole) i że nadal jesteśmy w przypadku, gdy x ∈ Z . Teraz używamy reprezentacji, w której pierwszy bit jest najbardziej znaczący . Czy możesz zbudować automat w ten sam sposób?$\mathbb Z/a\mathbb Z$$x∈\mathbb Z$

Wskazówka 5 : nie zawsze musisz zbudować automat, aby udowodnić, że język jest prawidłowy. Jak wykorzystać poprzednie wyniki, aby udowodnić, że jest regularny? (z najważniejszym bitem na początku)$M$

Podążam za pomysłem @vonbrand:

Wskazówka 1:

Rozwiąż najpierw dla . Możesz użyć twierdzenia Myhill-Nerode .$b=0$

Definiujemy następującą relację . Jest to oczywiście relacja równoważności. Ponadto jest to zgodne z prawem, ponieważ jeśli dodamy cyfrę d , otrzymamy ˉ x ≈ ˉ $\bar x\approx \bar y :\iff x\equiv y \mod a$$d$. Wreszcie nasycaL, ponieważLjest klasą równoważności[0]. Ponieważ≈ma skończoną liczbę klas według twierdzenia Myhill-Nerode, że jest on regularny. Związane FSA jest minimalny i ma$\bar x \approx \bar y \iff 10x+d \equiv 10y+d \mod a \iff \bar x d \approx \bar y d$$L$$L$$[0]$$\approx$$a$ stanów.

Wskazówka 2:

Rozwiąż ogólny przypadek, użyj ponownie automatu wywołanego przez przypadek .$b=0$

Wiemy, że język jest regularny dla . Stąd po prostu wziąć stan FSA M dla b = 0 języka. Teraz budujemy FSA dla L . Załóżmy, że b ma k cyfr. Następnie FSA rozgałęzia się jak 10-ary drzewo o głębokości k i zawiera wszystkie ścieżki do liczb z k cyfr. Wszystkie stany, które można osiągnąć za pomocą liczby innej niż x + b, odrzucają inaczej. Na koniec łączymy drzewną część FSA z automatem $b=0$$a$$M$$b=0$$L$$b$$k$$k$$k$$ax+b$$M$, zgodnie z pozostałą częścią przez podział przez .$a$

Język jest regularny.

Wskazówka: wyrzuć dziewiątki

Dowód na pomysł

Dla i b < 9 ,$a=9$$b < 9$

zbuduj automat z stanami oznaczonymi od 0 do 8 . 0 to stan początkowy, a jeden stan końcowy to b . Ze stanu s na cyfrze d przejście do stanu ( s $9$$0$$8$$0$$b$$s$$d$$(s + d) \;\mathrm{mod}\; 9$.

To handle other values of $a$ that are coprime with $10$,

group digits in packets to find some $k$ such that $a$ divides $10^k-1$ (e.g. take $k=3$ if $a=37$ because $999 = 27 \times 37$).

To handle values of $a$ whose only prime factors are $2$ and $5$,

note that it's all about a finite number of digits at the end.

To generalize to all values of $a$ and $b$,

use the fact that union and intersection of regular languages are regular, that finite languages are regular, and that the multiples of $a_1 \cdot a_2$ are exactly the multiples of both when $a_1$ and $a_2$ are coprime.

Note that we use whichever technique is convenient; the three main elementary techniques (regular expressions, finite automata, set-theoretic properties) are all represented in this proof.

Detailed proof

Let $a = 2^p 5^q a'$ with $a'$ coprime with $10$. Let $M' = \{\overline{a'\,x+b} \mid x\in\mathbb{Z} \wedge a'\,x+b \ge 0\}$ and $M'' = \{\overline{2^p 5^q\,x+b} \mid x\in\mathbb{Z} \wedge 2^p 5^q\,x+b \ge 0\}$. By elementary arithmetic, the numbers equal to $b$ modulo $a$ are exactly the numbers equal to $b$ modulo $a'$ and to $b$ modulo $2^p5^q$, so $M \cap \{\overline{x} \mid x \ge b\} = M' \cap M'' \cap \{\overline{x} \mid x \ge b\}$. Since the intersection of regular languages is regular, and $\{\overline{x} \mid x \ge b\}$ is regular because it is the complement of a finite (hence regular) language, if $M'$ and $M''$ are also regular, then $M \cap \{\overline{x} \mid x \ge b\}$ is regular; and $M$ is therefore regular since it is the union of that language with a finite set. So to conclude the proof it suffices to prove that $M'$ and $M''$ are regular.

Let us start with $M''$, i.e. numbers modulo $2^p 5^q$. The integers whose decimal expansion is in $M''$ are characterized by their last $\mathrm{max}(p,q)$ digits, since changing digits further left means adding a multiple of $10^{\mathrm{max}(p,q)}$ which is a multiple of $2^p 5^q$. Hence $0^* M'' = \aleph^* F$ where $\aleph$ is the alphabet of all digits and $F$ is a finite set of words of length $\mathrm{max}(p,q)$, and $M'' = (\aleph^* F) \cap ((\aleph \setminus \{0\}) \aleph^*)$ is a regular language.

We now turn to $M'$, i.e. numbers modulo $a'$ where $a'$ is coprime with $10$. If $a' = 1$ then $M'$ is the set of decimal expansions of all naturals, i.e. $M' = \{0\} \cup ((\aleph \setminus \{0\}) \aleph^*)$, which is a regular language. We now assume $a' > 1$. Let $k = a'-1$. By Fermat's little theorem, $10^{a'-1} \equiv 1 \mod a'$, which is to say that $a'$ divides $10^k-1$. We build a deterministic finite automaton that will recognize $0^* M'$ as follows:

• The states are $[0,k-1] \times [0,10^k-2]$. The first part represents a digit position and the second part represents a number modulo $10^k-1$.
• The initial state is $(0,0)$.
• There is a transition labeled $d$ from $(i,u)$ to $(j,v)$ iff $v \equiv d 10^i + u \mod 10^k-1$ and $j \equiv i + 1 \mod k$.
• A state $(i,u)$ is final iff $u \equiv b \mod a'$ (note that $a'$ divides $10^k-1$).

The state $(i,u)$ reached from a word $\overline{x}$ satisfies $i \equiv |\overline{x}| \mod k$ and $u \equiv x \mod 10^k-1$. This can be proved by induction over the word, following the transitions on the automaton; the transitions are calculated for this, using the fact that $10^k \equiv 1 \mod 10^k-1$. Thus the automaton recognizes the decimal expansions (allowing initial zeroes) of the numbers of the form $u + y 10^k$ with $u \equiv b \mod a'$; since $10^k \equiv 1 \mod a'$, the automaton recognizes the decimal expansions of the numbers equal to $b$ modulo $a'$ allowing initial zeroes, which is $0^* M'$. This language is thus proved regular. Finally, $M' = (0^* M') \cap ((\aleph \setminus \{0\}) \aleph^*)$ is a regular language.

To generalize to bases other than $10$, replace $2$ and $5$ above by all the prime factors of the base.

Formal proof

Left as an exercise for the reader, in your favorite theorem prover.