преобразовать грамматику в МП-автомат

[Grumzik]

Добрый день! Помогите пожалуйста. Необходимо преобразовать грамматику в МП-автомат.
$S\to0S1|A$
$A\to1A0|S|\varepsilon$
Я понимаю, что данной грамматике принадлежат слова,которые как бы "обратно симметричны" относительные середины,т.е там где слева 1, справа симметрично будет 0 и наоборот. Я пробовала делать автомат, который последовательно записывает в стек, а как только в его вершине появляется 01 или 10, то это изымается. Но такой автомат будет допускать и слова, не принадлежащие данной грамматике, например 1001. Была идея, что надо последний сивол перемещать вперед, и если там противоположный, то удалять. Но я это могу сделать только один раз при начальном заполнение стека. Подскажите пожалуйста идеи.

[Профессор Снэйп]

Программа JFLAP Вам в помощь.

-- Чт фев 04, 2010 21:17:22 --

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

[Grumzik]

Извините, а я не знаю как определять середину слова. Ведь я исходное слово всего 1 раз считать могу, а в стеке я могу только его верхний символ видеть.

[Профессор Снэйп]

А Вам и не надо определять середину, её автомат сам определит. Недетерминированным образом Вы представляете себе, что такое недетерминированность и чем отличается недетерминированный автомат от детерминированного? Если нет --- срочно читать!!!

[Grumzik]

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

[Профессор Снэйп]

А когда недетерминированный автомат распознаёт слово?

[Grumzik]

Я Ваших наводящих вопросов совсем не понимаю. Можете пожалуйста объяснить как связана середина слова и недетерминированный автомат.

[Профессор Снэйп]

А смысл? Я объясню, а Вы опять не поймёте.

[Grumzik]

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

[Профессор Снэйп]

Grumzik в сообщении #285872 писал(а):

где почитать об том как недетерминированный автомат сам определяет середину?

Везде!

Вы просто не понимаете, что значит недетерминированный автомат распознаёт слово. Узнайте уже, наконец, каков ответ на мой наводящий вопрос, и перестанете писать здесь глупости.