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

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

S → SS- (1st production rule)

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

S → () - (3rd production rule)

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

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

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

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

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

3 2
computer-science context-free-grammar

3 ответа:

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

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

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

Это совершенно правильный вывод.

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

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

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

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

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

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

1

В вашем подходе нет ничего "неправильного" - вы просто вывели другую последовательность символов для статьи Википедии.

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

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

EDIT: избитый до удара: P

1