ОБ ОДНОМ КРИТЕРИИ ЛЕВОРЕКУРСИВНОСТИ КОНТЕКСТНО-СВОБОДНОЙ ГРАММАТИКИ
см. http://arxiv.su/blogs/users/ashkotin/28498/
Определение: КСГ леворекурсивна если в ней существует леворекурсивный нетерминал.
Определение: нетерминал N1 леворекурсивен, если существует правило N1:N1q1, или существует вывод N1=>+N1q2, где q1, q2 — цепочки символов.
Проблема: непосредственно в определении предлагается рассмотреть все возможные цепочки, выводимые из N1, и посмотреть встретится ли хотя бы в одной из них N1 в начале. В общем случае цепочек бесконечно много и просмотреть их все не представляется возможным.
Критерий: пусть КСГ является КСГ «без e-правил». Построим ориентированный помеченный граф:
- Узлы — ровно столько сколько нетерминалов в КСГ. Каждый узел помечен своим нетерминалом.
- Стрелка проводится из N1 в N2 тогда и только тогда, когда существует правило N1:N2q. Для удобства стрелка метится этим правилом.
Усмотрение: КСГ леворекурсивна тогда и только тогда, когда у графа есть цикл (возможно петля).
Обоснование:
- если существует вывод, то каждое применённое правило имеет вид N1:N2q, т.к. у нас нет e-правил. Для каждого такого правила на графе проведена стрелка. Таким образом вывод пройдёт по графу и приведёт нас к исходному узлу, т.е. мы получим цикл.
- наоборот: если на графе есть цикл, то выписав правила находящиеся на метках стрелок (проходя их от начала к концу цикла) мы получим подстановки самого левого символа цепочки, которые дадут в результате опять N1 в начале.