Как проверить, доступна ли строка с использованием определенных правил?
Прошла 1 неделя с тех пор, как я начал пытаться найти решение этой проблемы, и в итоге я прочитал об алгоритме CYK, но не могу понять, как он мне поможет.
Итак, у меня есть определенная строка, с которой я начинаю, давайте назовем ее startString.
И у меня есть определенная строка, которую я хочу получить, применяя объясненные позже правила, называемые stopString.
————
Теперь давайте возьмем пример:
startString = "A"stopString = "2403"Правила этого примера следующие:
A->BC
B->D
B->ED
C->F
C->FBE->0
D->2
D->3
F->4
E->1
Программа примет вышеуказанный ввод и выведет минимальный список преобразований, примененных для перехода от startString к stopString, который МОЖЕТ БЫТЬ следующие:
A->BC, B->D, C->FB, B->ED, D->2, F->4, E->0, D->3
————
Мой вопрос: как CYK помогает мне здесь? Как получить «2403» из «А» с помощью CYK? Есть ли более простое решение этой проблемы?
Решение
Я начну с написания вашей грамматики в нормальной форме Хомского. В настоящее время есть два правила, которые не удовлетворяют этому свойству; а именно
B->D
C->F
Наивный способ исправить это — разложить их на три правила:
B->2
B->3
C->4
Теперь ваши правила производства
A->BC
B->ED
B->2
B->3
C->4
C->FB
D->2
D->3
E->0
E->1
F->4
Решатель использую (Вот) не допускает использование номеров в качестве терминалов. Таким образом, я просто создам биективное отображение
0 <-> a
1 <-> b
2 <-> c
3 <-> d
4 <-> e
Новая целевая строка "cead" вместо "2403", Включение этого в мой решатель дает правила производства.
Enter the start Variable A
Number of productions 11
A->BC
B->d
B->ED
C->e
C->FB
E->a
D->c
D->d
F->e
E->b
B->c
Enter string to be checked : cead
A
C
A B
DB CF E BD
String can be generated
К сожалению, правила немного затенены из-за наивного исправления; Однако, я думаю, этого будет достаточно.
Другие решения
Других решений пока нет …