# Which language does this klmn-grammar generate?

#### evinda

##### Well-known member
MHB Site Helper
Also,to see if I understood it,I tried an other example.
The grammar that is given is this:

$$w\epsilon \left \{ k,l,m,n \right \}^{*}:I\rightarrow I_{kn},I_{kn}\rightarrow kI_{kn}n|I_{ln}|I_{km},I_{ln}\rightarrow lI_{ln}n|I_{lm},I_{km}\rightarrow kI_{km}m|I_{lm},I_{lm}\rightarrow lI_{lm}m|\O$$ ,

and I found that it generates the following strings:

$$I\rightarrow I_{kn}\rightarrow k I_{kn} n \rightarrow kknn$$
$$I\rightarrow I_{ln}\rightarrow l I_{kn} n \rightarrow llnn$$
$$I\rightarrow I_{km}\rightarrow k I_{km} m \rightarrow kkmm$$
$$I\rightarrow I_{lm}\rightarrow l I_{kn} m \rightarrow llmm$$

Is this right??

#### evinda

##### Well-known member
MHB Site Helper
Re: How to find a language generated by a given grammar

Also,to see if I understood it,I tried an other example.
The grammar that is given is this:

$$w\epsilon \left \{ k,l,m,n \right \}^{*}:I\rightarrow I_{kn},I_{kn}\rightarrow kI_{kn}n|I_{ln}|I_{km},I_{ln}\rightarrow lI_{ln}n|I_{lm},I_{km}\rightarrow kI_{km}m|I_{lm},I_{lm}\rightarrow lI_{lm}m|\O$$ ,

and I found that it generates the following strings:

$$I\rightarrow I_{kn}\rightarrow k I_{kn} n \rightarrow kknn$$
$$I\rightarrow I_{ln}\rightarrow l I_{kn} n \rightarrow llnn$$
$$I\rightarrow I_{km}\rightarrow k I_{km} m \rightarrow kkmm$$
$$I\rightarrow I_{lm}\rightarrow l I_{kn} m \rightarrow llmm$$

Is this right??
If it is right,how can I find the language it generates?It is more difficult than the previous one,isn't it?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Re: How to find a language generated by a given grammar

Also,to see if I understood it,I tried an other example.
The grammar that is given is this:

$$w\epsilon \left \{ k,l,m,n \right \}^{*}:I\rightarrow I_{kn},I_{kn}\rightarrow kI_{kn}n|I_{ln}|I_{km},I_{ln}\rightarrow lI_{ln}n|I_{lm},I_{km}\rightarrow kI_{km}m|I_{lm},I_{lm}\rightarrow lI_{lm}m|\varnothing$$ ,

and I found that it generates the following strings:

$$I\rightarrow I_{kn}\rightarrow k I_{kn} n \rightarrow kknn$$
$$I\rightarrow I_{ln}\rightarrow l I_{kn} n \rightarrow llnn$$
$$I\rightarrow I_{km}\rightarrow k I_{km} m \rightarrow kkmm$$
$$I\rightarrow I_{lm}\rightarrow l I_{kn} m \rightarrow llmm$$

Is this right??
It doesn't look right to me.
There is no rule $I_{kn} \to kn$ so you cannot produce the first string like that.

#### evinda

##### Well-known member
MHB Site Helper
Re: How to find a language generated by a given grammar

It doesn't look right to me.
There is no rule $I_{kn} \to kn$ so you cannot produce the first string like that.
I used the rules: $$I_{kn} \rightarrow kI_{kn}n$$ and $$I_{kn} \rightarrow \varnothing$$
How else can I do this?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Re: How to find a language generated by a given grammar

I used the rules: $$I_{kn} \rightarrow kI_{kn}n$$ and $$I_{kn} \rightarrow \varnothing$$
How else can I do this?
Am I misunderstanding?
Then perhaps you can clarify?

\begin{array}{}
I&\rightarrow &I_{kn} \\
I_{kn}&\rightarrow& kI_{kn}n&|&I_{ln}&|&I_{km} \\
I_{ln}&\rightarrow& lI_{ln}n&|&I_{lm} \\
I_{km}&\rightarrow& kI_{km}m&|&I_{lm} \\
I_{lm}&\rightarrow& lI_{lm}m&|&\varnothing \\
\end{array}

Where is $I_{kn} \rightarrow \varnothing$?

I only see $I_{lm} \rightarrow \varnothing$.

#### evinda

##### Well-known member
MHB Site Helper
Re: How to find a language generated by a given grammar

Am I misunderstanding?
Then perhaps you can clarify?

\begin{array}{}
I&\rightarrow &I_{kn} \\
I_{kn}&\rightarrow& kI_{kn}n&|&I_{ln}&|&I_{km} \\
I_{ln}&\rightarrow& lI_{ln}n&|&I_{lm} \\
I_{km}&\rightarrow& kI_{km}m&|&I_{lm} \\
I_{lm}&\rightarrow& lI_{lm}m&|&\varnothing \\
\end{array}

Where is $I_{kn} \rightarrow \varnothing$?

I only see $I_{lm} \rightarrow \varnothing$.
Oh I think I misunderstood the rules.
Now I found that the grammar generates the following strings:
$$I\rightarrow I_{kn}\rightarrow kI_{kn}n\rightarrow kI_{ln}n\rightarrow klI_{ln}nn\rightarrow klI_{lm}nn\rightarrow kllI_{lm}mnn\rightarrow kllmnn$$
$$I\rightarrow _{kn}\rightarrow kI_{kn}n\rightarrow kI_{km}n\rightarrow kkI_{km}mn\rightarrow kkI_{lm}mn\rightarrow kklI_{lm}mmn\rightarrow kklmmn$$
So is the language $$\{k^il^jm^in^j\}$$?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Re: How to find a language generated by a given grammar

