Контекстно-бесплатная грамматика-теория вычислений

Question

Я готовлюсь к выпускным экзаменам и читаю статью по контекстной грамматике из Википедии и наткнулся на следующий пример.

S → SS- (1st production rule)

S → (S) - (2nd production rule)

S → () - (3rd production rule)

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

S-> SS -> (S)S-> ()S-> ()(S) -> ()() 

но когда я посмотрел ответ, это было так

S → SS → SSS → (S)SS → ((S))SS → ((SS))S(S)
→ ((()S))S(S) → ((()()))S(S) → ((()()))()(S)
→ ((()()))()(())

Я не уверен, что не так с моим ответом? Нужно ли использовать первое правило производства дважды? Может ли кто-нибудь помочь мне с этим.

Answer 1

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

Answer 2

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

РЕДАКТИРОВАТЬ: Удар в удар: P

Answer 3

Когда я пытался решить эту проблему, я начинал с символа запуска

Какая проблема? Статья в Википедии не представляет никаких проблем. Он просто показывает грамматику, описывающую язык хорошо подобранных скобок, и дает пример слова на этом языке и как его получить.

S-> SS -> (S)S-> ()S-> ()(S) -> ()() 

Это совершенно верный вывод.

но когда я посмотрел ответ, это было так

Это не ответ (вопросов не было). Это просто пример.

Я не уверен, что не так с моим ответом?

В вашем происхождении нет ничего плохого. ()() и ((()()))()(()) являются допустимыми словами в языке.

Необходимо ли дважды использовать первое правило производства?

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