# How can I check if the grammar is regular?

#### mathmari

##### Well-known member
MHB Site Helper
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 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!!!

What is the definition of a regular grammar?

#### mathmari

##### Well-known member
MHB Site Helper
Hey!!!

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

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

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Great! Thanks!!!

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

MHB Site Helper