Gluk (Kazan)

Вообще-то множество тут одно (оно же язык). И множество счетное (без никаких там N)
Так в отношении языка регулярных выражений, хочется услышать более подробную аргументацию отнесения его к той же группе языков, что и sql с qbe (только без аргументов типа "а кудаж его").
Без тени лукавства, хочется понять Вашу логику

http://filosof.historic.ru/enc/item/f00/s05/a000517.shtml


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

записать {1, 2, и так далее} - не годится - это символ.

Ваш пример с тремя точками - не годится - это символ.
нужна "не изменяемая потом процедура" котороя будет строить это множество целиком.

можно взять набор операторов из 6 главы дейта и построить такое множество?

вот программа на языке sql для построение множества {0, 1}:
конструкции (кроме цикла) для создания потенциально большого множества я не знаю.

---
я могу записать программу для генерации мощности 3 {0,1,2}

но это уже другая программа, а нужна одна и та же.

mayton нсщл maytonSQL - это (ИМХО) не язык программирования.
а если ктонить докажет обратное, вы на его счёт переведёте 100$?
Он удостоится чести поговорить со мной в любое время суток в ICQ. Хотя я сильно сомневаюсь что его доказательство можно будет считать состоятельным.
думаю Хомски проигнорирует такое заманчивое предложение

tchingiz http://censura.ru/articles/chomskyandmind.htm


Хомский
Тип 0: языки с фразовой структурой Это самые сложные языки, которые могут быть заданы только грамматикой, относящейся к типу 0. Для распознавания цепочек таких языков требуются вычислители, равномощные машине Тьюринга. Поэтому можно сказать, что если язык относится к типу 0, то для него невозможно построить компилятор, который гарантированно выполнял бы разбор предложений языка за ограниченное время на основе ограниченных вычислительных ресурсов.
К сожалению, практически все естественные языки общения между людьми, строго говоря, относятся именно к этому типу языков. Дело в том, что структура и значение фразы естественного языка может зависеть не только от контекста данной фразы, но и от содержания того текста, где эта фраза встречается. Одно и то же слово в естественном языке может не только иметь разный смысл в зависимости от контекста, но и играть различные роли в предложении. Именно поэтому столь велики сложности в автоматизации перевода текстов, написанных на естественных языках, а также отсутствуют (и, видимо, никогда не появятся) компиляторы, которые бы воспринимали программы на основе таких языков.
Далее языки с фразовой структурой рассматриваться не будут.
Тип 1: контекстно-зависимые (КЗ) языки
Тип 1 — второй по сложности тип языков. В общем случае время на распознавание предложений языка, относящегося к типу 1, экспоненциально зависит от длины исходной цепочки символов.
Языки и грамматики, относящиеся к типу 1, применяются в анализе и переводе текстов на естественных языках. Распознаватели, построенные на их основе, позволяют анализировать тексты с учетом контекстной зависимости в предложениях входного языка (но они не учитывают содержание текста, поэтому в общем случае для точного перевода с естественного языка требуется вмешательство человека). На основе таких грамматик может выполняться автоматизированный перевод с одного естественного языка на другой, ими могут пользоваться сервисные функции проверки орфографии и правописания в языковых процессорах.
В компиляторах КЗ-языки не используются, поскольку языки программирования имеют более простую структуру, поэтому здесь они подробно не рассматриваются.
Тип 2: контекстно-свободные (КС) языки
КС-языки лежат в основе синтаксических конструкций большинства современных языков программирования, на их основе функционируют некоторые довольно сложные командные процессоры, допускающие управляющие команды цикла и условия.
В общем случае время на распознавание предложений языка, относящегося к типу 1, полиномиально зависит от длины входной цепочки символов (в зависимости от класса языка это либо кубическая, либо квадратичная зависимость). Однако среди КС-языков существует много классов языков, для которых эта зависимость линейна. Практически все языки программирования можно отнести к одному из таких классов. КС-языки подробно рассматриваются в главе 4 “Синтаксические анализаторы” данного учебника.
Тип 3: регулярные языки
Регулярные языки — самый простой тип языков. Поэтому они являются самым широко используемым типом языков в области вычислительных систем. Время на распознавание предложений регулярного языка линейно зависит от длины входной цепочки символов.
Как уже было сказано выше, регулярные языки лежат в основе простейших конструкций языков программирования (идентификаторов, констант и т. п.), кроме того, на их основе строятся многие мнемокоды машинных команд (языки ассемблеров), а также командные процессоры, символьные управляющие команды и другие подобные структуры.
Регулярные языки — очень удобное средство. Для работы с ними можно использовать регулярные множества и выражения, конечные автоматы. Регулярные языки подробно рассматриваются в главе 3 “Лексические анализаторы”.

грамматика языка sql может быть описана на yacc-е ( я сам это видел в примерах по yacc),
то есть, sql является контекстно независимым (контекстно свободным) языком

Dried GagarinЭто форум, а не колония для исправления малолетних имбецилов.
Модератор:
забанен на двое суток

XDiaBLo
Добавьте тогда уж ещё и HTML к языкам программирования... Спорить не желаю, считаю вопрос не подлежащим обсуждению, т.к. ответ однозначен и известен всем средненьким студентам.
многие считают, что компьютер кроме вычисления функций
отображающие декартово произведение целых чисел в декартово произведение целых чисел
f : Z >< ...>< Z -> Z >< ... >< Z не умеет ничего другого.
Как бы не хотелось бы средненьким студентам, журналистам и менеджерам про продажам из софтверных компаний чегото сверх этого.