1 Это можно сделать непосредственно, т.е. за одну операцию. Условное обозначение?.
Например,d?hозначает, что цепочку символовhможно получить из цепочкиdза одну операцию.
Пример. Есть цепочкиd=aAbиh=anb. Здесь,a,n,b- терминальные символы (обозначены строчными буквами), а А – нетерминальный символ. Пусть среди множества правил Р есть такое:A®nЄР. То есть нетерминальный символ АЄN можно заменить на терминальныйn. Таким образом, за одну операцию изdможно получить цепочкуh.
2 Одну цепочку из другой можно получить не за одну операцию. Условное обозначение?*.
Например,a0?*an.
Это имеет место или еслиa0 =an , или существует последовательность непосредственно получаемых цепочек, таких, что a0?a1?a2?…?