Способ использования JFLAP для создания Pushdown Automaton

Question

Мне нужно создать автомат Pushdown с JFLAP, который распознает следующий язык:

Какие шаги нужно предпринять, чтобы сделать это? И как это работает?

Answer 1

Я думаю, что этот вопрос лучше подходит для https://cs.stackexchange.com/, но я все равно добавлю свое решение.

Формируем пример

На самом деле это проще, чем кажется, давайте рассмотрим в качестве примера, что у нас есть следующие значения для наших вхождений:

n = 2
m = 3
p = 1

Это должно позволить нам сформировать следующую строку:

a² b³ c¹ a^{1 + 3} b² = aabbbcaaaabb

Формирование логического понимания

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

1. Мы знаем, что встречаются внешние символы n раз и что n,m ≥ 1 поэтому мы должны следить за n здесь и мы требуем, чтобы это произошло хотя бы раз.
2. Мы знаем это q = p+m а также m также происходит, по крайней мере, поэтому мы должны отслеживать происшествия m,
3. Если q = p+m нам также нужно сохранить вхождение p но обратите внимание, что pтакже не может произойти, потому что заявлено, что p ≥ 0,

Формирование формального определения

Мы позволяем нашему КПК P быть следующим КПК:

P = (Q, Σ, Γ, τ, q₀, Z, q₆)

Куда:

• Q - набор состояний в нашем d-PDA
• Σ - входной символ, содержащий строку
• Γ - символ стека, содержащий множество Γ = {a, b}
• q₀ - наше начальное (начальное) состояние
• Z - наш символ стека #
• q₆ - наше конечное (конечное) состояние

Формирование автомата нажатия

Таким образом, из этого мы можем сформировать следующий автомат (в JFLAP):

Итак, здесь мы просто отслеживаем символы, как указано выше, но важно отметить, что здесь q3 где переход для c 0 или более переходов.

Мы также используем символ # как символ стека.

моделирование

Если мы смоделируем этот КПК с помощью ввода, как указано выше (aabbbcaaaabb), мы получаем следующие результаты: