Ответ 1
L = {0 n 1 n: n ≥ 0} - контекстно-свободный язык.
Согласование скобок в выражении можно считать похожим на i.e.
L = {(n) n: n ≥ 0}
Есть ли примеры перекачки лемм с "реальными" языками?
лемма о перекачке является свойством обычных языков и контекстно-бесплатные языки. Но все примеры, которые я видел, это такие вещи, как:
L = {0 n 1 n 2 n: n ≥ 0}
(который, кстати, не является контекстно-свободным языком).
Но меня интересует вот что: есть ли примеры его использования с любыми удаленно реальными или полезными языками? Я не смог найти никого. Является ли это одной из тех вещей или чисто теоретической ценности без практического применения?
Ответы
Ответ 2
эта программа python действительна:
print ((((((((((((((((((((((((1))))))))))))))))))))))))
а также всех других эквивалентных операторов с равным количеством ( слева и ) с правой стороны.
Вы не можете создать регулярное выражение, чтобы убедиться в этом, поэтому вы должны использовать синтаксический анализатор.
Это совсем не теоретически. Это причина, по которой вы не можете использовать регулярное выражение для анализа HTML.
Ответ 3
Одним из практических применений является тот факт, что каждый может перестать пытаться построить конечный автомат для распознавания синтаксиса С# или Fortran.
Другим практическим применением является тот факт, что каждый может перестать пытаться построить автомат pushdown для распознавания семантики С# или Fortran. (Даже если в Fortran, если вы пропустили имя переменной, вы получите новую переменную бесплатно, новая переменная, вероятно, может не работать с операторами, которые вы кодировали, когда вы намеревались называть одну из ваших объявленных переменных.)
Ответ 4
"Является ли эта одна из тех вещей или чисто теоретическая ценность абсолютно без практического применения?"
Хмм. Какое практическое применение? Вы мудро пометили свой вопрос "компьютерная наука". Поэтому я предполагаю, что ваш вопрос должен спросить: "Это практично для компьютерной науки?
В этом случае ответ будет...
Конечно! Его преподают как один из первых способов классификации различных классов сложности языка, помимо "большого-O (whateverthehell)". Это показывает, что есть проблемы, связанные с вычислением, выходящим за рамки только времени выполнения, в этом случае некоторые модели просто не могут вычислить некоторые функции. * Это довольно малое знакомство с формальными доказательствами относительно теории автоматов.
Огромная часть компьютерной науки, которую большинство учеников в области компьютерных наук (мои сверстники), похоже, предпочитают избегать, - это Теория вычислений, классификация, которая, очевидно, подпадает под леммы.
Надеюсь, очевидный факт состоит в том, что теория вычислений, как это или нет, является основополагающей для информатики. Чтобы не понять идею разных классов сложности (большой-О сам по себе не режет ее), не будет означать смерть компьютерного ученого, но он скроет значительную часть поля с его или ее точки зрения.
* Да, обычно проблема с остановкой отображается как первая, но они никогда не получают ее в первый раз.
Что касается, возможно, более циничной интерпретации вашего вопроса, в которой вы подразумеваете "действительно ли какая-либо часть программного обеспечения действительно использует это?", мой ответ, конечно, нет. Он является частью основы вычислений, а не его приложений. Это не значит, что он пренебрегает своими приложениями, а вовсе не. Оба имеют равную, благородную ценность.