Учитывая любой документ, я хочу иметь возможность генерировать NFA, который принимает только те слова, которые присутствуют в документе. В принципе, я хочу написать функцию, которая может динамически генерировать NFA из любого документа. Есть ли уже существующие алгоритмы, которые уже делают это?Учитывая, как создать NFA, который принимает только те слова, присутствующие в файле?
Если все, что вам нужно, это NFA без каких-либо требований, конструкция почти тривиальна.
Для каждого слова w создайте отдельную ветвь в вашей NFA с | w | + 1 состояния (не включая начальное состояние). Из состояния начала добавьте пустой переход в первое состояние, а затем добавьте переход из n-го состояния в n + 1-го состояния на n-й символ w. Выполните условие | w | + 1-го состояния.
Это даст вам DFA с таким количеством состояний, как у вас есть символы + слова в вашем файле. Если вы хотите меньше состояний, вы можете сделать что-то более многослойное, создав первый «слой» для всех первых букв во всех словах, второй «слой» для всех вторых букв во всех словах и т. Д. И добавьте переходы из состояний в слое n к состояниям в слое n + 1, если есть слова w, которые делают переходы действительными. Действительно, если вы сделаете это правильно, вы окажетесь в DFA, и это, вероятно, будет минимальным (упражнение: доказать или опровергнуть это).
Несмотря на название, большинство двигателей регулярных выражений теперь фактически являются NFA. Например, в Python вы можете использовать '\ b (word1 | word2 | word3) \ b' для соответствия списку слов. – justhalf