# Help understanding formal language notation

I am reading this text and it is making absolutely no sense to me. It as if it assumed I will understand. Not to mention the writer apparently had a book made and his grammar is poor. Some of the plain English sentences do not even make sense or have the letter s on the end of words where they should not be. please help me understand this:

Language generators. A language generator is a device that can be used to generate the sentences of a language. A generator seems to be a device of limited usefulness as a language descriptor. Generators can more easily read and understand them. A language generation method constructs a language generator G and capable of generating a string of language by a process called derivation. For example, consider a language L over alphabet

∑ = {a, b}

L= {a^n, b^n|n ≥ 1}

G = { s -> asb s -> ab s -> 3(i need to turn this symbol the opposite direction)}

W = aaa bbb

Derivation:

S ⇒ asb ⇒ aasbb ⇒ aaabbb

i.e., S ⇒ aaabbb It means we have derived aaabbb starting from start symbol S using the rules of language generator G in finite number of steps.

• If this is indeed a faithful transcription of the original wording, I sympathize with you. – Rick Decker Oct 26 '14 at 21:29
• Please, don't post the same question to multiple sites. – svick Oct 27 '14 at 2:31

1. $\Sigma$ is the symbol which is traditionally used for an alphabet. When you're talking about strings, you always have a finite set of symbols that can be in those strings. Here we use $\Sigma=\{a,b\}$ to say that all our strings are binary, that is, they only contain the letters $a$ and $b$. We could have just as easily chosen $0,1$ or $\vee, \wedge$ or any other symbols we like. We just need a finite set of symbols.
2. $\epsilon$ is the empty string, the string of length 0. Sometimes you'll see this as $\lambda$, which is confusing, so be prepared for either. In a programming language like C, you'd see this written as "". It has the property that when you append it to the beginning or end of a word, it gives you that same word.
The derivation rules basically are a way of generating strings. The idea is that, you start with a special start symbol, usually called $S$. We have upper and lowercase letters, called non-terminals and terminals. We keep applying rules until we only have lowercase letters left.