Подход к поиску контекстно-свободной грамматики более сложных языков

Question

У меня проблемы с приближением к следующей проблеме.

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

{x#y | x,y in {0,1}* and |x| != |y|} 

Как лучше всего подойти к этому вопросу? Сейчас я просто использую интуицию для решения подобных вопросов, но есть ли полезные методы? то есть вы могли бы подумать о том, как будет выглядеть КПК для этого языка, а затем извлечь из этого грамматику? Есть ли способ найти грамматик G = A и B с помощью грамматик A и B?

Я изо всех сил пытаюсь увидеть, как решить эту проблему, поэтому любая помощь будет высоко ценится.

Благодарю.

Answer 1

Использование интуиции является ценной техникой. По мере того, как вы решаете больше таких проблем, ваша интуиция обостряется, и это становится легче.

Нет формального метода для преобразования описания языка в CFG (если только описание не является чем-то, что отображается на CFG, конечно, как набор правил производства). Как правило, неясно, является ли язык контекстно-независимым (хотя CFG должны соответствовать множеству ограничений, поэтому часто можно доказать, что язык не является CFG, даже полу-механически, используя подсчет аргументов.) И даже не обязательно, что пересечение двух контекстно-свободных языков не зависит от контекста, поэтому нет процедуры, которая могла бы взять два контекстно-свободных языка и сгенерировать CFG для их соединения.

Однако объединение двух контекстно-свободных языков не зависит от контекста, и CFG может быть получен механически из CFG двух языков. Так что есть возможность разбить проблемы на части.

В случае этой конкретной проблемы я предлагаю простую эвристику, которая часто будет работать для вопросов, которые вы задаете на уроках формальных языков: попытайтесь основать проблему на более простых задачах, ответ на которые вы знаете.

Как и выше, объединение двух КЛЛ не зависит от контекста. Так конкатенация, определяемая как:

L₁·L₂ = {xy | x ∈ L₁ ∧ y ∈ L₂}

Вот два подхода, оба основаны на том, чтобы создать аналогичный язык, где |х| = |у| Любая строка, где |х| ≠ |у| должно иметь больше символов либо справа, либо слева. В зависимости от вашего наклона, вы можете добавить эти дополнительные символы в середине (на одной или другой стороне разделителя) или на одном из концов. Оба эти подхода предполагают использование союза; один из них - это конкатенация, а другой - вложение.

Удачи.