Как я могу доказать, является ли этот язык регулярным или нет?

Question

Как я могу доказать, является ли этот язык регулярным или нет?

L = {a ⁿ b ⁿ : n≥1} union {a ⁿ b ^{n + 2} : n≥1}

Answer 1

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

Идея состоит в том, чтобы использовать теорему Нерода - показать, что существует бесконечное число групп эквивалентности для R _L - и из теоремы можно вывести, что язык является нерегулярным .

Определить два типа наборов:

1. G_j = {a ⁿ b ^k |nk = j, k≥1} для каждого j в [-2, -1,0,1, ...]
2. H_j = {a ^j } для каждого j в [0,1, ...]
3. G_illegal = {0,1} ^* / (G_j U H_j) [для каждого j в указанном диапазоне]

Легко видеть, что для каждого x в G_illegal и для каждого z в {a, b} ^*: xz не входит в L.

Итак, для каждого x,y в G_illegal и для каждого z в {a, b} ^*: xz в L <-> yz в L.

Кроме того, для каждого z в {a, b} ^* - и для каждого x, y в некоторых G_j [таких же jдля обоих]:

• , если z содержит a, оба значения xz и yz отсутствуют в L
• , если z = b ^j , тогда xz = a ⁿ b ^k b ^j , а поскольку k+j = n - xz находится в L.То же самое относится к y, поэтому yz находится в L.
• , если z = b ^{j + 2} , то xz = a ⁿ b ^k b ^{j + 2} , а поскольку k+j+2 = n+2 - xz находится в L.То же самое относится к y, поэтому yz находится в L.
• , в противном случае x равно b ⁱ , так что i ≠ j и i ≠ j + 2, ивы получите, что xz и yz не в L.

Итак, для каждого j и для каждого x,y в G_j и для каждого z в {a, b} ^*: xz в L <-> yz в L.

Докажите то же самое для каждого H_j, используя тот же подход.

Также легко показать, что для каждого x G_j U H_j и для каждого y в G_illegal - для z = b ^j , xz находится в L иyz не в L.
Для x в G_j и y в H_i, для z = ab ^{j + 1} - легко увидеть, что xz не в L и yz в L.
Легко видеть, что для x, y в G_j и G_i соответственно или x, y в H_j, H_i - для z = b ^j : xz находится в L, а yz - нет.

Мы только что доказали, что созданные нами множества на самом деле являются отношениями эквивалентности для R _L из теорема Нерода и так как у нас есть бесконечное число этих множеств, каждое является отношением эквивалентности для R _L [у нас есть H_j и G_j для каждого j] - , которые мы можем вывести изТеорема Нерода о том, что язык L нерегулярен.

Answer 2

Вы можете просто использовать насосную лемму для обычных языков. В основном это говорит о том, что если вы можете найти строку для любого заданного целого числа n и любого разбиения этой строки на xyz так, чтобы | xy | <= n и | y | > 0, то вы можете накачать часть y строки, и она должна остаться на языке, это означает, что если xy ^ iz это не на языке для некоторых i, то язык не является регулярным.

Доказательство выглядит следующим образом, своего рода доказательство противника. Предположим, кто-то говорит вам, что этот язык регулярный. Затем спросите у него число n> 0. Вы строите удобную строку длиной больше n и даете противнику. Он разбивает строку по x, y z любым удобным для него способом, если | xy | <= п. Затем вам нужно прокачать y (повторить это i раз), пока не найдете строку, которая не на том же языке. </p>

В этом случае я говорю вам: дайте мне n. Вы исправляете. Я говорю вам: возьмите строку «a ^ n b ^ {n + 2}» и скажите, чтобы вы ее разбили. Любым способом, которым вы можете разбить эту строку, вы всегда должны будете сделать y = a ^ k с k> 0, так как вы вынуждены сделать | xy | <= n, и моя строка начинается с ^ n. Вот хитрость, вы даете противнику строку, чтобы любым способом, которым он может разбить ее, он дал вам часть, которую вы можете прокачать. Так что теперь мы качаем y, скажем, 0 раз, и вы получаете «a ^ m b ^ {n + 2}» с m <n, чего нет на вашем языке. Готово. Мы также можем прокачать 1 раз, n раз, n! Факторное время, все, что вам нужно, чтобы оно покинуло язык. </p>

Доказательство этой теоремы повторяется, говоря, что если у вас есть регулярный язык, то у вас есть автомат с n состояниями для некоторого фиксированного n. Если строка содержит более n символов, она должна пройти некоторый цикл в вашем автомате. Если мы назовем x часть строки перед входом в цикл, а y часть цикла, ясно, что мы можем качать y столько раз, сколько хотим, потому что мы можем продолжать работать в цикле столько раз, сколько мы хотим и результирующая строка должна быть на языке, потому что она будет распознаваться этим автоматом. Чтобы использовать теорему для доказательства нерегулярности, поскольку мы не знаем, каким будет предполагаемый автомат, мы должны оставить противнику возможность выбора для n и для положения цикла внутри автомата (не будет автомат, но вы говорите противнику что-то вроде: осмелитесь дать мне автомат, и я покажу вам, что он не может существовать.)