Наидобрейшего всем времени суток. Не знал, в какую ветвь запостить вопрос, решил сюда.

Предположим, что есть некоторое множество логических и арифметических операций, допустимых для данного вычислительного устройства. Т.е., помимо элементарных "И", "ИЛИ", "НЕ" в него входят умножители, сумматоры, делители. Кроме этого, существует набор правил, позволяющих реализовывать ограниченный набор математических алгоритмов (например, свертка, ДПФ, Z-преобразование). Можно ли, формально, считать эту совокупность грамматикой? Если не затруднит — аргументированно.

P.S. не уверен, что описал понятно, т.к. не являюсь специалистом в области формальных грамматик . Если что — уточню. Заранее спасибо.

Здравствуйте, v.tatischev, Вы писали:

VT>Наидобрейшего всем времени суток. Не знал, в какую ветвь запостить вопрос, решил сюда.

VT>Предположим, что есть некоторое множество логических и арифметических операций, допустимых для данного вычислительного устройства. Т.е., помимо элементарных "И", "ИЛИ", "НЕ" в него входят умножители, сумматоры, делители. Кроме этого, существует набор правил, позволяющих реализовывать ограниченный набор математических алгоритмов (например, свертка, ДПФ, Z-преобразование). Можно ли, формально, считать эту совокупность грамматикой? Если не затруднит — аргументированно.

VT>P.S. не уверен, что описал понятно, т.к. не являюсь специалистом в области формальных грамматик . Если что — уточню. Заранее спасибо.

Формальная (порождающая) грамматика определяется четверкой:
<E, N, P, S>,
где
E — множество терминалов;
N — множество нетерминалов;
P — конечное множество правил вывода α → β, где α — цепочка из нетерминалов и терминалов, в которой обязательно присутствует один нетерминал; β — произвольная цепочка из терминалов и нетерминалов;
S — стартовый (начальный) символ из N.

То есть если ты определишь все указанные элементы, то получишь формальную грамматику.

Ссылка по теме — http://ru.wikipedia.org/wiki/Формальная_грамматика. Здесь даже понятней написано =)

Здравствуйте, Alexey Zasimov, Вы писали:
AZ>Формальная (порождающая) грамматика определяется четверкой:
AZ> <E, N, P, S>,
AZ>где
AZ> E — множество терминалов;
AZ> N — множество нетерминалов;
AZ> P — конечное множество правил вывода α → β, где α — цепочка из нетерминалов и терминалов, в которой обязательно присутствует один нетерминал; β — произвольная цепочка из терминалов и нетерминалов;
AZ> S — стартовый (начальный) символ из N.
AZ>То есть если ты определишь все указанные элементы, то получишь формальную грамматику.

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

Здравствуйте, v.tatischev, Вы писали:

VT>Здравствуйте, Alexey Zasimov, Вы писали:
AZ>>Формальная (порождающая) грамматика определяется четверкой:
AZ>> <E, N, P, S>,
AZ>>где
AZ>> E — множество терминалов;
AZ>> N — множество нетерминалов;
AZ>> P — конечное множество правил вывода α → β, где α — цепочка из нетерминалов и терминалов, в которой обязательно присутствует один нетерминал; β — произвольная цепочка из терминалов и нетерминалов;
AZ>> S — стартовый (начальный) символ из N.
AZ>>То есть если ты определишь все указанные элементы, то получишь формальную грамматику.

VT>Спасибо за ответ.
VT>Определение то я читал, но меня, как НЕ специалиста в данном вопросе, смущает тот факт, что умножитель, сумматор и т.п. являются элементами, уже состоящими из элементарных логических устройств. Ну и ограниченность правил.

Структура умножителя, сумматора и любого другого объекта никак ни относится к формальным грамматикам. Я всего лишь попытался ответить на вопрос

VT> Можно ли, формально, считать эту совокупность грамматикой?

Формально можно считать формальной грамматикой то, что сводится к вышеобозначенной четверке. То есть если ты умножители, сумматоры и любые другие объекты сможешь запихнуть в рамки такой формальной структуры, то получишь формальную грамматику.

Пока непонятно, какую ты задачу решаешь, то есть что хочешь получить в результате. Если объяснишь, беседа получится более конструктивной.

