Алгоритм проверки грамматики против другой грамматики в ll(1)

Question

Мне нужен алгоритм, который проверяет, является ли язык G1 подмножеством языка G2 или нет. (Предположим, что G1 и G2 - две грамматики LL(1) с одинаковыми алфавитами, правила производства которых имеют форму A -> aB или A -> a, а "a" не является эпсилоном. У меня есть алгоритмы синтаксического анализа что проверка грамматики по отношению к строке, но не проверки по отношению к другому языку. Есть ли кто-нибудь, кто имеет решение.

Answer 1

Ваши грамматики выглядят как правильные. Таким образом, алгоритм заключается в преобразовании грамматик в NFA. Это тривиальное отображение 1-1. Затем преобразуйте NFA в DFA с использованием конструкции подмножества. Назовите их A и B. Их легко проанализировать, чтобы определить подмножество L (A)? ФУНТ). Например, поскольку существуют хорошо известные эффективные алгоритмы определения L(A) ==? L(B) и построение новой машины I(A,B), которая принимает L (A) пересечение L (B), просто вычислить

( L(I(A,B)) ==? L(A) )  or  ( L(I(A,B)) ==? L(B) )