История изменений
Исправление quasimoto, (текущая версия) :
То есть язык SKI нельзя породить с помощью BNF (КС по определению)
<T> ::= 'S' | 'K' | 'I' | '(' <T> <T> ')'
или грамматики Хомского
G = ({S, K, I, (, )}, {T}, T, {T -> S, T -> K, T -> I, T -> (TT)})
(тоже КС), так, что на соответствующем множестве термов (множестве строк как подмножестве KleeneStar({S, K, I, (, )}) порождённом указанными грамматиками) задаётся редуцирование и отношение бета эквивалентности делающее этот язык Тьюринг-полным?
А для разбора деревьев из текста (или его инвалидации) в случае КС-грамматик достаточно МП-автомата, как известно (разрешимость).
Исходная версия quasimoto, :
То есть язык SKI нельзя породить с помощью BNF (КС по определению)
<T> ::= 'S' | 'K' | 'I' | '(' <T> <T> ')'
или грамматики Хомского
G = ({S, K, I, (, )}, {T}, T, {T -> S, T -> K, T -> I, T -> (TT)})
(тоже КС), так, что на соответствующем множестве термов (множестве строк как подмножестве KleeneStar({S, K, I, (, )}) порождённом указанными грамматиками) задаётся редуцирование и отношение бета эквивалентности делающее этот язык Тьюринг-полным?
А для разбора деревьев из текста (или его инвалидации) в случае КС-грамматик достаточно МП-автомата, как известно.