Найти автоматы для этого языка L={A^i B^j C^k | 2k <= i <= 3k ИЛИ j!= (I +k) } с одним стеком
Я не могу найти автоматы, потому что я могу представить его только с несколькими стеками или с пересечением теории множеств.
1 ответ
Язык: L = { A^i B^j C^k | 2k <= i <= 3k OR j != (i+k) }
Этот язык является объединением двух языков L' а также L'':
L' = { A^i B^j C^k | 2k <= i <= 3k }
L'' = { A^i B^j C^k | j != (i+k) }
Если мы определим NPDA для каждого из этих языков, мы можем записать новый NPDA для объединения этих двух языков:
- введение нового начального состояния,
q* - добавление переходов
f(q*,e,Z) = (q0',Z)а такжеf(q*,e,Z) = (q0'',Z)гдеeэто эпсилон / лямбда,Zявляется дном символа стека иq0'а такжеq0''начальные состояния NPDA дляL'а такжеL''соответственно.
Мы разложили более сложную проблему на две более простые задачи и выяснили, как соединить ответы на более простые задачи, чтобы ответить на более сложную проблему. Это самый важный навык, который вы можете развить, когда дело доходит до формальных наук, таких как информатика, математика и, в значительной степени, компьютерное программирование.
Для чего нужен NPDA L' выглядит как? Он может читать любое количество BS вообще, при условии, что они находятся между Aс и Cs. Нам нужно отслеживать, сколько AS мы видим, скажем, нажав A в стек каждый раз, когда мы видим один; и нам нужно поп Aсо стека, как только мы начинаем видеть Cs. Предполагая, что мы хотим принять пустой стек, нам нужно удалить все As; а откуда мы знаем сколько убрать? Если бы мы имели 2k = iмы удалили бы два Aдля каждого C мы видим. Если бы мы имели i = 3kмы удалили бы три Aдля каждого C мы видим. Как есть, мы где-то посередине. Это концептуальная трудность. Понятие недетерминизма - N в NPDA - имеет решающее значение здесь. Нам не нужно точно знать, как строка будет принята; нам просто нужен процесс, который может принять строку на языке, а не принять ее не на языке. Мы можем догадаться, нужно ли нам удалить два или три As из стека в любой конкретный момент; это гарантирует, что мы не превысим 2k а также 3k границы, и это также позволит нам получить любой промежуточный результат. Чтобы это работало, мы можем просто аварийно завершить или отклонить все неудачные выполнения допустимых строк при условии, что одно из возможных выполнений прошло.
Вот NPDA, основанный на этом описании, предполагающий принятие пустым стеком и принимающее состояние:
Q s S Q' S'
------------------------
// read A's and push onto stack
q0 A Z q0 AZ
q0 A A q0 AA
// begin reading B's
q0 B Z q1 Z
q0 B A q1 Z
// begin reading C's if no B's
q0 C A q2 -
q0 C A q3 -
// read B's
q1 B Z q1 Z
q1 B A q1 A
// begin reading C's if B's
q1 C A q2 -
q1 C A q3 -
// pop the final A for the last C read
q2 - A q4 -
// if popping three A's, pop the middle A
q3 - A q2 -
// pop the first A for each C read after the first C
q4 C A q2 -
q4 C A q3 -
// transition to separate accepting state if stack empty
q4 - Z qA -
В приведенном выше NPDA переходы, которые приведут к "мертвому" состоянию, не показаны. Если вы хотите показать это, добавьте эти переходы и назовите состояние qR, В отсутствие этих явных переходов NPDA обычно понимается как "сбой" и отклоняет ввод. Для любой строки в L'будет путь через это NPDA что заканчивается в государстве qA с пустым стеком.
Для другого языка мы можем разбить его дальше. L'' это союз двух языков R' а также R'':
R' = { A^i B^j C^k | j < i + k }
R'' = { A^i B^j C^k | j > i + k }
Используя ту же конструкцию, описанную выше, мы можем создать NPDA для L'' находя NPDA для R' а также R'' и положить эти ответы вместе.
За R'мы можем подтолкнуть Aв стек, когда мы читаем As; мы можем поп As, если есть, или нажмите Bиначе при чтении Bs; и, наконец, мы можем поп Bs, если есть, или нажмите Cиначе при чтении Cs. Мы будем иметь j < i + k если и только если есть A или же C на вершине стека, когда мы закончим. Затем мы можем перейти в принимающее состояние и поп Aс и Cs из стека, чтобы получить пустой стек.
За R''мы можем сделать то же самое и искать B на вершине стека. Мы можем перейти в принимающее состояние и поп Bs очистить стек.
R' R''
Q s S Q' S' Q s S Q' S'
----------------------- -----------------------
// count A's, first B/C // count A's, first B/C
q0' A Z q0' AZ q0'' A Z q0'' AZ
q0' A A q0' AA q0'' A A q0'' AA
q0' B Z q1' BZ q0'' B Z q1'' BZ
q0' B A q1' - q0'' B A q1'' -
q1' C Z q2' CZ q0'' C A q2'' CZ
q1' C A q2' CA q0'' C Z q2'' CA
// count B's, first C // count B's, first C
q1' B Z q1' BZ q1'' B Z q1'' BZ
q1' B A q1' - q1'' B A q1'' -
q1' B B q1' BB q1'' B B q1'' BB
q1' C Z q2' CZ q1'' C Z q2'' CZ
q1' C A q2' CA q1'' C A q2'' CA
q1' C B q2' CB q1'' C B q2'' CB
// count C's // count C's
q2' C Z q2' CZ q2'' C Z q2'' CZ
q2' C A q2' CA q2'' C A q2'' CA
q2' C B q2' - q2'' C B q2'' -
q2' C C q2' CC q2'' C C q2'' CC
// accept if A's or C's // accept if B's
q2' - A qA' - q2'' - B qA'- -
q2' - C qA' -
// accept if A's or C's // accept if B's
qA' - A qA' - qA'' - B qA'' -
qA' - C qA' -
Следовательно, NPDA для вашего языка оригинала:
Q s S Q' S'
-----------------------
q* - Z q0 Z
q* - Z q0' Z
q* - Z q0'' Z
Добавьте к этому все другие переходы, данные ранее, и определите принятие как пустой стек в любом из трех принимающих состояний. qA, qA' или же qA'',