Здравствуйте, Alexey Zasimov, Вы писали:
AZ>Пока непонятно, какую ты задачу решаешь, то есть что хочешь получить в результате. Если объяснишь, беседа получится более конструктивной.
Ну, в общем-то, не совсем я решаю. Попробую по-порядку.
С одной стороны, у нас есть FPGA Xilinx с аппаратно реализованными примитивами для DSP. Откуда, собственно, и взялись сумматоры, умножители и т.п. С другой стороны — есть математик, который не является специалистом в цифровой схемотехнике, однако хорошо знает мат. аппарат. Есть идея разработки генератора схемотехнических модулей на основе мат. формул записанных, условно, языком TeX. В общем и целом как решать такую задачу практически я представляю, но братец мой пытается диссер защитить, а его профЭссора дюже интересуют формальные грамматики. Вот, собственно, и все. Жду уточняющих вопросов

Здравствуйте, v.tatischev, Вы писали:

VT>Здравствуйте, Alexey Zasimov, Вы писали:
AZ>>Пока непонятно, какую ты задачу решаешь, то есть что хочешь получить в результате. Если объяснишь, беседа получится более конструктивной.
VT>Ну, в общем-то, не совсем я решаю. Попробую по-порядку.
VT>С одной стороны, у нас есть FPGA Xilinx с аппаратно реализованными примитивами для DSP. Откуда, собственно, и взялись сумматоры, умножители и т.п. С другой стороны — есть математик, который не является специалистом в цифровой схемотехнике, однако хорошо знает мат. аппарат. Есть идея разработки генератора схемотехнических модулей на основе мат. формул записанных, условно, языком TeX. В общем и целом как решать такую задачу практически я представляю, но братец мой пытается диссер защитить, а его профЭссора дюже интересуют формальные грамматики. Вот, собственно, и все. Жду уточняющих вопросов

