GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 24

Question

Which of the following is/are correct? (Mark all the appropriate choices)

• A. A regular grammar is any right-linear or left-linear grammar.
• B. $A \rightarrow \alpha A \mid \beta$ is a right linear grammar, where $\alpha,\beta \in T^{\ast},$ where $T$ is the set of terminals
• C. $A \rightarrow A \alpha \mid \beta$ is a left linear grammar, where $\alpha,\beta \in T^{\ast},$ where $T$ is the set of terminals
• D. Any grammar which generates a regular language, is a regular grammar

Comments

option D is wrong .

counter example :-

S->ABC

A→ a

B→ b

C->c

the language generated by the grammar is { abc} which is regular but the grammar is not regular.

Answer 1

First three are the basic properties of regular grammar.

For every regular language there exists a regular grammar. But even a non-regular grammar can generate a regular language. So, option D is false.

So, the correct answer is $A;B;C;$

Comments

1. A regular grammar is any right-linear or left-linear grammar.

According to given statement if we take  one right linear grammar let say,

A → aaaaA | b;

Hear given above is right linear grammar but it is not the type 3 (regular) grammar as given in the Chomsky classification that type 3 grammar is any of the form

Non terminal → (Terminal) (Non Terminal)

or

Non Terminal → Terminal.

please clarify this confusion. @gatecse

---

@prnv28 But this can be converted to Regular Grammer

---

@hsahuja If we consider one CFG as given below,

A → BC

B → b

C → c

Now given below is a equivalent Regular grammar for given CFG,

A → bC

C → c

Here also we can convert CFG to Regular grammar but still given grammar is not regular.

So, Is it always valid to say that if we can convert any grammar to regular grammar than that given grammar if fall under Regular Grammar class?

---

@prnv28 The following is from the book ‘An Introduction to Formal Languages and Automata’ by Peter Linz (6^th edition, page no. – 92) :-

---

A grammar \(G = (V, T, S, P )\) is said to be right-linear if all productions are of the form

\[A → xB \ | \ x,\]

where \(A, B \in V\) , and \(x \in T^*\). A grammar is said to be left-linear if all productions are of the form

\[A → Bx \ | \ x.\]

A regular grammar is one that is either right-linear or left-linear.

[Note - I put in a '\(|\)' in the productions above because I was facing difficulty introducing line breaks while writing them in latex. Nevertheless, the definition is synonymous to that mentioned in the above provided resource.]

---

This book is a pretty standard resource that is followed by many universities, so I believe the above definition is accurate. Also, grammars given in option (B) and (C) are regular grammars, producing the languages \(L\big((\alpha)^*\beta\big)\) and \(L\big(\beta(\alpha)^*)\big)\), respectively.

P. S. - As per the above definition, even a production of the form \(A \rightarrow B\), where \(A, B \in V\), can be present in a regular grammar \(G = (V, T, S, P )\).