Какой язык принимает КПК, показано ниже

Question

Я не уверен в своем ответе на этот вопрос. Когда я следую за вопросом, мой ответ:

{a^nb^ma^n | m,n∈ N,m,n>=0}

Это правильно? Может кто-нибудь проверить мой ответ?

Answer 1

Предположим, что этот КПК принимает только состояние, и содержимое стека не имеет значения.

Затем он принимает все следующие параметры:

1. bb *, сразу видя ab из состояние 0
2. (aa) *, путем перехода между состояниями 0 и 2
3. (a ^ n) b * (a ^ n) для n> 0 путем чтения na в состояниях 0 и 2 , затем чтение любого числа b в состоянии 3, затем чтение na в состоянии 4.

Пункт 3 - это то, что вы определили, за исключением того, что он не включает пустую строку. Однако наш пункт №2 включает пустую строку, так что с этим счетом все в порядке. Итак, ваш язык не содержит ничего НЕ на языке; ваш язык является подмножеством моего.

Но мой язык также является подмножеством вашего, поскольку элемент 1 соответствует просто всем непустым строкам на вашем языке с n = 0, а мой элемент 2 соответствует все строки на вашем языке с m = 0.

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