How can I check if the grammar is regular?

  • Context: MHB 
  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Regular
Click For Summary

Discussion Overview

The discussion revolves around determining whether specific grammars are regular. Participants explore the definitions of regular grammars, analyze given examples, and consider how to check if the languages generated by these grammars are regular. The scope includes theoretical aspects of formal grammar and language generation.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested

Main Points Raised

  • Some participants inquire about the definition of a regular grammar, noting that rules typically take the form of $K \to \varnothing$ and $K \to aK'$.
  • There is a question about whether the rule $K \to aK$ is acceptable in the context of regular grammars.
  • One participant argues that $G_2$ is not a regular grammar due to the rule $I \to KL$, which does not conform to the expected forms.
  • Another participant agrees that $G_3$ is also not a regular grammar for similar reasons, citing the rule $I \to II$.
  • Participants discuss the equivalence of regular grammars and regular languages, suggesting that they are fundamentally the same.
  • There is uncertainty about whether the languages generated by the grammars that are not regular might still have regular grammars associated with them.
  • One participant proposes that finding the languages generated by the grammars and checking their regularity would be a reasonable approach.

Areas of Agreement / Disagreement

Participants generally agree on the definitions and characteristics of regular grammars, but there is no consensus on the regularity of the languages generated by the grammars in question. Multiple competing views remain regarding the implications of the definitions and the relationship between grammars and the languages they generate.

Contextual Notes

Participants express uncertainty about the implications of the definitions of regular grammars and the regularity of the languages generated by the grammars discussed. There are unresolved questions about the specific languages produced by the grammars and their potential regularity.

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
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$$
 
Technology news on Phys.org
mathmari said:
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! :o

What is the definition of a regular grammar?
 
I like Serena said:
Hey! :o

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.
 
mathmari said:
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. ;)
 
I like Serena said:
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! :o

And how can I check if the languages that these grammars generate are regular?
 
mathmari said:
Great! Thanks! :o

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.
 
I like Serena said:
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?
 
mathmari said:
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.
 
I like Serena said:
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?
 
  • #10
mathmari said:
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)
 
  • #11
I like Serena said:
That would be a good way to go! (Angel)

Ok! Thanks! :o
 

Similar threads

MHB Regular Expressions Help: Find Language for DFA Drawing
  • · Replies 13 ·
Replies
13
Views
4K
MHB How to find a language generated by a given grammar
  • · Replies 8 ·
Replies
8
Views
3K
MHB What Do $\phi$ and $\phi'$ Mean in Regular Grammars?
  • · Replies 24 ·
Replies
24
Views
4K
MHB How can I show that the sets are pairwise disjoint?
  • · Replies 12 ·
Replies
12
Views
2K
MHB Is the Subgraph Isomorphism problem NP-complete?
  • · Replies 1 ·
Replies
1
Views
3K
MHB How can I continue to find a regular expression?
  • · Replies 8 ·
Replies
8
Views
2K
Show isomorphism under specific conditions
  • · Replies 13 ·
Replies
13
Views
2K
MHB Regular and Context-free languages
  • · Replies 2 ·
Replies
2
Views
2K
MHB Context-Free Langs: S-L Check if Not CF?
  • · Replies 15 ·
Replies
15
Views
4K
Importance/Use of Gauss' Law and Ampere's Circuital Law
  • · Replies 30 ·
2
Replies
30
Views
2K