Пусть L - язык, состоящий из строк над алфавитом {0,1}, которые содержат равное количество 1s и 0s.Показать строки бит с count (1s) = count (0s) не является регулярным
Например:
000111
10010011
10
1010101010
Как вы можете показать, что L не является регулярным языком?
Я думаю, вы можете использовать тот же самый аргумент, который используется для того, чтобы показать, что {0^n 1^n: n> 0} не является регулярным, так как вы можете выбрать строку, которая будет противоречить лемме о перекачке.
Предположим, что L является обычным. Поэтому он должен удовлетворять лемме о перекачке для некоторого целого n (длина накачки). Возьмите шнур S=0^n 1^n, который принадлежит L. Согласно лемме, его можно разбить как S=xyz с |xy| <= n, |y|>0 и x y^i z принадлежащих L, для всех i>=0. Обратите внимание, что y должен состоять только из нулей. Теперь насос y, и вы добавляете только нули в строку, которая больше не принадлежит L. Так что у вас есть противоречие. Поэтому L не является регулярным.
@Kobi: Я думаю, что строка, которую я выбрал, сделает для доказательства. –
Согласно Wikipedia и ссылке rparree, это должно быть | xy | <= n. Из-за этого xy может охватывать только первую половину S = 0^n 1^n, что означает, что y может содержать только нули. –
Я не знаю о формальном доказательстве, но интуиция заключается в том, что вы не можете построить DFA для распознавания этого языка (считайте, что для обеспечения непрерывного количества состояний для отслеживания строк формы 111...111000...000 или аналогичных).
Это не язык {0^n 1^n: n> 0}, цифры могут быть в любом порядке. Как вы можете использовать лемму о перекачке, чтобы показать, что язык, описанный в Q, является нерегулярным? –
@ AndrewTomazos-Fathomling: Но это суб-язык интересующего вас языка. –
И это также подъязыка '0 * 1 *', и это регулярно. –
Формального доказательство может быть получен с помощью насосной леммы для регулярных языков следующим образом:
Пусть язык является регулярным. Поэтому он должен удовлетворять лемме о перекачке для целочисленного числа const. Пусть s - любая строка с равным числом 0s и 1s. Тогда s можно разделить на 3 части х, у, г, такие, что |xy|<=p, |y|>0, то x(y^i)z, где i>=0 должны также принадлежат L.
Позвольте мне разделить строку следующим образом:
y является часть строки, которая имеет не равное число 0s и 1s.x может быть подстрокой s до y.z может быть частью после y.Теперь, если я «откачать» строку, взяв i = 0, то оставшаяся строка будет только xz, которые, безусловно, имеют неодинаковое число 0 и 1, которые не принадлежат к языку L.
Таким образом, мы достигли противоречия, поскольку мы ранее предполагали, что L является регулярным.
Таким образом, это не является регулярным.
Если это было немного трудно понять вышеприведенную часть, рассмотрите пример. Пусть p является целым числом 5. Пусть 0+1000+11101 - строка в L. (+ указывает на конкатенацию) Позвольте мне взять x как «0», y be "1000", z - оставшаяся часть 11101. Тогда, если мы выполним x(y^i)z с i=0, оставшаяся строка будет 011101, которая не является частью L. Таким образом, нерегулярно.
Примечание: пример был просто образцом, чтобы вы поняли логику. Невозможно определить значение p случайным образом.
Возможно, вы имеете в виду 'count', а не' sum'. – Kobi
@ Kobi есть какая-то теория эзотерического языка, которую вы пытаетесь сделать? В противном случае сумма «n» 1s совпадает с числом «n» 1s. – Alnitak
Помогает ли это: http://www.cs.nott.ac.uk/~txa/g51mal/notes-3x.pdf? –