Formal Definition
Let Σ = { } be the alphabet consisting of the symbols and let Σ∗ denote its Kleene closure. For any element u ∈ Σ∗ with length |u| we define partial functions insert : Σ∗ × (N ∪ {0}) → Σ∗ and delete : Σ∗ × N → Σ∗ by
- insert(u, j) = u with "" inserted into the jth position
- delete(u, j) = u with "" deleted from the jth position
with the understanding that insert(u, j) is undefined for j > |u| and delete(u, j) is undefined if j > |u| − 2. We define an equivalence relation R on Σ∗ as follows: for elements a, b ∈ Σ∗ we have (a, b) ∈ R if and only if there exists a finite sequence of applications of the insert and delete functions starting with a and ending with b, where the empty sequence is allowed. That the empty sequence is allowed accounts for the reflexivity of R. Symmetry follows from the observation that any finite sequence of applications of insert to a string can be undone with a finite sequence of applications of delete. Transitivity is clear from the definition.
The equivalence relation partitions the language Σ∗ into equivalence classes. If we take ε to denote the empty string, then the language corresponding to the equivalence class Cl(ε) is called the Dyck language.
Read more about this topic: Dyck Language
Famous quotes containing the words formal and/or definition:
“The spiritual kinship between Lincoln and Whitman was founded upon their Americanism, their essential Westernism. Whitman had grown up without much formal education; Lincoln had scarcely any education. One had become the notable poet of the day; one the orator of the Gettsyburg Address. It was inevitable that Whitman as a poet should turn with a feeling of kinship to Lincoln, and even without any association or contact feel that Lincoln was his.”
—Edgar Lee Masters (18691950)
“No man, not even a doctor, ever gives any other definition of what a nurse should be than thisdevoted and obedient. This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (18201910)