Отказ
Я знаю, что формальное доказательство с использованием леммы прокачки было опубликовано выше. Тем не менее, я приведу совершенно неформальное объяснение, потому что, как мне кажется, обычно полезно иметь некоторую интуицию о проблеме, прежде чем искать формальное решение.
Общая интуиция
В общем, когда язык зависит от какого-либо рода подсчетов, он должен звонить в звонок, что он, вероятно, не является регулярным. Причина в том, что счет может стать сколь угодно большим . Вы можете увидеть это конкретно в своем примере.
Почему это не регулярно?
Представьте себе, что вы пытаетесь создать DFS для вашего языка. Вас интересует разница между числом a и суммой чисел b и c (назовите это D_abc). В DFS вся информация собирается в самом состоянии . В качестве примера рассмотрим состояние после чтения 10 последовательных a и состояния после чтения 100 последовательных a. Эти два состояния должны отличаться . Теперь, расширив этот аргумент для любого числа a (или эквивалентно любому D_abc), вы можете сделать вывод, что вам нужно бесконечное число состояний, то есть язык не является регулярным .
Бонус: почему он не зависит от контекста?
А теперь подумайте об использовании автомата. КПК позволяет вам понять сложность (бесконечного) подсчета, используя его (бесконечный) стек. В вашем примере вы можете сделать это так:
Если стек пуст (т. Е. D_abc = 0), поместите любой символ, который вы встретите, в стек (т. Е. Если a встречается D_abc <- 1, в противном случае, если b или c вдоль D_abc <- -1).
Если верхний элемент стека равен a (т. Е. D_abc> 0), если появляется a, протолкните его в стек (т. Е. D_abc <- D_abc + 1, иначе выскочит верх a из стека (т.е. D_abc <- D_abc - 1).
Аналогично, если верхний элемент равен b или c (то есть D_abc < 0), если приходит b или c, вставьте его в стек (то есть D_abc <- D_abc - 1), иначе удалите верхний элемент из стека (т.е. D_abc <- D_abc + 1).
Используя вышеприведенные правила, стек хранит счетчик D_abc в каждый момент, что и нужно, чтобы принять или не принять строку. Таким образом, вы можете сделать вывод, что язык не зависит от контекста .