Oh I think I misunderstood the rules.
Now I found that the grammar generates the following strings:
$$I\rightarrow I_{kn}\rightarrow kI_{kn}n\rightarrow kI_{ln}n\rightarrow klI_{ln}nn\rightarrow klI_{lm}nn\rightarrow kllI_{lm}mnn\rightarrow kllmnn$$
$$I\rightarrow _{kn}\rightarrow kI_{kn}n\rightarrow kI_{km}n\rightarrow kkI_{km}mn\rightarrow kkI_{lm}mn\rightarrow kklI_{lm}mmn\rightarrow kklmmn$$
So is the language $$\{k^il^jm^in^j\}$$?
Those look like correct words.
But I don't think that is the language.

Let's try to visualize it:

Does that perhaps give you a clue what the words will look like?

#### evinda

##### Well-known member
MHB Site Helper
Re: How to find a language generated by a given grammar

Those look like correct words.
But I don't think that is the language.

Let's try to visualize it:

View attachment 1808

Does that perhaps give you a clue what the words will look like?
Is it maybe $$\{k^il^jm^in^j:i,j>0\}$$ or is it something else?

Last edited:

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Re: How to find a language generated by a given grammar

Is it maybe $$\{k^il^jm^in^j:i,j>0\}$$ or is it something else?
I'm afraid it's something else.
For starters, there are 2 paths through the graph, so you will get 2 possibilities.

Let's try the upper path.
When we leave state $I_{kn}$ we have $k^p I_{ln} n^p$, where $p$ could be $0$.
When leaving state $I_{ln}$, we have made it to $k^p l^q I_{lm} n^q n^p$.
When we finally leave $I_{lm}$ with $\varnothing$, we have $k^p l^q l^r m^r n^q n^p$.

So one of the 2 possible word sets is $\{ k^p l^{q+r} m^r n^{p+q} : p,q,r \in \mathbb Z_{\ge 0} \}$.

#### evinda

##### Well-known member
MHB Site Helper
Re: How to find a language generated by a given grammar

I'm afraid it's something else.
For starters, there are 2 paths through the graph, so you will get 2 possibilities.

Let's try the upper path.
When we leave state $I_{kn}$ we have $k^p I_{ln} n^p$, where $p$ could be $0$.
When leaving state $I_{ln}$, we have made it to $k^p l^q I_{lm} n^q n^p$.
When we finally leave $I_{lm}$ with $\varnothing$, we have $k^p l^q l^r m^r n^q n^p$.

So one of the 2 possible word sets is $\{ k^p l^{q+r} m^r n^{p+q} : p,q,r \in \mathbb Z_{\ge 0} \}$.
So,the other possible word set is: $$\{k^{p+q}l^{r}m^{r+q}n^{p}: p,q,r \in \mathbb Z_{\ge 0} \}$$ ?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Re: How to find a language generated by a given grammar

So,the other possible word set is: $$\{k^{p+q}l^{r}m^{r+q}n^{p}: p,q,r \in \mathbb Z_{\ge 0} \}$$ ?
Yep!

#### evinda

##### Well-known member
MHB Site Helper
Re: How to find a language generated by a given grammar

Nice so,if I want to write the general language,do I have to write both cases?

Or can we find one formula that satisfies both cases?

Last edited:

#### evinda

##### Well-known member
MHB Site Helper
Re: How to find a language generated by a given grammar

Nice so,if I want to write the general language,do I have to write both cases?

Or can we find one formula that satisfies both cases?
So,is the answer the languages $$\{k^{p+q}l^{r}m^{r+q}n^{p}: p,q,r \in \mathbb Z_{\ge 0} \}$$ and $\{ k^p l^{q+r} m^r n^{p+q} : p,q,r \in \mathbb Z_{\ge 0} \}$ ?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Re: How to find a language generated by a given grammar

So,is the answer the languages $$\{k^{p+q}l^{r}m^{r+q}n^{p}: p,q,r \in \mathbb Z_{\ge 0} \}$$ and $\{ k^p l^{q+r} m^r n^{p+q} : p,q,r \in \mathbb Z_{\ge 0} \}$ ?
The language is the combination of the two:
$$\{k^{p+q}l^{r}m^{r+q}n^{p}: p,q,r \in \mathbb Z_{\ge 0} \} \cup \{ k^p l^{q+r} m^r n^{p+q} : p,q,r \in \mathbb Z_{\ge 0} \}$$
Or for short:
$$\{k^{p+q}l^{r}m^{r+q}n^{p},\quad k^p l^{q+r} m^r n^{p+q}\ :\ p,q,r \in \mathbb Z_{\ge 0} \}$$

#### evinda

##### Well-known member
MHB Site Helper
Re: How to find a language generated by a given grammar

The language is the combination of the two:
$$\{k^{p+q}l^{r}m^{r+q}n^{p}: p,q,r \in \mathbb Z_{\ge 0} \} \cup \{ k^p l^{q+r} m^r n^{p+q} : p,q,r \in \mathbb Z_{\ge 0} \}$$
Or for short:
$$\{k^{p+q}l^{r}m^{r+q}n^{p},\quad k^p l^{q+r} m^r n^{p+q}\ :\ p,q,r \in \mathbb Z_{\ge 0} \}$$
Great!!!!Thank you very much!!!!!