Построение автомата пуш-ап из контекстно-свободной грамматики

Question

Построение автомата пуш-ап из контекстно-свободной грамматики

Из этого раздела вики-статьи о КПК я получил приблизительное представление о процессе создания КПК из данного CFG. То, что эта статья не проясняет, является шагом, необходимым, когда есть несколько производственных правил для одного нетерминала.

Например, предположим, что у нас есть грамматика, заданная в виде:

$S \to xAy$
$A \to B$
$B \to abB$
$B \to \epsilon$

Ясно, что эта грамматика распознает все строки вида x (ab) * y [по совпадению это тоже обычный язык].

Здесь у меня возникли проблемы при создании КПК из этой грамматики из-за этих 2 правил

$B \to abB$
$B \to \epsilon$

То есть, какое из этих двух правил будет использоваться на этапе расширения при одновременном нажатии на стек?

0

context-free-grammar pushdown-automaton pda

Источник

user1636016 04 ноя '13 в 06:29

2 ответа

Решение

Для более четких деталей у слайдов есть пример.

1

Источник

user2682363 11 мар '15 в 05:48

Другие вопросы по тегам context-free-grammar pushdown-automaton pda

user2682363 11 мар '15 в 05:42 2015-03-11 05:42 · Accepted Answer · 2015-03-11 05:42

Как показано в этом слайде, ваш КПК будет имитировать крайние левые выводы

1

Источник

user2682363 11 мар '15 в 05:42