grammarchomsky-normal-form

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

Solution

  • 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 → ε
→ ()()