Для n> = 0 является ли данная грамматика (a ^ na ^ na ^ n) контекстной? Я пробовал использовать лемму о перекачке, и результат был, нет, это не контекстно-зависимый.

Как длина накачки обычного языка соотносится с длиной накачки родственного языка. Например, если A: ‹B:‹ C - все обычные языки, а k - длина накачки B, знаем ли мы что-нибудь о длинах накачки A и C? Когда мы смотрим на конечные языки, можно наивно...

L = { w | w in {0,1}* and w has equal number of 0s and 1s } Пусть n — номер леммы о накачке. Я выбираю s = 0 n 1 n и y = 0 t , где 1 ‹= t ‹= n. Что дает xyz = 0 (nt) 0 t 1 n = 0 n 1 n который находится в Л. Но xz = 0 (n-t) 1 n...

Это странно, но, прокачивая лемму, скажем Пусть L будет обычным языком. Существует константа n такая, что для каждой строки w в L такой, что |w| >= n , мы можем разбить w на xyz так, чтобы xy*z также было в L . Эта...

A = {0^a 1^b 2^c | a < b < c} Мне нужно показать, что A не зависит от контекста. Я предполагаю, что для этого мне нужно использовать лемму о накачке, но как?

У меня есть язык: L = {0 ^ i 1 ^ i | я> = 0} Грамматика, описывающая его, доказывает, что это контекстно-свободный язык: S -> 0S1 | е Если язык контекстно-свободный, должна выполняться лемма о перекачке. Однако я не могу заставить его...

Я немного запутался в теории леммы о накачке. Насколько я знаю, используется, чтобы решить, регулярный язык или нет. Есть переменная let be m такая, что есть состояния? x = vxu Where vx >= m And u not ε (>=1) and a variable i such that...

Как я должен доказать, что L={a^n b^m | n=km for k in N} не является обычным языком, используя лемму о накачке? Я начал с того, что взял слово w из L , w=a^n b^m с n=km вместо некоторого k из N . Есть три возможных разложения для w :...

Недавно у меня было задание, в котором меня попросили использовать лемму о перекачке, чтобы показать, что язык не является регулярным, и, к сожалению, я получил неправильный ответ. Язык, который нужно доказать, не является регулярным: L = {a i b...

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

Я пишу что-то о Ppumping Lemma. Я знаю, что язык L = {a^nb^n| n ≥ 0 } не зависит от контекста. Но я не понимаю, как этот язык удовлетворяет условиям леммы прокачки (для контекстно-свободных языков)? если мы выберем строку s = a^pb^p, |s| > р ,...

Приближается экзамен, и профессор хочет, чтобы эта информация была включена. Я понимаю, как работает лемма, но я не могу осмыслить, как происходит «накачка» с точки зрения входа или выхода и сколько раз.