PushDown Automaton (PDA) для L = {a^(n) b^(n) c^(n) | n> = 1}

Question

Я нахожусь в безумном поручении, пытаясь построить автомат Pushdown для неконтекста -бесплатный язык L = {a^(n) b^(n) c^(n) | n> = 1} и думал о двух подходах.

Первый подход: -

Я думал, что для каждого «а» в строке I подтолкнет 3 «а» в стек и для каждого «Ъ» в строке, я выскочит 2 'a' из стека теперь для каждого 'c' в строке, я все равно буду иметь 1 'a' в стеке.

Проблема с первым подходом: - язык, порождаемый становится чем-то вроде этого L = {а^(р) Ь (т) с^(п) | р> = 1 и не мог определить, как т и п могут быть определены}

Второй подход: -

Мы знаем, что L = {а^(п) Ь (m) c^(m) d^(n) | n> = 0} - контекстно-свободный язык и L = {wxw | w∈ (a, b) *} также является контекстно-свободным языком.

Итак, я думал, что L = {a^(n) b^(m) b^(m) c^(n) | п> = 1 и т = пол ((п + 1)/2)}

Проблема со вторым подходом: - не знаю, если мы можем вычислить пол (п + 1/2) в КПК без нарушения элементов стека.

Помогите определить, как m и n могут быть определены в первом подходе, и как я могу найти пол ((n + 1)/2) в КПК.

Файлы JFLAP доступны как при необходимости.

Answer 1

Как отмечает Ami Tavory, для этого языка нет КПК, так как этот язык не является контекстным. Легко распознать этот язык, если вы используете очередь вместо стека, используете два стека или используете машину Тьюринга (все эквиваленты).

Queue машина:

1. Enqueue a с тех пор, как вы видите a с, пока вы не увидите b.
2. Dequeue a s и Епдиеие b с тех пор, как вы видите b с, пока вы не увидите c
3. DEQUEUE b сек до тех пор, как вы видите c с.
4. Принять, если вы закончите этот процесс без дополнительного ввода и пустой очереди.

Два стека PDA:

1. Используйте первый стек, чтобы убедиться, a^n b^n нажатием a когда вы видите a и выскакивают a, когда вы видите b;
2. Используйте второй стопку, чтобы убедиться, что b^n c^n нажав b, когда вы видите b и выскакивает b, когда вы видите c;
3. Примите, если оба стека пусты в конце этого процесса.

машина Тьюринга:

1. Обеспечить a^n ... c^n путем замены каждого a с A и стирание соответствие c;
2. Обеспечить A^n b^n путем удаления совпадающих пар A и b;
3. Примите, если в конце этого процесса у вас больше нет A и не более b, т. Е. Лента была полностью очищена.

Answer 2

Одна из причин, по которой вам не удалось построить автомат для пуска, для этого языка, потому что его нет. Это показывает Bar Hillel pumping lemma.

Чтобы набросать доказательство, предположим, что это можно сделать. Тогда для некоторого р, каждая строка больше, чем р может быть разделена на uvwxy, S.T.,

• | VWX | < p

• | vx | > 1

• ^{уф п} WX ^п у также принят автоматом, для любого п .

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