У меня есть язык {a^i b^j c^k | i,j,k>=0 & i>j & j>k} . Я начал с предположения, что для меня выбрано какое-то m , такое, что строка z = a^m b^(m-1) c^(m-2) Затем строка разделяется на (z =) uvwxy , чтобы vx не были...

У меня есть один небольшой вопрос по поводу леммы о накачке для обычных языков - достаточно ли она хороша, чтобы показать, что если конкретная строка, принадлежащая языку L, не может быть прокачана, то язык является неправильным? Например, если я...

У меня вопрос по компилятору. Определите, является ли {(ab)^n | n >= 0} является обычным языком? Но я могу нарисовать свою НФА. Но если я воспользуюсь леммой о накачке, то получу противоречащий ответ. Может кто-нибудь мне помочь ?

У меня вопрос по конкретной проблеме леммы перекачки для контекстно-свободных языков. Предположим, у нас есть следующий язык: L = {(a^i)(b^j)(c^k)(d^l) | 0 < i < k AND j > l > 0 } Вот моя попытка доказать, что язык не является...

Я знаю, как решить лемму о накачке для a n b n :n›=0 Но я не понимаю, как решить этот пример: a n b 2n+1 :n›=0 Я пытался решить это, но я не уверен, что я решил это правильно или нет? Может ли кто-нибудь помочь мне здесь? Я могу показать, как я...

Я пытаюсь доказать, что следующий язык не является регулярным, используя лемму о накачке L = {a i b j | i = 2j для некоторого j 0} Я решил выбрать s = a 2p b p , таким образом, |s| p, и я могу разделить его на три части xyz, где для...

Итак, у меня есть домашний вопрос, который требует доказать, что A = {a ^ n b ^ n c ^ n | n> = 0} нерегулярно по лемме о накачке. Из моего учебника: Чтобы использовать лемму о накачке для доказательства того, что язык B не является...

У меня проблемы с довольно сложным вопросом. Меня просят доказать язык {0 ^ n 1 ^ m 0 ^ n | m, n> = 0} нерегулярно по лемме о накачке. Во всех примерах, которые я видел, язык повышается только до одной и той же переменной (т.е. a ^ n b ^ n). Итак,...

Как рассчитать минимальную длину прокачки обычного языка. Например, если у меня 0001*, то минимальная длина прокачки для этого должна быть 4, то есть 000 не прокачивается. Почему это так?

У меня возникли проблемы с доказательством того, что определенный язык не является регулярным. Язык определяется как L a = { wz : w,z ∈ {0,1}* и |w| > |г|} Я не знаю, как подойти к этому. Независимо от того, какую строку я выбираю, я...

Если я позволю строке w быть a^mb^m , то мы знаем, что y будет состоять только из a из-за правила |xy| <= m . И если я установлю i=0 , то ww^R будет иметь меньше a с левой стороны, чем с правой. Таким образом, это доказывает, что...

Я пытаюсь доказать, что следующий язык не является регулярным, используя лемму о накачке. L = {a k b 3l a l | к 1 , л 0} Я решил выбрать w = a b 3p a p , тогда |w| = 4п+1п Какие-нибудь советы? Спасибо!

Доказательство «выкачивания леммы» из книги ‹ Введение в теорию вычислений › : Лемма о накачке: если A — регулярный язык, то существует число p (длина накачки), где, если s — любая строка в A длины не менее p, то s можно разделить на три части, s...

Both Mr. Mithlesh Upadhyay and You play a game: 1. Mr. Mithlesh Upadhyay gives you a constant n. 2. You choose a word w in the language of length at least n. 3. Mr. Mithlesh Upadhyay gives you x, y, and z with xyz = w, |xy|≤n, and y not empty. 4. Now...

пусть L = {ww R u | w, u ∈ {0,1}+}. Является ли L обычным языком? Обратите внимание, что w, u не может быть пустым. Я пытался доказать, что это не обычный язык с помощью леммы о накачке, но потерпел неудачу, когда w = 0^p1^p , 01^p , (01)^p ....