- Thread starter
- #1

- Apr 14, 2013

- 4,601

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

- Thread starter mathmari
- Start date

- Thread starter
- #1

- Apr 14, 2013

- 4,601

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

- Admin
- #2

- Mar 5, 2012

- 9,417

Hey!!!

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

What is the definition of a regular grammar?

- Thread starter
- #3

- Apr 14, 2013

- 4,601

The rules of a regular grammar are of the form:Hey!!!

What is the definition of a regular grammar?

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

- Admin
- #4

- Mar 5, 2012

- 9,417

Yes.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 $ ?

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

Correct.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.

- Thread starter
- #5

- Apr 14, 2013

- 4,601

Great! Thanks!!!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 aregular grammaris a left regular grammarora right regular grammar.

Correct.

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

- Admin
- #6

- Mar 5, 2012

- 9,417

From wiki: a regular grammar is a formal grammar that describes a regular language.Great! Thanks!!!

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

More specifically, they are the same!

Or formally: the definitions are equivalent.

- Thread starter
- #7

- Apr 14, 2013

- 4,601

So only the language that is generated from the first grammar is 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.

- Admin
- #8

- Mar 5, 2012

- 9,417

Eh... not exactly.So only the language that is generated from the first grammar is regular?

The languages generated by those other grammars might have another grammar that is regular.

- Thread starter
- #9

- Apr 14, 2013

- 4,601

So do I have to find the languages that these grammars generate and then check if they are regular?Eh... not exactly.

The languages generated by those other grammars might have another grammar that is regular.

- Admin
- #10

- Mar 5, 2012

- 9,417

That would be a good way to go!So do I have to find the languages that these grammars generate and then check if they are regular?

- Thread starter
- #11

- Apr 14, 2013

- 4,601

Ok! Thanks!That would be a good way to go!