Czy dodawanie zwykłych języków jest zamknięte?

W szczególności rozumiem przez dodanie, że to alfabet . Podane języki regularne i pod jakimś alfabetu , spojrzenie na . $\Sigma_i$ $\{0, 1, 2, ..., i\}$ $A$ $B$ $\Sigma_i$ $A\times B$

Dla każdej uporządkowanej pary zdefiniuj „sumę” tej uporządkowanej pary jako , gdzie i są liczbami w podstawie i. Wiodące zera są ignorowane, więc znajduje się przed każdym zaakceptowanym ciągiem. Oznacza to, że jest zdefiniowany jako 0. $(a, b) \in A\times B$ $a+b$ $a$ $b$ $0^*$ $\epsilon$

Język to zbiór ciągów reprezentujących wszystkie takie możliwe sumy. $A+B$

Jak dotąd wiem:

Tak jest w przypadku unary ( ). $\Sigma_1$
Dotyczy to każdego skończonego języka regularnego i , ponieważ każdy język skończony jest regularny, a jest skończony. $A$ $B$ $A+B$
Język = ss jest wielokrotnością n w bazie b pod jest regularna dla dowolnego . Oznacza to, że można również dodawać dowolne języki w postaci , ponieważ , co również jest normalne. Istnieją jednak języki takie jak = ss zaczyna się i kończy na 1}, który nie spełnia tych kryteriów, więc nie opisuje wszystkich zwykłych języków. $C_n$ $\{$ $|$ $\}$ $\Sigma_b$ $b >= 1$ $C_n$ $C_i+C_j=C_{i + j}$ $D$ $\{$ $|$

automata-theory Phylliida
źródło

Nie jest prawdą, że jeśli A jest regularne w bazie 2, to również jest regularne w bazie 3, rozważ np.

Potęgi

Rozumiem, masz rację. Zredagowałem to pytanie odpowiednio. Próbowałem to udowodnić i wydawało się to prawdą, a potem źle zrozumiałem, czym był homomorfizm, i założyłem, że to prawda. Ale nie, przepraszam za to. Jeśli język jest regularny w bazie b ^ a dla niektórych a> 1, jest on również regularny w dowolnej innej bazie b ^ (ac) dla dowolnego 1 <= c <a. (więc na przykład, jeśli język jest regularny w bazie 8, jest on również regularny w bazie 4 i 2, po prostu symulując dfa base-8).

Phylliida,

„Oznacza to, że ϵ jest zdefiniowane jako 0”. Nie rozumiem co to znaczy. Jeśli 0 i ϵ są takie same, wszystkie zera można usunąć, a interpretacja liczb nie działa.

babou

Chodzi o to, że jeśli pusty ciąg ϵ jest w uporządkowanej parze, dodaje 0 do drugiego ciągu. Również dla dowolnego ciągu, który ma wiodące zera, można je usunąć. Oznacza to, że 000101 jest na przykład taki sam jak 101. To właśnie miałem na myśli, jeśli ε pojawia się w sznurku przez siebie , niż jest to równoważne pod względem wartości w stosunku do sumy jako 0 lub 00, lub 000 przez siebie . Jeśli te struny znajdują się w innym ciągu, wszystkie zakłady są jednak wyłączone, a ta zamiana nie jest już ważna.

Phylliida,

Odpowiedzi:

Tak, oni są.

Najpierw rozważmy alfabet którego symbolami są trzy cyfry (ułożone jedna nad drugą w stos trzech cyfr). Na podstawie tego alfabetu możemy zdefiniować zwykły język którym ciąg utworzony przez najwyższą z trzech cyfr należy do , zwykły język którym ciąg utworzony przez środek trzech cyfr należy do , i zwykły język gdzie dwa górne ciągi sumują się z dolnym. i używają tylko zmodyfikowanych automatów dla i , podczas gdy $\Sigma_i^3$ $A'$ $A$ $B'$ $B$ $C$ $A'$ $B'$ $A$ $B$ $C$ wykorzystuje fakt, że można dodawać, skanując od prawej do lewej, zachowując tylko jedną cyfrę przeniesienia jako stan.

Zatem jest (przez zamknięcie pod skrzyżowaniem) zwykłym językiem, który rozpoznaje stosy trzech ciągów, jeden w , jeden w i trzeci w sumie. Homomorfizm, który usuwa dwie górne cyfry ze stosu, pozostawiając tylko dolną, przenosi je do żądanego języka, a wynik jest zamykany pod homomorfizmem. $A'\cap B'\cap C$ $A$ $B$

David Eppstein
źródło

To naprawdę niesamowite. Nie zdawałem sobie sprawy, że możesz wykorzystać te stosy w ten sposób. Dzięki!

Phylliida,

Trzeba przyznać, że jest to trochę niepewne, ponieważ w tym przypadku zawiera tylko sumy łańcuchów o tym samym rozmiarze, ponieważ możemy „symulować” sumy łańcuchów o różnych rozmiarach, dodając zera po lewej stronie i łatwo zmodyfikować dfa w inna dfa, która rozpoznaje 0 * przed wszystkimi ciągami akceptującymi (po zbudowaniu sumującej dfa do rozpoznawania C z homomorfizmem).

Phylliida,

Przypuszczam, że największym kluczem jest to, że A i B muszą być „technicznie zmodyfikowane” w taki sam sposób, aby były 0 * A i 0 * B, a gdy to zrobimy, wystarczy, aby dla każdej pary a i b znaleźć suma 0 * a + 0 * b st obie wartości mają wystarczającą liczbę zer wiodących, aby dopasować rozmiary, a następnie wynik można usunąć zera w razie potrzeby, ponieważ C jest modyfikowany w ten sam sposób. Czy to sugerowało, czy jest prostszy sposób, aby spojrzeć na to, czego mi brakuje?

Phylliida,

Tak, są pewne szczegóły techniczne dotyczące wypełniania, ale tak naprawdę nie zmieniają podstawowych pomysłów, więc je pominąłem.

David Eppstein

Fajnie, to ma sens.

Phylliida,

Tak. Daję NFA, który odczytuje słowo od końca, ponieważ nawet takie automaty potrafią rozpoznać tylko zwykłe języki. Przypuszczamy również, że i są podane przez takie automaty, i . NFA domysły na każdym kroku, co dana cyfra i jest czeki, że dodatek jest poprawna, i oblicza nowe poszczególne stany i . Na końcu słowa akceptuje, jeśli i tylko wtedy, gdy zarówno jak i akceptują. $A$ $B$ $M_A$ $M_B$ $a$ $b$ $M_A$ $M_B$ $M_A$ $M_B$

domotorp
źródło