Welcome to our community

Be a part of something great, join today!

Which language does this klmn-grammar generate?

evinda

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

[tex] 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 [/tex] ,

and I found that it generates the following strings:

[tex]I\rightarrow I_{kn}\rightarrow k I_{kn} n \rightarrow kknn[/tex]
[tex]I\rightarrow I_{ln}\rightarrow l I_{kn} n \rightarrow llnn[/tex]
[tex]I\rightarrow I_{km}\rightarrow k I_{km} m \rightarrow kkmm[/tex]
[tex]I\rightarrow I_{lm}\rightarrow l I_{kn} m \rightarrow llmm[/tex]

Is this right?? :confused:
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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:

[tex] 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 [/tex] ,

and I found that it generates the following strings:

[tex]I\rightarrow I_{kn}\rightarrow k I_{kn} n \rightarrow kknn[/tex]
[tex]I\rightarrow I_{ln}\rightarrow l I_{kn} n \rightarrow llnn[/tex]
[tex]I\rightarrow I_{km}\rightarrow k I_{km} m \rightarrow kkmm[/tex]
[tex]I\rightarrow I_{lm}\rightarrow l I_{kn} m \rightarrow llmm[/tex]

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

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,779
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:

[tex] 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 [/tex] ,

and I found that it generates the following strings:

[tex]I\rightarrow I_{kn}\rightarrow k I_{kn} n \rightarrow kknn[/tex]
[tex]I\rightarrow I_{ln}\rightarrow l I_{kn} n \rightarrow llnn[/tex]
[tex]I\rightarrow I_{km}\rightarrow k I_{km} m \rightarrow kkmm[/tex]
[tex]I\rightarrow I_{lm}\rightarrow l I_{kn} m \rightarrow llmm[/tex]

Is this right?? :confused:
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
Apr 13, 2013
3,720
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: [tex]I_{kn} \rightarrow kI_{kn}n[/tex] and [tex] I_{kn} \rightarrow \varnothing[/tex]
:confused: How else can I do this?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,779
Re: How to find a language generated by a given grammar

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

Let me expand your ruleset:
\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
Apr 13, 2013
3,720
Re: How to find a language generated by a given grammar

Am I misunderstanding?
Then perhaps you can clarify?

Let me expand your ruleset:
\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:
[tex]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[/tex]
[tex]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[/tex]
So is the language [tex]\{k^il^jm^in^j\}[/tex]? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,779
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:
[tex]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[/tex]
[tex]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[/tex]
So is the language [tex]\{k^il^jm^in^j\}[/tex]? :confused:
Those look like correct words. ;)
But I don't think that is the language.

Let's try to visualize it:

Grammar_klmn.png

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

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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 [tex]\{k^il^jm^in^j:i,j>0\}[/tex] or is it something else? :confused:
 
Last edited:

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,779
Re: How to find a language generated by a given grammar

Is it maybe [tex]\{k^il^jm^in^j:i,j>0\}[/tex] or is it something else? :confused:
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
Apr 13, 2013
3,720
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: [tex] \{k^{p+q}l^{r}m^{r+q}n^{p}: p,q,r \in \mathbb Z_{\ge 0} \} [/tex] ?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,779
Re: How to find a language generated by a given grammar

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

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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? :confused:
 
Last edited:

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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? :confused:
So,is the answer the languages [tex] \{k^{p+q}l^{r}m^{r+q}n^{p}: p,q,r \in \mathbb Z_{\ge 0} \} [/tex] 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
Mar 5, 2012
8,779
Re: How to find a language generated by a given grammar

So,is the answer the languages [tex] \{k^{p+q}l^{r}m^{r+q}n^{p}: p,q,r \in \mathbb Z_{\ge 0} \} [/tex] 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
Apr 13, 2013
3,720
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!!!!! (Clapping)