REGULAR GRAMMARS

Question

if a is a terminal and S, A, B are three non-terminals, then which of the following are regular grammars?
(a) S → ε, A → aS|b
(b) A → aB|a, B → bA|b
(c) A → Ba|Bab
(d) A → abB|aB
please explain how u proceed?
The answer is given "b"

Answer 1

A grammar is either left linear (any non-terminal in production comes at the left end) or right linear (any non-terminal in production comes at the right end) is regular.

$S\to Sa \mid a$ is left-linear so it is regular grammar.

$S\to aS \mid  a$ is right-linear, so it is regular grammar.

$S\to SaS \mid a$ is neither left linear nor right linear and hence it is not regular grammar.

Now check all options who satisfy the definition of regular grammar. Here both option (A)and (B)are satisfying the definition of regular grammar.

Comments

but in type-3 V-> T*V/T*(RLG),  V-> VT*/T*(LLG).

now all follow this.

---

But,

It is not T*, it shoud be single terminal or a single terminal followed by a single vertex for (RLG) and accordingly for (LLG).

And according to Chomsky, it allowes S--->€(epsilon) only if S doesn't appear on right side of any rule.

So A got rejected. But still 1st generate epsilon as only string and we can have FA for that, so it should be regular.

Still confused!!

---

but regular grammar definition says grammar should be either left-linear or right-linear.and it is satisfying the condition.So (A) is also regular grammar.

Answer 2

Reason behind not counting A option as regular, as far as I think is that if you consider s start symbol, nothing can be generated from it. Am I correct...

Comments

s->ε will create ε and that fall under the regular language