Почему {a^nb^n | n> = 0} не регулярный?
В курсе CS я беру существует пример языка, который не является регулярным:
{a^nb^n | n >= 0}
Я могу понять, что это не является регулярным, так как никакой Автомат/Машина Конечного состояния не может быть записан, который проверяет и принимает этот вход, так как это испытывает недостаток в компоненте памяти. (Исправьте меня, если я неправ),
Статья в Википедии о Регулярном языке также перечисляет этот пример, но не предоставляет (математическое) доказательство, почему это не является регулярным.
Кто-либо может просветить меня на этом и предоставить доказательство для этого или указать на меня также хороший ресурс?
2 ответа
То, что вы ищете, это лемма прокачки для регулярных языков.
Вот пример с вашей точной проблемой:
Примеры:
Пусть L = {ambm | m ≥ 1}
Тогда L не является регулярным.
Доказательство: Пусть n - как в лемме о перекачке.
Пусть w = anbn.
Пусть w = xyz, как в лемме о прокачке.
Таким образом, xy2z ∈ L, однако xy2z содержит больше a, чем b.
Должно быть:
D code = new D(x.ToString);
Я сходил с ума из-за этого. Наконец-то, думаю, я понял. В настройках проекта я правильно устанавливал права и подписи кода в правильной конфигурации Adhoc. Тем не менее, хотя там все казалось нормальным, когда я проверил «Project - > Edit Active Target» мой объект подписи кода все еще застрял в «iPhone Developer».
После переключения на правильный «iPhone Distribution» и повторной компиляции, Xcode попросил меня разрешить подписание кода в первый раз. И все скомпилировано и перенесено на мой телефон сейчас!
Надеюсь, что это поможет. Я серьезно верю, что эта проблема - ошибка или дефект на стороне Apple. Я потерял несколько часов для простой вещи, благодаря их IDE без документов...
-121--2296204-Поскольку невозможно записать конечный автомат, который будет «считать» идентичные последовательности символов «a» и «b». В двух словах FSM не могут «считать». Попробуйте представить себе такой FSM: сколько состояний вы бы дали символу 'a'? Сколько «б»? Что делать, если у вашей входной последовательности больше?
Обратите внимание, что если у вас было n < = X с X целочисленным значением, вы могли бы подготовить такую FSM (имея одну с большим количеством состояний, но все же конечное число); такие формулировки будут регулярными.