Автомат PushDown (PDA) для L={a^(n)b^(n)c^(n)|n>=1}

Question

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

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

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

Проблема с первым подходом:- сгенерированный язык становится примерно таким: L={a^(p)b^(m)c^(n)| p>=1 и не может определить, как можно определить m и n}

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

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

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

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

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

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

Answer 1

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

Машина очереди:

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

Двухстоечный КПК:

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

Одна из причин, по которой вам не удалось создать автомат для этого языка, заключается в том, что его нет. Лемма прокачки Бар Гилеля показывает это.

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

• | VWX | <р

• | ъх | > 1

• uv ⁿ wx ⁿ y также принимается автоматом для любого n.

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