Преобразование спецификации языка в правила производства (не уверен, что это CFG или CSG)

Question

Я должен написать функцию, которая проверяет, являются ли входные строки допустимыми для данной языковой спецификации. Я думал, что это будет стандартная форма CFG -> нормальная форма Хомского, затем синтаксический анализ CYK, но одно из правил в языке предотвращает это.

Некоторые правила просты, если мы определяем терминалы {a,b,c,d,e,f,P,Q,R,S}тогда допустимые строки

1) Любая из строчных клемм в изоляции
2) Если "x" является допустимой строкой, то и Sx

Но третье правило

3) Если X и Y являются допустимыми входными строками, то PXY, QXY, RXY

где {P,Q,R} остальные заглавные буквы, а X и Y не являются окончательными.

Как бы выглядело правило производства для этого? Я думал, что это будет что-то вроде

XY -> PXY (and QXY, RXY)

но есть две проблемы с этим. Во-первых, это не правило CFG - означает ли это, что этот язык вместо этого определяет CSG?

И второе, что это не работает, потому что

XY -> PXY -> PPXY

не будет действительным сообщением во всех случаях.

Answer 1

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

Во-первых, давайте позволим A быть нетерминалом, который расширяется до некоторой допустимой строки, сделанной только с использованием первых двух правил, мы получаем

A -> a | b | c | d | e | f

Теперь, ваше второе правило говорит, что если вы можете построить строку ω, то вы можете построить Sω. Мы могли бы закодировать это как

A -> SA

Наконец, вы сказали, что если у вас есть две строки X и Y, то вы можете объединить их вместе как

PXY
QXY
RXY

Один из способов думать об этом - генерировать строку P, за которой следуют любые две допустимые строки (то же самое для Q или R). Таким образом, вы можете добавить правила

A -> PAA | QAA | RAA

Это дает окончательную грамматику

A -> a | b | c | d | e | f
A -> SA
A -> PAA | QAA | RAA

Надеюсь это поможет!