Является ли язык слов, содержащих одинаковые числа 001 и 100, регулярным?

Мне было интересно, когда языки, которые содержат одинаковое количество экземпляров двух подстрок, будут регулярными. Я знаю, что язык, содержащий равное количество единиц и нулей, не является регулярным, но является языком, таким как , где = число экземпляров подстроки "001" равно числу экземпляров подстроки " 100 " обычный? Обратите внимание, что строка «00100» будет принята. $L$ $L$ $\{ w \mid$ $\}$

Моя интуиция говорит мне, что это не так, но я не могу доказать это; Я не могу превратить его в форму, которую можно прокачать через лемму прокачки, так как я могу это доказать? С другой стороны, я пытался создать DFA, NFA или регулярное выражение и потерпел неудачу на этих фронтах, так что же мне делать дальше? Я хотел бы понять это в целом, а не только для предлагаемого языка.

formal-languages regular-languages pumping-lemma Бен Элгар
источник

Вы видели, как доказать, что язык не является регулярным ?

Юхо

Почему вы не можете ответить на собственное решение?

Юваль Фильмус

@YuvalFilmus Пользователи с низкой репутацией задерживаются, чтобы ответить на свой вопрос (8 часов, если респ <100).

Жиль "ТАК - перестань быть злым"

0

$0$

q 5

$q5$

01

$01$

10

$10$

Ответы:

Ответ извлечен из вопроса.

Как указывает Хендрик Ян, в q5 должна быть дополнительная нулевая петля.

автомат

Юхо
источник

это конструкция, а не доказательство

vzn

в классах CS для простых задач иногда даются только DFA, но это не доказывает, что он точно принимает язык. Вы должны [как-то] показать для каждой входной строки, что она работает правильно. "как это работает?"

vzn

q_{5}

$q_5$

q_{2}

$q_2$

Это вопрос с подвохом. Попробуйте создать строку, которая содержит два 001 и не содержит 100, и посмотрите, почему вы не можете это сделать. Если X = «число 001» и Y = «число 100», то X = Y или X = Y ± 1.

Как только вы поймете хитрость, очень маловероятно, что язык будет неправильным, и тогда создание DFA будет довольно простым. Есть только 8 состояний с их переходами, если следующий символ 0/1:

State S0: Input is empty. -> S1/C0

State S1: Input is 0. -> C2/C0

State A: Y = X + 1, input ends in 00. -> A/C0

State B0: X = Y + 1, input ends in 1. -> B1/B0

State B1: X = Y + 1, input ends in 10. -> C2/B0

State C0: X = Y, input ends in 1. -> C1/C0

State C1: X = Y, input ends in 10. -> A/C0

State C2: X = Y, input ends in 00. -> C2/B0

Начальное состояние - S0, а S0, S1, C0, C1, C2 - принимающие состояния.

gnasher729
источник