автомат выталкивания, возможны два языка (условие ИЛИ)

Question

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

Насколько я понимаю, мы можем построить недетерминированный автомат выталкивания, и каждый раз, когда мы читаем символ a, мы можем вставлять либо один A, либо два A - по «усмотрению» автомата.

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

Я прав? Или я что-то упускаю?

Если нет, мне бы хотелось понять, как справиться с условием «или» в первом упражнении.

Спасибо.

Answer 1

поскольку $L_2\ne L_3$, они явно не могут быть приняты одним и тем же автоматом выталкивания. Похоже, вы имеете в виду автомат, который распознает$L_3$. Наверное, самый простой способ создать такой, чтобы распознавать$L_2$, заключается в разработке двух детерминированных автоматов выталкивания, один для $\{a^nb^n:n\in\Bbb N\}$ и один для $\{a^{2n}b^n:n\in\Bbb N\}$. Затем объедините их в один автомат, который имеет переходы.$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ и $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, где $q_0$ - исходное состояние комбинированного КПК, $Z$ - начальный символ стека, а $q_1$ и $q_2$являются начальными состояниями двух вспомогательных автоматов выталкивания. Другими словами, первое, что делает комбинированный КПК, - это «выбирает», искать ли слово типа$a^nb^n$ или слово типа $a^{2n}b^n$, а затем детерминированно следует этому выбору.