Подтвердить строку, указанную Контекст Свободная грамматика в Java

Question

Как кто-то может проверить, является ли строка частью контекстной свободной грамматики? Не только виртуально, но и построить для него алгоритм?

Учитывая контекст свободной грамматики с правилами, такими как

• V-> v1v2
• v1-> 1 | 1v1
• v2-> 2 | 2v2

Очевидно, что это язык 1^n 2^n. Но как бы вы шли с помощью алгоритма, чтобы проверить, действительно ли это на самом деле. Я пытаюсь выполнить это в java.

Answer 1

Возможно, вы захотите изучить Earley's algorithm или CYK algorithm, которые являются двумя алгоритмами для определения того, генерируется ли строка из контекстно-свободной грамматики. Алгоритм Эрли работает во времени O (n) для любой строки длины n, независимо от правил производства в грамматике (хотя постоянный член в записи большого числа O зависит от грамматики), тогда как алгоритм CYK требует, чтобы грамматика сначала преобразуется в Chomsky normal form, чтобы гарантировать O (n) время выполнения.

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