Пусть f (x) = 2 ^ x. Для любого положительного n, f (n + 1) - f (n)> = n.
L = {a ^ f (m)} не является регулярным. Рассмотрим строки a ^ (2 ^ x + 1). После того, как FA обрабатывает такую строку, наименьшая строка, которая приводит к принимающему состоянию, представляет собой ^ (2 ^ x - 1) длиной 2 ^ x - 1. Поэтому для каждого значения x потребуется отдельное состояние. Поскольку существует бесконечно много значений x (натуральных чисел), не существует FA для распознавания L; следовательно, L не обычный язык.