обычная/свободная от контекста грамматика

Я надеюсь, что кто-то может помочь мне понять вопрос, который у меня есть, это не домашнее задание, это просто пример вопроса, который я пытаюсь решить. Проблема состоит в том, чтобы определить грамматику, которая генерирует все суммы любого числа операндов. Например, 54 + 3 + 78 + 2 + 5... и т. д. Самый простой способ определить проблему:

non-terminal {S,B}
terminal {0..9,+,epsilon}

Rules:

S -> [0..9]S
S -> + B
B -> [0..9]B
B -> + S
S -> epsilon
B -> epsilon 

epsilon is an empty string.

Мне кажется, это должно быть правильно, поскольку вы можете рекурсивно определить первое число с помощью первого правила, затем, чтобы добавить следующее целое число, вы можете использовать второе правило, а затем определить второе целое число, используя третье правило. Затем вы можете использовать четвертое правило, чтобы вернуться к S и определить столько целых чисел, сколько вам нужно.

Это решение кажется мне обычной грамматикой, поскольку оно подчиняется правилу A -> aB или A -> a, но в примечаниях к этому вопросу говорится, что невозможно определить эту проблему, используя обычную грамматику. Может ли кто-нибудь объяснить мне, почему моя попытка неверна и почему это должно быть контекстно-свободным?

Спасибо.


grammar regular-language context-free-grammar
person user2928132    schedule 27.12.2014    source источник
comment
Сначала обратите внимание, что в вашей грамматике справа может быть +. Если первый B пуст, то 1+ является допустимым предложением, что, я думаю, вы не имеете в виду.   -  person paulotorrens    schedule 27.12.2014

Ответы (2)


arrow_upward
1
arrow_downward

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

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

Например, для механизма регулярных выражений (как в Perl или JavaScript) можно было бы легко написать /(\d+)(\+(\d+))*/.

Вы можете написать это так:

non-terminal {S,R,N,N'}
terminal {0..9,+,epsilon}

Rules:

S -> N R
S -> epsilon

N -> [0..9] N'
N' -> N
N' -> epsilon

R -> + N R
R -> epsilon

Что должно работать корректно.

person paulotorrens    schedule 28.12.2014
comment
Спасибо за ваш ответ, Пауло, ваше объяснение того, что нерегулярные грамматики, как правило, должны быть сбалансированы, имеет смысл и очень помогает. Одна вещь, которая смущает меня в предложенном вами решении, заключается в том, что я думал, что обычные грамматики могут иметь только терминал или терминал и нетерминал в правой части правила, например. А -> аБ. Ваше первое правило для S имеет два нетерминальных символа справа (также первое правило для R -> + N R). Не означает ли это, что определяемый язык является контекстно-свободным? - person user2928132; 29.12.2014
comment
Нет, язык по-прежнему обычный. На самом деле я использовал S -> N R, потому что нетерминал N определяет число. Хотя рекомендуется (при обучении) использовать первый элемент на нетерминале в качестве терминала, это не обязательно. Вы можете легко переписать его, заменив первый N на терминалы (например, S -> [0..9] N' R). То, как я написал это, позволяет избежать дублирования кода, когда он не нужен. Обратите внимание, что в середине любого выражения нет рекурсии. - person paulotorrens; 29.12.2014

arrow_upward
0
arrow_downward

Язык нормальный. Регулярное выражение будет таким:

((0|1|2|...|9)*(0|1|2|...|9)+)*(0|1|2|...|9)*(0|1|2|...|9)

Терминалы: {0,1,2,...,9,+}

"|" означает союз, а * означает закрытие звезды

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

E->E+E
E->(E)
E->F
F-> 0F | 1F | 2F | ... | 9F | 0 | 1 | ... | 9
person abbaasi    schedule 28.12.2014
comment
Спасибо за ваш ответ, я думаю, что начинаю понимать, один вопрос, который у меня есть по поводу вашего контекстно-свободного примера, заключается в том, что из-за того, что у вас есть правило E -> E + E, язык может быть двусмысленным? - person user2928132; 29.12.2014
comment
На самом деле грамматика, которую я написал, неоднозначна, потому что, например, строка 1+2+3 имеет два разных дерева вывода. Язык НЕ неоднозначен, так как мы можем написать для него недвусмысленную грамматику. - person abbaasi; 31.12.2014