CODEWITHSUNDEEP
grammarchomsky-normal-form
PTN
PTN

Reputation: 1692

Parse balanced parentheses CNF

I have a grammar S -> (S)S | empty

I converted it to a Chomsky Normal Form like this

S -> AS | empty
A -> LB
B -> SR
L -> (
R -> )

I'm not sure if I converted it correctly, but how do I parse this input ()() using the CNF

Upvotes: 0

Views: 592

Answers (1)

rici
rici

Reputation: 241861

Do the following derivation in reverse:


  S        S → AS   
→ AS       A → LB
→ LBS      L → (
→ (BS      B → SR
→ (SRS     S → ε
→ (RS      R → )
→ ()S      S → AS   
→ ()AS     A → LB
→ ()LBS    L → (
→ ()(BS    B → SR
→ ()(SRS   S → ε
→ ()(RS    R → )
→ ()()S    S → ε
→ ()()

Upvotes: 1

Related Questions