Нужна помощь в построении грамматики?

Question

L = ((a^n)(b^n+m)(a^m)) | n, m = 0, 1, 2...)

Я новичок в контекстно-свободной грамматике и знаю основы, но я некоторое время боролся с этим.

Для начала, я не знаю, что означает эта часть кода:

| n, m = 0, 1, 2...)

И во-вторых, как можно иметь одну и ту же переменную с разными показателями? Я чувствую, что не понимаю полную концепцию.

Редактировать: Мне также нужно уметь составлять правила для построения этой грамматики.

Редактировать: добавлен тег

Answer 1

Сначала опишите язык словами. Этот язык имеет особенно аккуратное описание: это язык всех строк, начинающихся с а, после которых идет буква b, а затем буква a, где число b равно общему числу a (с обеих сторон).

Далее, мы попытаемся придумать правило, чтобы брать строки в языке и создавать новые строки. Учитывая строку, вы можете получить следующую самую длинную строку, добавив a спереди и a b посередине, или a сзади и a b посередине. Пустая строка также на этом языке (n = m = 0), так что это может служить основой для индукции. Если мы посмотрим на это немного ближе, мы можем получить еще лучшее правило: мы можем разбить любую строку a ^ n b ^ n + m a ^ m на две строки (a ^ n b ^ n) (a ^ m b ^ m). Поскольку конкатенацию легко сделать с грамматиками, а a ^ k b ^ k легко сделать с грамматиками, это все, что нужно.

Я получаю правила ...

  S := LR
  L := empty | aLb
  R := empty | bRa

Чтобы получить, например, aabbba ...

  S := LR := aLbR := aaLbbR := aabbR := aabbbRa := aabbba

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

Что легко сделать в грамматике? Объединение языков, объединение языков, даже сопоставление пар символов (например, a ^ k b ^ k), палиндромов и т. Д.

Answer 2

Это просто математическая запись для ограничения значений n и m.Это означает, что для строки, состоящей из формы (a^n)*(b^n+m)*a^m, «n» и «m» являются двумя отдельными значениями (хотя они могут быть равными), а 0, 1, 2 ... просто означают, что они являются любым целочисленным значениембольше или равно нулю.