Formal Languages : Exercise

Exercise 1 (Dyck Language)

Let Σ ={a1, . . . , an} ∪ {b1, . . . ,bn} be the alphabet formed by n pairs of bracket. A word w ∈ Σ* is well-bracketed if it can be reduced to ε by the rules ∀ 1 ≤ i ≤ n. ai bi → ε.

Show that the Dyck language D*n={w ∈ Σ* |w is well bracketed} is generated by the grammar : S → a1 S b1 S + . . . + an S bn S + ε.

Exercise 2 (Lukasiewicz Language)

Let Σ ={a, b}, P={S → aSS+b} and G=(Σ,{S}, P ). Let the Lukasiewicz language L be the language generated by G.

  • 1. Show that every word u ∈ L satisfy the property; (1): |u|b =|u|a + 1.
  • 2. Show that every word u ∈ L satisfy the property; (2): ∀ v prefix of u, v ≠ u:|v|a ≥ |v|b.
  • 3. Deduce that L = {u ∈ Σ* | u satisfy (1) and (2)}.
  • 4. Show that L = D*1b, where D*n is the Dyck language defined above.