# Using a language to define a grammar

I'm currently having trouble understanding how to use a language to generate a grammar.

Using the language:

$$L=\{a^n b^m | n, m \geq 1\}$$ as an example:

I know (from my notes) that this language creates the grammar:
Grammar: G
Terminals: $a, b$
Non-terminal: $S, T$
Start symbol: $S$
Productions: $S \rightarrow Sb, S \rightarrow Tb, T \rightarrow Ta, T \rightarrow a$

But, i'm unsure how the grammar was actually determined (especially the productions) in the way that they are. I think I might have missed some information when researching but i'm unsure of what.
Could someone please point me in the right direction, or give me a brief explanation.

Thanks,

UPDATE

Given the following language:

$$L_2 = \{a^n b^{2n} c^n | 1 \leq n \leq 10\}$$

I can conclude that this is a regular language because n is bounded so i want to create a left-linear or right-linear grammar for the language

• I don't understand what you mean by "1 n 10" – Jens Renders Mar 14 '16 at 22:06
• My apologies. I've just updated – s.ranch Mar 14 '16 at 22:07

It's the other way around, the grammar defines the language. If you start with the starting symbol $S$ and apply finitly many reductions on it, you can obtain strings over the alphabeth $\{a,b\}$. For example: $$S \rightarrow Tb \rightarrow ab$$

This means that $ab \in L$ where $L$ is your language. Your language is nothing more than the set of strings that val be created with this grammar, and it's usually denoted $L(G)$ where $G$ is your grammar.

When you start from a language, and ask which grammar it is defined by, there can be many solutions, and there can be none.

To create for example a right linear grammar for the second language, you can use only these production rules: $$A \rightarrow cB$$ $$A \rightarrow c$$ $$A \rightarrow \epsilon$$

with $A, B$ nonterminals and $c$ a terminal. To make sure there is atleast one $a$ we can start with the rule $$S \rightarrow aA_1$$

Now we can either go to $B$ or add an extra $a$ $$A_1 \rightarrow aA_2 | bB_1$$ $$\vdots$$ As you can see I'm keeping track of the amount of letters used, this way I can make sure it's less than 10 for each letter.

• Ok thanks, one other question. Looking at the language in my example. Can you tell by looking at it if its a regular language (if it can be modelled using right-linear or left-linear) – s.ranch Mar 14 '16 at 20:33
• if you put this question in your question (by editing) I can edit my answer too. Thats more easy to explain than in the comments – Jens Renders Mar 14 '16 at 20:39
• Ok sure, I've just edited it now. – s.ranch Mar 14 '16 at 21:43