Описание тега pumping-lemma
Лемма в основном используется для доказательства того, что язык не является регулярным / контекстно-независимым.
2
ответа
Накачка леммы в контекстно-свободных языках
A = {0^a 1^b 2^c | a < b < c} Мне нужно показать, что A не является контекстно-свободным. Я предполагаю, что для этого мне нужно использовать Лемму прокачки, но как?
04 ноя '10 в 10:01
1
ответ
Понять лемму прокачки
Я относительно новичок в лемме прокачки, и у меня есть проблема, которая, я думаю, я ответил правильно, может кто-нибудь сказать мне, если это работает, и если нет, то почему Проблема: {www | w is {a,b}*} Мой подход: L = www u * (v ^ k) * w должно б…
30 апр '14 в 23:14
1
ответ
Прокачивание леммы на обычных языках?
Я немного запутался в теории леммы прокачки. Как я знаю, используется, чтобы решить, является ли язык регулярным или нет. Существует переменная let m такая, что это состояния? x = vxu Where vx >= m And u not ε (>=1) and a variable i such that …
09 янв '14 в 02:57
2
ответа
Контекстная лемма прокачки
Является ли следующий языковой контекст бесплатным? L = {a^i b^k c^r d^s | i+s = k+r, i,k,r,s >= 0} Я пытался придумать грамматику без контекста, чтобы сгенерировать это, но не могу, поэтому я предполагаю, что она не является контекстно-свободной…
24 апр '12 в 23:51
1
ответ
Этот язык регулярный? {0^n 1^m | m!= n}, я не понимаю прямого доказательства по длине накачки
Есть прямой способ доказать это: если p длина накачки, и мы берем строку s = 0p1p+p! тогда неважно что такое разложение s = xyz это строка xy1+p!/|y|z будет равно 0p+p!1p+p! чего нет в языке. Я не понимаю значение y, данное здесь.
16 окт '14 в 02:12
1
ответ
Насосная лемма (Обычный язык)
Мне нужна помощь с проблемой прокачки леммы. L = { {a,b,c}* | #a(L) < #b(L) < #c(L) } Это то, что я получил так далеко: y = uvw is the string from the pumping lemma. Я положил у = abbc^n, n - длина из леммы прокачки. y находится в L, потому чт…
16 ноя '12 в 00:13
1
ответ
Есть ли в обычном языке L бесконечные слова?
Это странно, но прокачивая лемму, скажем Позволять L будь обычным языком. Существует постоянная n такой, что для каждой строки w в L такой, что |w| >= nмы можем сломать w в к xyz такой, что xy*z также в L, Эта лемма сильна, потому что она доказыв…
12 апр '16 в 18:47
1
ответ
Трудно закрепить нерегулярный язык с накачкой леммы
У меня возникают проблемы с доказательством того, что определенный язык не является регулярным. Язык определяется как La = { wz: w, z ∈ {0,1} * и |w| > |z|} Я не знаю, как подойти к этому. Независимо от того, какую строку я выбираю, я всегда сталкив…
25 фев '16 в 23:42
2
ответа
Свойства закрытия контекстно-свободных языков
У меня есть следующая проблема: Языки L1 = {a^n * b^n: n>=0} и L2 = {b^n * a^n: n>=0} являются языками без контекста, поэтому они закрыты для L1L2, поэтому L={a^n * b^2n A^n: n>=0} также должен быть свободным от контекста, так как он генерируется св…
09 май '10 в 05:17
1
ответ
Насосная лемма для языка, который является регулярным
Я пытаюсь показать, как лемма прокачки применима к языку, который наверняка является регулярным. У меня есть язык {0, 1} с четным числом 1. Этот язык может быть представлен DFA с двумя состояниями. Таким образом, длина накачки здесь составляет 2, пр…
31 янв '14 в 22:52
2
ответа
Почему число строк должно быть больше или равно числу состояний в лемме прокачки?
Если L регулярный язык, то существует постоянная n (который зависит от L) такой, что для каждой строки w на языке Lтакой, что длина w Больше или равно nмы можем разделить w на три строки, w = xyz, w = length of string. n = Number of States. Почему м…
27 мар '15 в 19:55
1
ответ
Насосная лемма для обычного языка
У меня есть небольшая путаница в проверке, является ли данный язык регулярным или нет, используя лемму прокачки. Предположим, мы должны проверить: Язык принимающий четное число 0 в обычном или нет? Мы знаем, что это регулярно, потому что мы можем по…
05 фев '13 в 10:18
2
ответа
Является ли bin(n)bin(2^(k+1) * n + 1)^R контекстом бесплатно?
bin - самое короткое число в двоичной системе Является ли bin(n)bin(2^(k+1) * n + 1)^R контекстом бесплатно? k, n принадлежит натуральным числам. Я знаю, что bin(n)bin(n + 1)^R не зависит от контекста, но я не знаю, как решить bin(n)bin(2^(k+1) * n …
11 фев '19 в 06:28
0
ответов
Как выбрать слово для прокачки леммы?
У меня есть язык L={a^i b^j c^k | i,j,k >= 0, i+j=k}. С леммой прокачки я должен показать, что язык не является регулярным. Как мне начать? Могу ли я выбрать слово z=a^n c^n, чтобы показать его (поэтому j=0). Или я должен использовать слово z = a^n …
26 фев '19 в 13:47
1
ответ
Являются {a^n | n >= 0} и {a^p | р = простое число} не регулярно?
В курсе CS у меня есть следующие примеры: {a^n | n >= 0} а также {a^p | p = prime number} Эти языки регулярны или нет? Есть ли кто-нибудь, кто может сделать противоречие накачки леммы?
19 апр '15 в 09:22
1
ответ
Советы по проверке языка не являются регулярными с использованием леммы Pumping
Я пытаюсь доказать, что следующий язык не является регулярным, используя лемму прокачки L = {ai bj | i = 2j для некоторого j ≥ 0} Я решил выбрать s = a2p bp, таким образом |s| ≥ p, и я могу разбить его на три части xyz, где для каждого i ≥ 0, xyi z …
23 май '13 в 10:59
3
ответа
Докажи язык нерегулярным с прокачкой леммы
Я пытаюсь доказать, что следующий язык не является регулярным, используя лемму прокачки L= { a^i b^j | я ^2 > J} Любые советы по этому поводу? Я полностью застрял. Благодарю.
18 окт '11 в 16:42
2
ответа
Использование леммы Огдена против регулярной леммы накачки для контекстно-свободных грамматик
Поэтому я изучаю разницу между лемматами в вопросе. Каждая ссылка, которую я могу найти, использует пример: {(a^i)(b^j)(c^k)(d^l) : i = 0 or j = k = l} чтобы показать разницу между ними. Я могу найти пример, используя обычную лемму, чтобы "опровергн…
27 сен '12 в 02:06
1
ответ
Насосная Лемма Помощь
Недавно у меня было задание, в котором меня попросили использовать накачанную лемму, чтобы показать, что язык не является регулярным, и, к сожалению, получил неправильный ответ. Язык для доказательства является нерегулярным: L = {ai bj ck: i = j или…
18 окт '16 в 04:22
0
ответов
Лемма прокачки на регулярном языке для строки с четными нулями
Определить, является ли строка с четным числом нулей а) контекстной, б) регулярной а) используя лемму прокачки для КЛЛ.... ее можно представить как e (0n) e (0n) e. так что это КЛЛ. б) это можно представить как (00)* в регулярном выражении Итак, я д…
07 апр '14 в 09:36