линейная грамматика с неравным количеством нулей и единиц

изменить₂:

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

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

• |vx| > 0,
• |uvxy| ≤ n и
• uvⁱwxⁱy ∈ L< sub>UNEQ для всех i ≥ 0.

Пусть n — константа, гарантированная леммой о накачке. Рассмотрим строку

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

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

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

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

• z' = uv^{(n!|vx|-1 + 1)}wx^{(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 и b:

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

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