Skip to main content
1 of 5
fade2black
  • 9.9k
  • 2
  • 25
  • 36

In fact you are given two languages

  1. $L_1$ defined as a set of strings of balanced parentheses.
  2. $L_2$ defined as a set of strings with equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'

You have to prove that these two languages/sets are equal. One way to prove it is to demonstrate that the grammar you indicated in your post does generate both languages.

Another way is to prove $L_1 \subset L_2$ and $L_2 \subset L_1$.

fade2black
  • 9.9k
  • 2
  • 25
  • 36