MHB Which language does this klmn-grammar generate?

[evinda]

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]

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?

 

[I like Serena]

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]

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?

 

[I like Serena]

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?

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]

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:
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\}?

 

[I like Serena]

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:

View attachment 1808

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

 

[evinda]

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:

https://www.physicsforums.com/attachments/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?

 

[I like Serena]

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]

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} \} ?

 

[I like Serena]

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! :D

 

[evinda]

Re: How to find a language generated by a given grammar

Yep! :D

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?

 

[evinda]

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} \}$ ?

 

[I like Serena]

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]

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)