Is L = {a^n b^m | n> m} регулярный или нерегулярный язык?

Question

У меня возникли проблемы при решении/доказательстве этой проблемы. Любые идеи, пожалуйста?

Answer 1

L = {а ^п б ^м | n> m} есть нет правильный язык.

Да, проблемы сложно в первые несколько попытках и заслуживает голоса вверх.

Pumping Lemma Необходимое свойство регулярного языка - инструмент для формального доказательства того, что язык не является правильным языком.

Формальное определение: Pumping lemma for regular languages

Пусть L быть регулярным языком. Тогда существует целое число р ≥ 1, в зависимости только от L таким образом, что каждая строкаш в л длиной, по меньшей мере р (р называется «длиной накачки») может быть написанные в ш = хуг (т.е. ш может быть разделена на три суб-строк), удовлетворяющих следующим условиям:

1. | y | ≥ 1
2. | xy | ≤ р
3. для все я ≥ 0, ху ^я г ∈ л

Предположим, если вы выбираете строку W = а ^п b ^m, где (n + m) ≥ p и n > m + 1. Выбор W действителен, но этот выбор Вы не можете показать, что язык не правильный язык. Потому что с этим W вы всегда по-крайней мере один выбор y=a прокачивать новые строки на языке, повторяя a для всех значений i(при г = 0 и я> 1) ,

Прежде чем написать свое решение для доказательства, язык не является регулярным.Пожалуйста, обратите внимание на следующие пункты и уведомление: я сделал смелые every string w и all i в формальном определении леммы о перекачке выше.

• Хотя с некоторыми Sufficiently large W в языке, который вы способны генерировать новую строку в языке, но не для всех! Есть много возможных вариантов для W (ниже в моем доказательстве) с тем, что вы не можете найти любого выбора из у для создания новой строки в языке для всех я> = 0. Так что каждый Sufficiently large W не способен генерировать новую строку в языке, поэтому язык NOT regular.

считывание: what pumping lemma formal definition says

Доказательства использования насосной леммы

Шаг (1): наличие строки Вт = а ^н б ^м котором (n + m) ≥ p и n = m + 1.

Is this choice ofWis valid according to pumping lemma?

Да, такое Вт в языке потому, что количество a = п > количество b = м. W находится на языке и достаточно большой> = p.

Step (2): Теперь выбрал y для создания новой строки для всеi >= 0.

И нет выбор возможен для y на этот раз! Зачем?

Первый, это эссе, чтобы понять, что мы не можем иметь b символ в у, потому что он будет либо генерировать новые строки выхода из шаблона или в результате строки общего числа b будет более чем общее число a символов.

Второй, мы не можем выбрать у = некоторые «s, потому что с i=0 вы получите новую строку, в которой число a с будет менее номером b s, что не представляется возможным в языке. (запомнить количество a в W был только еще один, то b поэтому удаление любого средства в результирующей строке N (а) = N (б), что не является приемлемым, так как п> т)

Таким образом, мы могли бы найти некоторые W, которые достаточно велики, но с использованием этого мы не можем генерировать новую строку на языке, которая противоречит свойству леммы перекачки регулярного языка, следовательно, тогда язык {a ⁿ b ^m | n> m} не действительно правильный язык.