Есть ли примеры прокачки лемм с «настоящими» языками?

Question

насосная лемма является свойством обычных языков и контекстно-свободных языков . Но все примеры, которые я видел, были такими:

L = {0 ⁿ 1 ⁿ 2 ⁿ : n ≥ 0}

(что, кстати, является , а не контекстно-свободным языком).

Но что меня интересует, так это: есть ли примеры его использования с какими-либо отдаленно реальными или полезными языками? Я не смог найти ни одного. Это одна из тех вещей или чисто теоретическая ценность без какого-либо практического применения?

Answer 1

L = {0 ⁿ 1 ⁿ : n ≥ 0} является языком без контекста.

Сопоставление скобок в выражении можно считать похожей формой, т.е.

L = {( ⁿ ) ⁿ : n ≥ 0}

Answer 2

эта программа на питоне действительна:

print ((((((((((((((((((((((((1))))))))))))))))))))))))

, а также все другие эквивалентные утверждения с равным количеством ( слева и ) справа.

Вы не можете создать регулярное выражение для проверки этого, поэтому вам нужно использовать синтаксический анализатор.

Это совсем не теоретически. По этой причине вы не можете использовать регулярные выражения для разбора HTML.

Answer 3

Одним из практических применений является тот факт, что каждый может прекратить попытки построить конечный автомат для распознавания синтаксиса C # или Fortran.

Другим практическим применением является тот факт, что каждый может прекратить попытки создать автомат для нажатия, чтобы распознавать семантику C # или Fortran. (Даже если в Фортране, если вы неправильно введете имя переменной, вы получите новую переменную бесплатно, новая переменная, вероятно, может не работать с операторами, которые вы закодировали, когда намеревались назвать одну из объявленных переменных.)

Answer 4

«Это одна из тех вещей или чисто теоретическая ценность без какого-либо практического применения?»

Хмм. Какое практическое применение? Вы мудро пометили свой вопрос "информатика". Итак, я полагаю, что ваш вопрос должен задаться вопросом: «Это практично для информатики?

В этом случае ответ ...

Конечно, это так! Он преподается как один из первых способов классификации различных классов сложности языка, помимо просто "большой-O (whateverthehell)". Это показывает, что существуют проблемы, касающиеся вычислений, выходящих за рамки просто времени выполнения, в этом случае некоторые модели просто не могут вычислить некоторые функции. * Это довольно слабое введение в формальные доказательства теории автоматов.

Огромная часть информатики, которую большинство студентов, изучающих информатику (мои сверстники), похоже, стремятся избегать, - это теория вычислений, классификация которой явно подпадает под действие лемм.

Надеюсь, очевидный факт заключается в том, что теория вычислений, нравится нам это или нет, является фундаментальной для компьютерных наук. Если не понять идею о различных классах сложности (сам по себе big-O на самом деле этого не делает), это не означает смерть ученого, но он скрывает значительную часть поля от его или ее взгляда.

* Да, обычно проблема остановки отображается первой, но они никогда не получают ее в первый раз.

Что касается, возможно, более циничной интерпретации вашего вопроса, в которой вы имеете в виду «действительно ли какой-либо программный продукт использует это?», Мой ответ, конечно, нет. Это часть основы вычислений, а не их приложений. Это не звучит пренебрежительно по отношению к его приложениям, совсем нет. Оба имеют равную, благородную ценность.