Как написать производственное правило для набора мощности данного набора

Question

Я пишу небольшой командный язык.Язык имеет несколько простых команд, которые могут быть составлены, чтобы составить сложные.Например, если у нас есть команды fry an egg, make a sandwich, make coffee, мы можем создать новую команду:

make a breakfast := fry an egg, make a sandwich, make coffee.

Однако иногда я хочу только кофе на завтрак, иногда кофе и бутерброд и т. Д. То есть make a breakfast может быть любым подмножеством набора команд: {fry an egg, make a sandwich, make coffee}

Таким образом, мне нужноправило для определения набора мощности данного набора простых команд.Имеет ли это смысл ?Могу я это сделать?

Answer 1

Похоже, вы используете (E) грамматическую нотацию BNF. Если ваш вопрос о том, как захватить powerset в грамматическом правиле. AFAIK (E) BNF позволяет только описывать неконтекстные грамматики, однако набор мощности можно смоделировать как язык {a ^ 2 ^ n} в алфавите {a}, который является контекстно-зависимым Это означает, что вы не можете использовать (E) BNF для описания какого-либо powerset. Однако, что вы можете сделать, это перечислить конкретный powerset. Например: S: = (a, {b, {c}} | (b, {c}) | c | эпсилон); Этот язык является powerset алфавита {a, b, c}.