Могут ли формальные грамматики генерировать другие грамматики?

Я в моделях класса вычислений, и мы просто покрываем формальные грамматики. Как мы уже определили, формальная грамматика:Могут ли формальные грамматики генерировать другие грамматики?

некоторых терминальных символов
Некоторые нетерминальные символы
Символ начала
Некоторые правила производства

Учитывая, что грамматик генерировать Кажется возможным, что вы могли бы выбрать грамматику, которая создавала бы другую грамматику. Несколько минут поиска, похоже, не дают большого обсуждения в этой области. Мои вопросы в основном таковы:

Это интересный вопрос в информатике?
Можете ли вы компактные грамматики, генерируя грамматики, которые их генерируют, или сложность неприводимая?

источник

2016-03-01 Bronze

Является ли это интересным вопросом, конечно, спорным. –

@willem: если мы говорим, что вопрос $ Q $ _interesting_, если существует некоторый наблюдатель $ O $, такой, что $ O является заинтересованным в Q $, то существование этого сообщения, похоже, разрешает дебаты, при условии, что мы считают, что Бронза находится в «информатике». – rici

@Bronze: вы можете задать этот вопрос на сайте _computer science_, например http://cs.stackexchange.com. Здесь вы в основном найдете программистов. Эти наборы не являются непересекающимися, кроме как в рабочее время, но вероятность взаимодействия может быть выше. – rici

Существует, например, ряд формализмов - обозначение BNF, которые описывают грамматики и которые сами представляются строками в контекстно-свободной грамматике.

Но я не уверен, что это то, что вы ищете. Грамматика не существует (обычно) для представления одной строки; скорее, грамматика описывает (обычно бесконечный) набор строк, не приписывая никакой семантики.

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

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

источник

2016-03-01 19:58:48 rici

Вопрос о грамматике, которая генерирует другую грамматику, достаточно интересен тем, что имеет название и некоторую литературу - см. https://en.wikipedia.org/wiki/Two-level_grammar и ссылки оттуда.

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

источник

2017-01-08 21:58:56

Могут ли формальные грамматики генерировать другие грамматики?

ответ

Смежные вопросы