Можно ли решить, является ли язык, описываемый числом случаев, регулярным?

14

Известно, что язык слов, содержащих одинаковые числа 0 и 1, не является регулярным, а язык слов, содержащих одинаковые числа 001 и 100, является регулярным ( см. Здесь ).

Учитывая два слова , разрешимо ли, если язык слов, содержащий равное количество и является регулярным?w1,w2w1w2

sdcvvc
источник
Можете ли вы привести другие примеры определенных языков, кроме и или и ? Как насчет примера с алфавитом из 3 символов? 1i001i0i110i
Бабу
Если является строгим подсловом , есть большая вероятность, что язык пустой, поэтому регулярный. Я не знаю других примеров. Вт 2w1w2
sdcvvc
Я подозреваю, что приведенные выше примеры являются единственными, что делает проблему разрешимой. Если вы укажете только две подстроки, я бы предположил, что это CF ... в зависимости от того, что вы можете указать в отношении случаев. Вы не достаточно точно определили, что вы подразумеваете под «описанным числом случаев».
Бабу
Тело вопроса достаточно точное ИМО.
sdcvvc
1
решения для особых случаев, похоже, основаны на идее, что вхождения подстрок гарантируют только единичные вхождения промежуточного w 2 . так что если предположить, что текущие ответы верны [пока мне не ясно], то, кажется, существует некоторая связь между w 1 , w 2, которая гарантирует в середине сканирования строки, что можно находиться в состоянии «равно» или «неравно» ", но только с максимальным конечным числом для" неравного "случая. w1w2w1w2
vzn

Ответы:

3

Даны ли два слова , w 2 , разрешимо ли, если язык L слов, содержащих одинаковое количество w 1 и w 2 , регулярен?w1w2Lw1w2

Сначала некоторые определения:
они могут быть сделаны более краткими, и примечания могут быть улучшены, если они будут использоваться в доказательствах. Это только первый черновик.

Учитывая два слова и w 2 , мы говорим, что: w1w2

  • всегда происходитс w 2 , отмечается w 1w 2 , если w1 w2w1w2

    1. для любой строки такой, что s = x w 2 y с x ,ss=xw2y и | х | 0 , | х | 1 | , | у | 0 , | у | 1 | 1 существует другое разложение s = x w 1 y . Примечание: условие, что х и уx,y ≥∣w1+w2|x|0,|x|1|,|y|0,|y|1|1s=xw1y
      xyкаждый из них содержит как минимум 0 и 1 требуется в патологическом случае (найденном @sdcvvc): , w 2 = v 1 i + j и y 1 и его симметричные варианты.w1=1i0w2=v1i+jy1
    2. есть строка с x ,s=xw2y , что существует не более одного разложения s = x w 1 y x,y ≥∣w1+w2s=xw1y
  • всегда взаимодействуетс w 2 , отмечается w 1w1 w2 , если каждый из них всегда встречается с другим,w1w2

  • и ш 2 происходит независимо другдруга, отмечено ш 1w1w2 , если ни один не всегда встречается с другим,w1w2

  • всегда встречается m раз или больше,чем w 2 , отмечается w 1 w m w 2 , если для любой строки s такой, что s = x w 2 y сx , y | w 1+ w 2 существует m других разложений s = x i w 1 y iw1 mw2w1mw2ss=xw2yx, y| ≥∣w1+w2ms=xiw1yiдля такой, что из i j следует x ix j .i[1,m]ijxixj

Эти определения построены так, что мы можем игнорировать то, что происходит на концах строки, где должны присутствовать и w 2 . Граничные эффекты в конце строки должны анализироваться отдельно, но они представляют конечное число случаев (на самом деле я думаю, что я забыл один или два таких граничных подслуча в моем первом анализе ниже, но это не имеет большого значения). Определения совместимы с перекрытием случаев.w1w2

