MHB How can I check if the grammar is regular?

[mathmari]

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

 

[I like Serena]

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]

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.

 

[I like Serena]

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]

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?

 

[I like Serena]

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]

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?

 

[I like Serena]

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]

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?

 

[I like Serena]

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]

That would be a good way to go! (Angel)

Ok! Thanks!