Линейная грамматика, производное слово

Question

Предполагая, что дана правильная линейная грамматика, как бы вы показали шаги для получения слова?Например, если бы у меня был грамматик:

S -> aA
A -> bA
A -> aB
B -> cB
B -> a

И я хотел составить слово abbbacca.Как бы я показал мой шаг производной?Будет ли это:

S => A => A => A => A => B => B => B

или что-то более похожее на:

aA => abA => abbA => abbbA => abbbaB => abbbacB => abbbaccB => abbbacca

Answer 1

Преобразование комментариев в ответ, чтобы вопрос мог исчезнуть из списков без ответа ...

Форма

S => aA => abA => abbA => abbbA => abbbaB => abbbacB => abbbaccB => abbbacca

- более обычный и предпочтительный способ показать производную. Для дополнительного кредита, особенно для больших грамматик, может быть полезно показать метку правила, примененного к стрелке деривации, что-то вроде

S =(1)=> aA

Конечно, чтобы это было действительно полезно, правила должны иметь ярлыки!