CODEWITHSUNDEEP
computer-sciencecontext-free-grammar
cool
cool

Reputation: 89

Context free grammar- theory of computation

I am studying for my finals & I was reading context free grammars article from wikipedia and came across following example. 

S → SS- (1st production rule)

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

S → () - (3rd production rule)

I am well aware of left and right derivation. When I tried to solve this problem I start with start symbol 

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

but when I looked the answer, it was like this

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

I am not sure what goes wrong with my answer? Is it necessary to use first production rule twice? Could anybody help me with this.

Upvotes: 2

Views: 1587

Answers (3)

asdfjklqwer
asdfjklqwer

Reputation: 3594

The article is simply giving one possible string which can be represented using that grammar... you are giving another possible string. You could use derivation to prove that those strings are valid according to the grammar (i.e. going in the reverse direction).

EDIT: Beaten to the punch :P

Upvotes: 1

SimonJ
SimonJ

Reputation: 21306

There's nothing "wrong" with your approach - you've just derived a different sequence of symbols to the Wikipedia article.

The crucial point is that it's possible to derive any sequence of matching, nested parentheses using the grammar, but not sequences like (() or )()(.

Upvotes: 2

sepp2k
sepp2k

Reputation: 370415

When I tried to solve this problem I start with start symbol

What problem? The wikipedia article doesn't pose any problem. It just shows a grammar describing the language of well-matched parentheses and gives an example of a word in that language and how to derive it.

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

That's a perfectly valid derivation.

but when I looked the answer, it was like this

That's not the answer (there was no question). It's just an example.

I am not sure what goes wrong with my answer?

There's nothing wrong with your derivation. Both ()() and ((()()))()(()) are valid words in the language.

Is it necessary to use first production rule twice?

You can apply the production rules as often as you want (assuming of course the non-terminal you want to replace is present in the term) and in any order you want. It all just depends on which word you want to derive.

Upvotes: 1

Related Questions