Поиск контекстно-свободной грамматики (CFG)

Дайте контекстно-свободную грамматику H, которая генерирует язык

 M = {a^m
b^n
| 2m > n > m}.
‘

Подсказка: m не может быть равно 0, потому что в этом случае 2m = m. m не может быть 1, потому что в этом случае 2 > n > 1 такого натурального числа n не существует. Итак, самая короткая строка в языке M — это aabbb. Для более длинных строк вам нужно убедиться, что количество n bs и количество m as удовлетворяют условию 2m > n > m.


context-free-grammar formal-languages automata-theory
person Satya    schedule 18.10.2017    source источник
comment
Если вам нужна помощь с этим домашним заданием, вам нужен cs.stackexchange.com.   -  person Davis Herring    schedule 19.10.2017
comment
Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что он не относится к переполнению стека и принадлежит другому веб-сайту, возможно, cs.stackexchange. ком .   -  person Patrick Trentin    schedule 19.10.2017
comment
@DavisHerring: Этот вопрос уже задавали на Computer Science, возможно, тем же автором, и почти сразу же закрыли, как это бывает, как кросспост , но также и потому, что Информатика настоятельно не рекомендует делать за меня домашние задания.   -  person rici    schedule 19.10.2017
comment
@rici: Согласен. Я не говорил, что это будет тепло встречено, и назвал это домашним заданием явно не просто так.   -  person Davis Herring    schedule 20.10.2017
comment
@DavisHerring: Возможно, для do-my-homework.stackexchange.com существует рынок, но, насколько мне известно, он даже не находится в бета-версии. (Хотя меня часто удивляет толерантность пользователей математики.) Обычно я стараюсь не рекомендовать использование Информатика для вопросов, которые явно не соответствуют стандартам для этого сайта; это просто создает дополнительную работу для модераторов-добровольцев.   -  person rici    schedule 20.10.2017
comment
@rici: Достаточно честно. Быть не по теме кажется более фундаментальным (и более объективным, поскольку это не зависит от стандартов других сайтов), чем плохое исследование (также известное как домашнее задание), но я постараюсь не забывать отдавать предпочтение последнему, когда это может быть вредно. поступить иначе.   -  person Davis Herring    schedule 20.10.2017
comment
@rici делает мою домашнюю работу для меня здесь тоже не по теме, как ни странно, вопрос все еще открыт, за него проголосовали и даже ответили ..   -  person Patrick Trentin    schedule 28.10.2017

Ответы (1)


arrow_upward
1
arrow_downward

Мы знаем, что aabbb есть в языке, поэтому S -> aabbb неплохое начало. Как мы можем получить более длинные строки в языке? Что ж, нам нужно сохранить 2m > n > m. Самые короткие строки (для заданного числа a) в этом языке содержат на одну b больше, чем a, так что мы можем предположить, что S -> aSb не является плохой догадкой; он обязательно генерирует строки на нашем языке, а именно самые короткие (для заданного числа as). Точно так же в самых длинных строках нашего языка на одну b меньше, чем в два раза больше a, поэтому S -> aSbb также безопасен, поскольку генерирует самые длинные строки (для заданного количества a). Наша грамматика пока такова:

S -> aabbb
S -> aSb
S -> aSbb

Каждое производство после первого добавляет один a и один или два b. Второе производство может использоваться отдельно для генерации самых коротких строк (для заданного числа as), а третье, когда используется отдельно, генерирует самые длинные строки (для заданного числа as). Как насчет строк между самой короткой и самой длинной? Можно ли использовать эти произведения для получения всех этих строк?

Они могут. Вы можете доказать это по индукции. Вы должны показать, что все строки длины n (1) в языке генерируются грамматикой и (2) генерируются грамматикой, находятся в языке.

Базовый случай: самая короткая строка в языке — aabbb, и она генерируется грамматикой.

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

Шаг индукции: мы должны показать, что грамматика генерирует все и только строки языка для любой строки длины k + 1. Мы уже утверждали, что грамматика не может создать строку не на языке; используя только вторую продукцию, вы получаете n = m + 1, а используя только третью продукцию, вы получаете n = 2m - 1. Чтобы увидеть, что он генерирует все строки в языке, вспомните, что любая строка в языке начинается как минимум с двух a и заканчивается как минимум тремя b. Таким образом, это может быть записано как aaxbbb. Можно показать, что если эта строка на языке, то одно или оба из axbb и/или axb также должны быть на этом языке.

  1. axbb is in L if 2(m - 1) > n - 1 > m - 1, or 2m - 1 > n > m
  2. axb is in L if 2(m - 1) > n - 2 > m - 1, or 2m > n > m + 1.

Поскольку в каждом случае, начиная с базового, у нас есть хотя бы один из 2m - 1 > n и/или n > m + 1, один из них также находится в L. По предположению индукции грамматика порождает его; и одно из произведений грамматики произведет из него исходную строку длины k + 1. Таким образом, грамматика генерирует все строки в L.

person Patrick87    schedule 19.10.2017