Обычные языки закрыты при добавлении?

Конкретно, что я имею в виду под сложением, мы определяем как алфавит . Учитывая регулярные языки и под некоторым алфавитом , смотреть на . $\Sigma_i$ $\{0, 1, 2, ..., i\}$ $A$ $B$ $\Sigma_i$ $A\times B$

Для каждой упорядоченной пары определите «сумму» этой упорядоченной пары как , где и - числа в базе i. Лидирующие 0 игнорируются, поэтому перед каждой принятой строкой. Это означает, что определяется как 0. $(a, b) \in A\times B$ $a+b$ $a$ $b$ $0^*$ $\epsilon$

Язык - это набор строк, представляющих все возможные суммы. $A+B$

До сих пор я знаю:

Это верно в ( ). $\Sigma_1$
Это верно для любых конечных регулярных языков и , потому что любой конечный язык является регулярным, а конечным. $A$ $B$ $A+B$
Язык = ss кратно n в базе b в регулярно для любого . Это означает, что любые языки вида также могут быть добавлены, как , что также является регулярным. Однако есть такие языки, как = ss начинается и заканчивается 1}, который не соответствует этим критериям, поэтому он не описывает все обычные языки. $C_n$ $\{$ $|$ $\}$ $\Sigma_b$ $b >= 1$ $C_n$ $C_i+C_j=C_{i + j}$ $D$ $\{$ $|$

automata-theory Phylliida
источник

Неверно, что если A является регулярным в базе 2, оно также является регулярным в базе 3, рассмотрим, например, степени 2.

domotorp

Понятно, ты прав. Я отредактировал вопрос соответственно. Я пытался доказать это, и это казалось правдой, а потом я неправильно понял, что такое гомоморфизм, и предположил, что это правда. Но это не так, извините за это. Если язык регулярен в базе b ^ a для некоторого a> 1, то он также регулярен в любой другой базе b ^ (ac) для любого 1 <= c <a. (так, например, если язык является базовым в базе 8, он также является регулярным в базе 4 и 2, просто имитируя базовый dfa 8).

Phylliida

«Это означает, что ϵ определяется как 0». Я не понимаю, что это значит. Если 0 и ϵ одинаковы, то все 0 можно удалить, и интерпретация чисел больше не работает.

Бабу

Дело в том, что если пустая строка ϵ находится в упорядоченной паре, она добавляет 0 к другой строке. Также для любой заданной строки, которая имеет ведущие 0, они могут быть удалены. Это означает, что 000101 такой же, как 101, например. Это то , что я имел в виду, если а £ появляется в строке сама по себе , чем это эквивалентно стоимости по отношению к сумме , как 0, или 00, или 000 сами по себе . Если эти строки находятся в другой строке, все ставки отключены, и эта замена больше не действительна.

Phylliida

Ответы:

Да.

Сначала рассмотрим алфавит , символы которого представляют собой тройки цифр (сложенных друг над другом в стопку из трех цифр). Над этим алфавитом мы можем определить обычный язык где строка, образованная самой верхней из трех цифр, принадлежит , обычный язык где строка, образованная серединой трех цифр, принадлежит , и обычный язык где две верхние строки суммируются с нижней. и просто используют модифицированные автоматы для и , а $\Sigma_i^3$ $A'$ $A$ $B'$ $B$ $C$ $A'$ $B'$ $A$ $B$ $C$ использует тот факт, что вы можете делать сложение, сканируя справа налево, сохраняя только одну цифру переноса в качестве состояния.

$A'\cap B'\cap C$ $A$ $B$

Дэвид Эппштейн
источник

Это действительно круто. Я не понимал, что вы можете использовать эти стеки таким образом. Спасибо!

Phylliida

По общему признанию это немного сомнительно, потому что в этом случае он содержит только суммы строк одинакового размера, однако, потому что мы можем «смоделировать» суммы строк разных размеров, добавляя нули слева, и просто изменить dfa в другая dfa, которая распознает 0 * перед всеми принимающими строками (когда вы создаете суммирующую dfa для распознавания C с гомоморфизмом).

Phylliida

Я предполагаю, что самый большой ключ в том, что A и B должны быть «технически модифицированы» таким же образом, чтобы быть 0 * A и 0 * B, и как только мы сделаем это, достаточно для каждой пары a и b найти сумма 0 * a + 0 * b st. Оба значения имеют достаточные начальные 0, чтобы соответствовать размерам, и затем результат может быть удален из 0 по мере необходимости, поскольку C изменяется таким же образом. Это подразумевалось, или есть более простой способ посмотреть на то, что мне не хватает?

Phylliida

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

Дэвид Эппштейн

Круто, это имеет смысл.

Phylliida

$A$ $B$ $M_A$ $M_B$ $a$ $b$ $M_A$ $M_B$ $M_A$ $M_B$

domotorp
источник