линейная грамматика с неравным числом 0 и 1

Question

Возможно ли придумать линейную грамматику с неравным числом 0 и 1?

Например, 0100, 01100, 111,1,0, 100101001 ...

Я знаю, что для этого существует не зависящая от контекста грамматика, но есть ли линейная грамматика?

Спасибо.

Answer 1

Грамматика регулярна тогда и только тогда, когда она либо левая, либо правая.Левые регулярные грамматики эквивалентны левым линейным грамматикам.Правильные правильные грамматики эквивалентны правым линейным грамматикам.Следовательно, если существует регулярная грамматика, которая генерирует указанный язык, то она является правой или левой регулярной и, следовательно, эквивалентна либо левой, либо правой линейной грамматике.

edit ₁ :

Обратите внимание, что не существует регулярной грамматики, генерирующей указанный язык L _UNEQ .Чтобы увидеть это, рассмотрим тот факт, что L _EQ = {w: n _a ( w ) = n _b ( w )} является дополнением к L _UNEQ .Поскольку обычные языки закрыты при дополнении и L _EQ - это , а не обычный язык, L _UNEQ - это не обычный язык.

edit ₂ :

Я считаю, что лемму прокачки для линейных языков можно использовать дляпоказать, что указанный язык L _UNEQ не является линейным.Вот что я придумала.Я уверен, что это правильно.Моя основная проблема заключается в том, что вас попросили - предположительно - для линейного языка, генерирующего указанный язык;однако я пришел к выводу, что такой грамматики не существует.

Предположим, L _UNEQ линейно.По лемме прокачки для линейных языков существует n > 0 в зависимости от L _UNEQ , такой что для всех z ∈ L _UNEQ , z можно записать uvwxy где:

• | vx |> 0,
• | uvxy |≤ n и
• ультрафиолетовый ⁱ wx ⁱ y ∈ L _UNEQ для всех i ≥ 0.

Пусть n будет постоянной гарантированной величинойНасосная лемма.Рассмотрим строку

• z = a ⁿ b ^{(n! + 2n)} a ⁿ

С z ∈ L _UNEQ ,его можно разложить на подстроки uvwxy , удовлетворяющие ограничениям леммы прокачки, так что для всех i ≥ 0 строка

• uv ⁱ wx ⁱ y = a ^{| u |} a ^{i | v |} a ^{(n - | u | - | v |)} b ^{(n! + 2n)} a ^{(n - | x | - | y |)} a ^{i | x |} a ^{| y |}

является членом L _UNEQ .Так как 1 ≤ | vx |≤ n, | vx |делит n !.Следовательно, ( n ! | vx | ^-1 + 1) является натуральным числом.Установка i в ( n ! | vx | ^-1 + 1) дает строку

• z '= уф ^{( n ! | vx | -1 + 1)} ш ^{( n ! | vx | -1 + 1)} y = a ^{| u |} a ^{( n ! | vx | -1 + 1) | v |} a ^{(n - | u | - | v |)} b ^{(n! +2n)} a ^{(n - | x | - | y |)} a ^{( n ! | vx | -1 + 1) | x |} a ^{| y |}

Упрощениенакачанная колонна дает нам равное количество a и b ':

• n _a ( z ') = 2n - | vx |+ ( n ! | Vx | ^-1 + 1) | vx |= 2n + n !

С (2n+ n !) Эквивалентно числу b в перекачиваемой колонне, z '∉ L _UNEQ . Но это противоречит предположению, что L _UNEQ является линейным языком. Следовательно, L _UNEQ не является линейным языком.