How to show that a Dyck-Language $K$ is equals to $L$?

Question

let $L,K\subseteq \Sigma^*$ be Languages over $\Sigma=\{(,)\}$.

$L$ is defined as follows :

1- $\epsilon \in L$

2- $u,v \in L \Rightarrow uv\in L $

3- $u\in L \Rightarrow (u)\in L$

4- a String is only in $L$, if it's according to the above mentioned Rules in $L$

$K = \{w\in \Sigma^*|\: |w|_(=|w|_)\wedge \forall u,v : uv =w,|u|_(\ge|u|_)\}.$

i want to show that $L=K$, but i don't exactly understand the definition of $L$.

now i know that $K$ is the same one from https://en.wikipedia.org/wiki/Dyck_language right ?

1- What is the use of the Rule 4 in $L$ ?

2- is a String like $(^nw)^n$ in $L$ ?

3- how to show the equality of $L$ and $K$ ?

Answer 1

1. Rule 4 seems to clarify the role of the first three rules; that is, $x \in L$ if and only if $x$ can be constructed using the first three rules. One might interpret the rules as stating that "if $x$ can be constructed by the rules, then $x \in L$", without the converse statement. Rule 4 avoids this ambiguity.
2. Are you assuming $w \in L$? If so, then by rule 3, $(w) \in L$, so we can apply rule 3 to $(w)$, meaning $((w)) \in L$, etc. This repeated application of rule 3 shows that $(^n w )^n \in L$.
3. Hint: To prove that $L = K$, you need to show that for all strings $x$, $x \in L$ if and only if $x \in K$. To do this, first take any $x_L \in L$, and show that $x_L \in K$ must be true. Then, take any $x_K \in K$, and show that $x_K \in L$ must be true. You will certainly need to use the definitions of $L$ and $K$ to make these arguments.

Answer 2

$L$ is indeed the language of balanced parentheses, the one you cite is an inductive definition. Rule 4 is there to ensure that no word other than those that may be obtained with rules 1-3 is in the language.

Proving equality is trivial by structural induction. (Hint: if the parentheses are well-matched, then there must be a pair of external ones...)