В моей записной книжке я написал:Необходимое условие для грамматики неоднозначности
Необходимое условие для грамматики двусмысленности
A->BB, где А и В нетерминалы.A->a|b, где A является нетерминальным, а {a, b} - терминалами.Не могли бы вы подтвердить или опровергнуть это заявление?
Это не так, потому что есть другие двусмысленные грамматики, которые не имеют ни одного из этих правил.
Например cc может быть получены A -> Bc -> cc, но и A -> cC -> cc в следующей грамматике:
A -> Bc | cC
B -> c
C -> c
Спасибо. Возможно ли, что учитель говорил о грамматике, которая является продуктом какого-то упрощающего алгоритма? Ваш пример может быть упрощен до A -> cc | см. – Josef
Возможно, учитель приводил примеры двусмысленных грамматик с этими правилами. Хотя я не понимаю, почему использование второго типа правил приведет к двусмысленной грамматике. –
@Grant Фактически 'A -> cc | cc' - это то же самое, что писать 'A -> cc', который * не * неоднозначен. Помните, что формальная грамматика является ** набором ** произведений вида 'α -> β'. И '{α -> β, α -> β} = {α -> β}', поскольку наборы не содержат дубликатов. Однако вы можете упростить грамматику в ответ на: 'A -> Ac | cA | c'. – Bakuriu
Определения неоднозначной грамматики ясно: есть больше чем один вывод для предложения в языке. Я не помню алгоритмического решения для поиска, если грамматика неоднозначна. – Apalala