Если речь идет о создании системы типа ECad (http://en.wikipedia.org/wiki/Electrical_CAD), то тогда схему электронного устройства можно описывать при помощи формального языка =)

Здравствуйте, Alexey Zasimov, Вы писали:

AZ>Если речь идет о создании системы типа ECad (http://en.wikipedia.org/wiki/Electrical_CAD), то тогда схему электронного устройства можно описывать при помощи формального языка =)

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

ОФТОП: Вообще, для меня загадка, зачем лезть в область, в которой ничего не понимаешь (но которую знаю я) и пытаться скрестить ее с другой областью (в которой я ничего не понимаю, не компиляторшик)

Здравствуйте, v.tatischev, Вы писали:
VT>Предположим, что есть некоторое множество логических и арифметических операций, допустимых для данного вычислительного устройства. Т.е., помимо элементарных "И", "ИЛИ", "НЕ" в него входят умножители, сумматоры, делители. Кроме этого, существует набор правил, позволяющих реализовывать ограниченный набор математических алгоритмов (например, свертка, ДПФ, Z-преобразование). Можно ли, формально, считать эту совокупность грамматикой? Если не затруднит — аргументированно.

Грамматикой называется любое конечное описание формального языка. Формальный язык задается как множество цепочек, не обязательно конечное или непустое. Для задания бесконечного языка необходим какой-то конечный способ описания законов (синтаксических отношений) между символами цепочек данного языка. Если такие законы существуют и их можно описать конечным образом, то такое описание, задающее язык, называется грамматикой. Если язык конечен, то сам язык будет также и своей грамматикой. Пример: язык L = {a^nb^n | N \in N+} (N+ -- натуральный ряд без нуля) -- это грамматика. Для языка L' = {aa, bbb, c} он же и есть грамматика.

Есть еще вопрос: для всякого ли языка имеется грамматика или нет? Оказывается, для большего числа языков над данным алфавитом вообще нельзя построить никакой грамматики. Точное доказательство этого факта я здесь приводить не буду, приведу только сам принцип. Язык может быть описан грамматикой только, если имеется конечный набор законов, которым удовлетворяют все цепочки этого языка. Если язык есть просто случайный бесконечный набор цепочек, то его никакой грамматикой описать нельзя.

В математике рассматривают строгие формальные объекты, поэтому хочется рассматривать и грамматики, как такие объекты. Приходим к понятию "формальная грамматика". Формальная грамматика -- это строгое описание синтаксических отношений, которым удовлетворяют все цепочки данного языка. В этом смысле, грамматику можно назвать онтологией языка. Обычно интересны не произвольные формальные описания, но описания в рамках какого-то одного формализма, метода. Такие формализмы называют еще синтаксическими теориями. В качестве примеров можно привести порождающие грамматики Хомского, автоматные грамматики, язык регулярных выражений, категориальные грамматики, окрестностные грамматики, формальные степенные ряды над языками и много еще чего.

Алгоритмически, можно выделить три способа задания языка грамматикой:
1. Распознающие грамматики. Это устройство (алгоритм), которому на вход передается цепочка, а устройство в ответ печатает "да", если цепочка принадлежит языку, и "нет" -- в противном случае.
2. Перечисляющие грамматики. Это устройства, которые одну за другой печатают все цепочки языка. Понятно, если язык бесконечный, то процесс печати никогда не закончится.
3. Порождающие грамматики. Это устройства, которые по заказу могу напечатать (породить) любую цепочку языка.

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

Все это подробно и разжевано можно прочитать в моем учебнике, который я написал по курсу, который читаю для студентов РГГУ: В.А. Лапшин. Лекции по математической лингвистике. М.: Научный Мир, 2010.

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

Здравствуйте, mefrill, Вы писали:
Очень подробное описание, спасибо.

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

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

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

Здравствуйте, v.tatischev, Вы писали:

VT>Здравствуйте, Alexey Zasimov, Вы писали:
AZ>>Пока непонятно, какую ты задачу решаешь, то есть что хочешь получить в результате. Если объяснишь, беседа получится более конструктивной.
VT>Ну, в общем-то, не совсем я решаю. Попробую по-порядку.
VT>С одной стороны, у нас есть FPGA Xilinx с аппаратно реализованными примитивами для DSP. Откуда, собственно, и взялись сумматоры, умножители и т.п. С другой стороны — есть математик, который не является специалистом в цифровой схемотехнике, однако хорошо знает мат. аппарат. Есть идея разработки генератора схемотехнических модулей на основе мат. формул записанных, условно, языком TeX. В общем и целом как решать такую задачу практически я представляю, но братец мой пытается диссер защитить, а его профЭссора дюже интересуют формальные грамматики. Вот, собственно, и все. Жду уточняющих вопросов
Как интересно..Если грамматику определять классически
Формальная (порождающая) грамматика определяется четверкой:
<E, N, P, S>,
где
E — множество терминалов;
N — множество нетерминалов;
P — конечное множество правил вывода α → β, где α — цепочка из нетерминалов и терминалов, в которой обязательно присутствует один нетерминал; β — произвольная цепочка из терминалов и нетерминалов;
S — стартовый (начальный) символ из N.

То правила вывода P не могут описать все варианты схем.. А вот если правил вывода заменить предикатами (путь тоже P), то классическиое определение это частный случай когда предикаты выглядят как правила вывода. Тогда сехемы можно рассматривать как предикаты специального вида.. Получатся не совсем классические грамматики но можно придумать специальный вид предикатов описывающий электронные схемы.. Там есть хорошее поле для исследований.. И вид предиктаов есть.. И даже трнслятор продуман...Но работа совсем не детская..

Здравствуйте, mefrill, Вы писали:

M>Здравствуйте, v.tatischev, Вы писали:
VT>>Предположим, что есть некоторое множество логических и арифметических операций, допустимых для данного вычислительного устройства. Т.е., помимо элементарных "И", "ИЛИ", "НЕ" в него входят умножители, сумматоры, делители. Кроме этого, существует набор правил, позволяющих реализовывать ограниченный набор математических алгоритмов (например, свертка, ДПФ, Z-преобразование). Можно ли, формально, считать эту совокупность грамматикой? Если не затруднит — аргументированно.

M>Грамматикой называется любое конечное описание формального языка. Формальный язык задается как множество цепочек, не обязательно конечное или непустое. Для задания бесконечного языка необходим какой-то конечный способ описания законов (синтаксических отношений) между символами цепочек данного языка. Если такие законы существуют и их можно описать конечным образом, то такое описание, задающее язык, называется грамматикой. Если язык конечен, то сам язык будет также и своей грамматикой. Пример: язык L = {a^nb^n | N \in N+} (N+ -- натуральный ряд без нуля) -- это грамматика. Для языка L' = {aa, bbb, c} он же и есть грамматика.

Тут же очевидно что требуются не цепочки.. Вернее можно назвать и цепочки, но они будут не линейные, а могут иметь соединения-разветвления. Интересная задача..

Здравствуйте, v.tatischev, Вы писали:

VT>Здравствуйте, mefrill, Вы писали:
VT>Очень подробное описание, спасибо.

VT>"С этой точки зрения, Ваш способ описания языка -- это грамматика и даже целый формализм, такой "логический" подход к описанию языка."
VT>Если рассматривать практическую реализацию, то формализма в задаче больше чем самого языка, если так можно выразиться

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

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

> математических алгоритмов (например, свертка, ДПФ, Z-преобразование). Можно ли,
> формально, считать эту совокупность грамматикой? Если не затруднит —
> аргументированно.

Нет, грамматика -- совсем другое понятие. Это из лингвистики.
Это набор правил, позволяющих сказать, является ли данное сообщение
на каком-то языке валидным для этого языка.
Грамматика определяет язык.

То, что ты имееш в виду, видимо -- функциональная полнота по Тьюрингу.

Если ты опишеш какими-то правилами (неважно, какими) все возможные
наборы алгоритмов, допустимые для этого устройства, тогда эти
правила будут грамматикой.

Здравствуйте, v.tatischev, Вы писали:

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

Не обязательно водить языковую структуру к цепочкам. В лингвистике цепочки вообще очень редко рассматриваются, обычно рассматриваются деревья, т.е. графы. Тогда язык будет произвольным набором деревьев. Формализмы описания синтаксических деревьев имеются в большом количестве, можно почитать по этому поводу Гладкого: А.В. Гладкий. Синтаксические структуры естественного языка. М.: Издательство ЛКИ, 2007. Грамматиками деревьев занимался Борщев, почитайте его доклад на Диалоге по окрестностным грамматикам, может пригодится и сделает вещи яснее: http://www.dialog-21.ru/Archive/2005/Borschev%20V/BorschevV.htm. С деревьями все то же самое, что и с цепочками, только основная структура сложнее немного.

Здравствуйте, batu, Вы писали:
B>Тут же очевидно что требуются не цепочки.. Вернее можно назвать и цепочки, но они будут не линейные, а могут иметь соединения-разветвления. Интересная задача..

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

Здравствуйте, mefrill, Вы писали:

M>Здравствуйте, batu, Вы писали:
B>>Тут же очевидно что требуются не цепочки.. Вернее можно назвать и цепочки, но они будут не линейные, а могут иметь соединения-разветвления. Интересная задача..

M>Кстати, а почему не цепочки? Если в качестве языка взять траектории, (что есть траектории?)
т.е. наборы состояний (или чего-то еще) (Чего еще?)
, которые проходит устройство в процессе каждого (зачем каждого?)
вычисления, то вполне себе язык получается и его грамматика (не понял.. с каких это дел устройство или состояние стало грамматикой?)
-- конкретное устройство.(Этих устройств всего ничего. Машина тьюринга, да с магазинной памятью)
В классической вычислительной задаче в качестве цепочек рассматриваются входные данные, например, записанные на ленте машины Тьюринга. Там это называется проблемой (программой)
, а языком данной машины Тьюринга называют тем проблемы, на которые машина дает положительный ответ. (а что такое положительный ответ? Насколько я понимаю ответа вообще может не быть)

Здравствуйте, v.tatischev, Вы писали:

VT>Предположим, что есть некоторое множество логических и арифметических операций, допустимых для данного вычислительного устройства. Т.е., помимо элементарных "И", "ИЛИ", "НЕ" в него входят умножители, сумматоры, делители. Кроме этого, существует набор правил, позволяющих реализовывать ограниченный набор математических алгоритмов (например, свертка, ДПФ, Z-преобразование). Можно ли, формально, считать эту совокупность грамматикой? Если не затруднит — аргументированно.

Речь идёт о том, как построить грамматику языка, описывающего валидные схемы? (И не описывающего невалидные) (и как сделать парсер такого языка)
Начнём с того, что язык этот — контекстно-зависимый.
Поэтому — либо у нас будет классический трёхступенчатый парсер (лексер, парсер синтаксиса, семантический блок), причём лексер регулярный, а синтаксис КС или даже регулярный; либо попробуем выразить семантику средствами КЗ-грамматики. То есть, по сути, алгоритм семантики перепишем на языке машины Поста.
(Конечно, тот факт, что машина Поста эквивалентна машине Тьюринга, должен нас вдохновить... но подвиг получится сумрачный).

Здравствуйте, Кодт, Вы писали:

К>Речь идёт о том, как построить грамматику языка, описывающего валидные схемы? (И не описывающего невалидные) (и как сделать парсер такого языка)

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

Здравствуйте, v.tatischev, Вы писали:

VT>Предположим, что есть некоторое множество логических и арифметических операций, допустимых для данного вычислительного устройства. Т.е., помимо элементарных "И", "ИЛИ", "НЕ" в него входят умножители, сумматоры, делители. Кроме этого, существует набор правил, позволяющих реализовывать ограниченный набор математических алгоритмов (например, свертка, ДПФ, Z-преобразование). Можно ли, формально, считать эту совокупность грамматикой? Если не затруднит — аргументированно.

Зачем пытаться это в виде грамматики изобразить? Это же форменная TRS: http://en.wikipedia.org/wiki/Term_rewriting

Здравствуйте, mefrill, Вы писали:

К>>Речь идёт о том, как построить грамматику языка, описывающего валидные схемы? (И не описывающего невалидные) (и как сделать парсер такого языка)

M>А что такое "язык валидных схем"? Схема, вроде, не цепочка.

Язык, описывающий валидные схемы. А не язык валидных схем.

M>Надо алгоритм, который каждую схему в линейное представление преобразует, а также обратный алгоритм. В общем, взаимооднозначное соответствие между множеством всех валидных схем и некоторым формальным языком цепочек.

Не надо взаимной однозначности.
Каждой цепочке соответствует схема, а каждой схеме может соответствовать множество цепочек.
(Простой пример: от количества пробелов и комментариев в исходнике результат компиляции не зависит).

Я не уверен, нужен ли именно алгоритм, или мы можем для спортивного интереса остановиться на каком-то неконструктивном соответствии

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

Оставим за кадром вопрос, реализует ли конкретная схема конкретную вычислительную задачу. Для систем без состояния это NP-полная проблема SAT, для систем с состоянием вообще можно споткнуться о проблему остановки. Будем считать, что уж чего-чего, а Garbage In Garbage Out схема реализует.

Но есть базовые критерии схемотехники: правила коммутации элементов. Не должно быть висячих входов, не должно быть соединённых между собой выводов.
(Если, конечно, элементная база не умеет работать с высоким сопротивлением, или с двунаправленными портами).


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

Тут я вижу вот какую сложность.
Для парсера нет проблем убедиться, что все элементы идентифицированы уникально. Мы заводим список встреченных идентификаторов и проверяем, что очередной идентификатор там ещё не встречался.
А для генератора — либо мы вводим правила проб и ошибок, достаточно простые, но зацикливающие машину; либо пишем затейливый алгоритм, порождающий очередное уникальное имя с оглядкой на все существующие.
Пробы и ошибки выглядят так:

ListIds --> ( Ids )

( Ids ) --> ( )
или
( Ids ) --> ( Ids + Id )

Id --> куча букв и цифр

( <ids1...> <id> <ids2...> + <id> ) --> ( <ids1...> <id> <ids2...> )
иначе
( <ids...> + <id> ) --> ( <ids...> , <id> )

Зацикливание идёт так: родили очередной Id, дописали +Id в цепочку, обнаружили, что он там уже есть, удалили +Id из цепочки, вернулись в исходное положение.

В общем, здесь богатое поле для знатоков формальных языков, теории алгоритмов и всего такого.