Необходимо рассмотреть 4 основных случая (игнорируя симметрию между и w 2 ):w1w2

  1. Оба слова обязательно встречаются вместе, за исключением, возможно, на концах строки. Это касается только пар вида 1 i 0 и 01 i или 0 i 1 и 10 i . Это легко распознаетсяконечным автоматом,который только проверяет наличие одиночных вхождений на обоих концах строки, которая должна быть распознана, чтобы убедиться, что в обоих концах или ни на одном конце нет ни одного случая. Существует также вырожденный случай, когда w 1 = w 2 : тогда язык L, очевидно, регулярен.w1w2
    1i001i0i110iw1=w2

  2. , но не w 2w 1 Одно из двух слов не может встречаться без другого, но обратное неверно (за исключением, возможно, в конце строки). Это происходит, когда:w1w2w2w1

    • является подстрокой w 2 : тогда конечный автомат может просто проверить, что w 1 не встречается вне экземпляра w 2 .w1w2w1w2

    • и w 2 = v 1 j для некоторого слова v { 0 , 1 } , v 01 i : тогда конечный автомат проверяет, как в предыдущем случае, что w 1 не встречается отдельно от w 2 , Однако автомат позволяет считать один дополнительный экземпляр w 1 , который позволит принять, если w 2w1=1i0w2=v1jv{0,1}v01iw1w2w1w2это суффикс строки. Есть три других симметричных случая (симметрия 1-0 и симметрия слева-справа).

  3. Одно из двух слов встречается дважды в другом. Это может быть распознано конечной автоматизацией, которая проверяет, что меньшее слово никогда не встречается в строке. Это также немного более сложный вариант, который объединяет два варианта случая 2. В этом случае автомат проверяет, что меньшая строка 1 i 0 никогда не встречается, за исключением, возможно, как часть v в большей v 1 j, которая появляется как суффикс строки (и 3 других случая по симметрии).w12w2
    1i0vv1j

  4. 2 слова могут встречаться независимо друг от друга. Мы создаем обобщенную последовательную машину (gsm) G, которая выводит a, когда распознает вхождение w 1 и b при распознавании вхождения w 2 , и забывает все остальное. Язык L регулярен, только если язык G ( L ) регулярен. Но G ( L ) = { w { a , b } w aw1w2
    Gaw1bw2LG(L) который явно не зависит от контекста и не является регулярным. Следовательно, L не является регулярным. На самом деле мы имеем L = G - 1 ( G ( L ) ) . Так как обычные языки и языки без контекста закрыты при отображении gsm и обратном отображении gsm, мы также знаем, что L не зависит от контекста.G(L)={w{a,b} wa=∣wb}L
    L=G1(G(L))L

Один из способов организовать формальное доказательство может быть следующим. Сначала создайте КПК, который распознает язык. На самом деле это можно сделать на машине с 1 счетчиком, но проще иметь два символа стека, чтобы избежать дублирования конечного элемента управления. Затем для случаев, когда это должен быть FA, покажите, что счетчик может быть ограничен константой, которая зависит только от двух слов. Для остальных случаев покажите, что счетчик может достигать любого произвольного значения. Конечно, КПК должен быть организован так, чтобы доказательства были достаточно легкими для переноски.

Представление FA как двухпакетных символов PDA, вероятно, является самым простым представлением для него. В нерегулярном случае конечная управляющая часть КПК такая же, как у GSM в приведенном выше наброске проверки. Вместо того , чтобы выводить «ы и б » S , как в GSM, КПК подсчитывает разницу в количестве с стека.ab

Babou
источник
У меня был вопрос о свободе контекста в случае трех слов. Я удалил его, когда понял, что его можно проанализировать аналогичным образом. Сначала я подумал, что доказательство отсутствия CFness сделает оригинальное упражнение, но GSM разрушает его.
Бабу
2
Непонятно, что вы подразумеваете под «происходить независимо друг от друга», «обязательно собраться вместе» и т. Д. Вместо этого напишите формальные определения и докажите, что они охватывают все случаи.
sdcvvc
1
Я не уверен, что вы спрашиваете, и какой уровень формализации вам нужен, для какой цели. Я понял, что анализировать возможные отношения двух слов от руки не гарантируется, и все равно не имеет значения. Важно то, может ли вхождение одного слова существовать, не создавая в то же время вхождения (или нескольких) другого слова. Детали не имеют значения, так как они всегда будут локализованы и, таким образом, управляемы конечным образом. Два конца не имеют значения, так как они также локализованы. Даже совпадения случаев не имеют значения, поскольку их может быть только конечное число в 1 месте
babou
1
Я спросил вас о точных определениях терминов, упомянутых в комментарии. Спасибо, что написали их. Я должен был угадать их раньше? В любом случае, вы, кажется, утверждаете, что . Это не удовлетворяет условию 1. определения « w 1 всегда встречается с w 2 », поскольку в s = 0 M 0 i 1 1 M не встречается 1 0 i . 0i110iw1w210is=0M0i11M
sdcvvc
Извините, я не хотел вас догадываться. Мне потребовалось время, чтобы понять, что именно вы хотели. Мой провал только. Что касается вашего встречного примера, вы правы. Но для меня это только означает, что я должен быть немного более осторожным с теломерами, в определении отношений. Я определил их слишком быстро, но или 1 М не дают много информации в этом контексте. Это действительно пограничный патологический пример в патологическом случае, который на самом деле не может иметь место, если используется более 2 символов. Я просто не верю, что это что-то меняет. 0M1M
Бабу