Регулярные выражения распознают обычные языки. Ваш язык конечный , поэтому он является регулярным по определению (вы можете написать для него регулярное выражение, объединив все слова с | между ними), но для обычных языков характерно повторения шаблонов . Конечный язык не может иметь произвольных повторений, что означает, что в вашем регулярном выражении не может быть *. Так что это не очень традиционный обычный язык. В некоторых случаях регулярное выражение для языка, в частности для конечного языка, не может быть на намного проще, чем просто перечисление всех строк языка. Это один из таких случаев. У языка есть структура, но это не структура, основанная на повторениях, поэтому сила регулярных выражений просто не соответствует задаче /
Если вы посмотрите на сложность, которая вам нужна в вашем регулярном выражении (или конечно) конечный автомат, еще один способ сопоставления с обычными языками), чтобы распознать строки вашего языка, вы можете посмотреть информацию, которую вы должны запомнить, увидев любой префикс строки.
Чтобы распознать k1k2k3k4 и отклоните k1k2k3k1, k1k2k3k2 и k1k2k3k3, информация, которую вы должны запомнить после просмотра k1k2k3, это то, что вы видели k1, k2 и k3. Таким образом, для любой последовательности ключевых слов вы должны помнить точное подмножество ключевых слов , которое было замечено до сих пор. Это примерно экспоненциальная длина видимой строки.
Если у вас есть 100 ключевых слов, после просмотра 50 из них вам нужно запомнить, какие 50, и есть K (100,50) возможных комбинаций (иначе). 100891344545564193334812497256). Вот откуда берется факториал (K (100,50) равно 100! / (50! * 50!)). Ваше регулярное выражение должно быть в состоянии различать guish столько состояний, потому что для любых двух существует суффикс, который будет разрешен одним и отклонен другим.