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.



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

  • $\begingroup$ I don't understand what you mean by "1 n 10" $\endgroup$ – Jens Renders Mar 14 '16 at 22:06
  • $\begingroup$ My apologies. I've just updated $\endgroup$ – 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.

  • $\begingroup$ 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) $\endgroup$ – s.ranch Mar 14 '16 at 20:33
  • $\begingroup$ 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 $\endgroup$ – Jens Renders Mar 14 '16 at 20:39
  • $\begingroup$ Ok sure, I've just edited it now. $\endgroup$ – s.ranch Mar 14 '16 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.