Welcome to our community

Be a part of something great, join today!

How can I check if the grammar is regular?

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,145
I have the following grammars and I have to check if they are regular. Could you tell me how I can check this?

$G_1:$$$ I \to aK|bL$$
$$K \to bL| \varnothing$$
$$L \to dL|cK| \varnothing$$

$G_2:$$$ I \to KL$$
$$K \to aK|bK| \varnothing$$
$$L \to cL| dL| \varnothing$$

$G_3:$$$I \to II|(I)| \varnothing$$
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,887
I have the following grammars and I have to check if they are regular. Could you tell me how I can check this?

$G_1:$$$ I \to aK|bL$$
$$K \to bL| \varnothing$$
$$L \to dL|cK| \varnothing$$

$G_2:$$$ I \to KL$$
$$K \to aK|bK| \varnothing$$
$$L \to cL| dL| \varnothing$$

$G_3:$$$I \to II|(I)| \varnothing$$
Hey!!! :eek:

What is the definition of a regular grammar?
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,145
Hey!!! :eek:

What is the definition of a regular grammar?
The rules of a regular grammar are of the form:
$$ K \to \varnothing $$
$$ K \to aK' $$

At the second rule can it be $ K \to a K $ ?

At $G_2$ we have the rule $I \to KL$, that isn't of the form of one of the above rules, so $G_2$ is not a regular grammar, is it?

And $G_3$ for the same reason ($ I \to II$ ) is not a regular grammar.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,887
The rules of a regular grammar are of the form:
$$ K \to \varnothing $$
$$ K \to aK' $$

At the second rule can it be $ K \to a K $ ?
Yes.
If you read the context of the definition of a "right regular grammar", it should say that a rule of the second type has a single non-terminal on the left side, and a terminal followed by a non-terminal on the right hand side.
Note that a regular grammar is a left regular grammar or a right regular grammar.


At $G_2$ we have the rule $I \to KL$, that isn't of the form of one of the above rules, so $G_2$ is not a regular grammar, is it?

And $G_3$ for the same reason ($ I \to II$ ) is not a regular grammar.
Correct. ;)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,145
Yes.
If you read the context of the definition of a "right regular grammar", it should say that a rule of the second type has a single non-terminal on the left side, and a terminal followed by a non-terminal on the right hand side.
Note that a regular grammar is a left regular grammar or a right regular grammar.




Correct. ;)
Great! Thanks!!! :eek:

And how can I check if the languages that these grammars generate are regular?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,887
Great! Thanks!!! :eek:

And how can I check if the languages that these grammars generate are regular?
From wiki: a regular grammar is a formal grammar that describes a regular language.

More specifically, they are the same!
Or formally: the definitions are equivalent.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,145
From wiki: a regular grammar is a formal grammar that describes a regular language.

More specifically, they are the same!
Or formally: the definitions are equivalent.
So only the language that is generated from the first grammar is regular?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,887
So only the language that is generated from the first grammar is regular?
Eh... not exactly.
The languages generated by those other grammars might have another grammar that is regular.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,145
Eh... not exactly.
The languages generated by those other grammars might have another grammar that is regular.
So do I have to find the languages that these grammars generate and then check if they are regular?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,887
So do I have to find the languages that these grammars generate and then check if they are regular?
That would be a good way to go! (Angel)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,145