# 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 Answer

The problem seems to be that they assume you have a background in formal language theory. Here's the basics.

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.

3. This is a description of context-free grammars. It's basically a concise way of defining a set of strings over some alphabet. We say that a string is in the set if there's some set of derivation rules we can apply to get that string.

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.

The X -> Y things you see are the derivation rules. This is saying, in any string, you can replace the symbol on the left with the symbol on the right. The idea is that you keep doing this until you get a word with only lowercase letters.