3. Definition of Regular Grammar

·         Generates regular languages

·         Restrictions on production rules:

Types:

1.       Right-Linear Grammar

o    Productions:
A → a B
A → a

o    A, B = variables; a = terminal

2.     Left-Linear Grammar

o    Productions:
A → B a
A → a

o    A, B = variables; a = terminal

Key Rule:

·         Grammar must be entirely right-linear or entirely left-linear

·         Cannot mix both types

4. Examples of Regular Grammars

Example 1: Even number of ‘a’s (Right-Linear Grammar)

G = ({S, A}, {a, b}, P, S)

Production Rules:

·         S → b S

·         S → a A

·         S → ε

·         A → b A

·         A → a S

Generates strings with an even number of ‘a’s

Example 2: Strings start with ‘a’ and end with ‘b’ (Right-Linear Grammar)

G = ({S, A, B}, {a, b}, P, S)

Production Rules:

·         S → a A

·         A → a A

·         A → b A

·         A → b B

·         B → ε

Ensures string starts with ‘a’ and ends with ‘b’

5. Identifying Regular Grammars

Recap of Production Forms:

·         Right-Linear:
A → a B or A → a

·         Left-Linear:
A → B a or A → a

Requirement:

·         Grammar must be exclusively right-linear or left-linear

6. Examples for Identification

Right-Linear Grammar Example

G1 = ({S, A}, {a, b}, P1, S)

Productions:

·         S → a S

·         S → b A

·         A → a

·         A → b A

All productions follow right-linear form

Left-Linear Grammar Example

G2 = ({S, A}, {a, b}, P2, S)

Productions:

·         S → S a

·         S → A b

·         A → a

·         A → A b

All productions follow left-linear form

7. Examples of Non-Regular Grammars

Non-Regular Grammar Example

G3 = ({S}, {a, b}, P3, S)

Productions:

·         S → a S b

·         S → ε

Generates aⁿ bⁿ; Not right-linear or left-linear → Not Regular

Mixed Grammar (Non-Regular)

G4 = ({S, A, B}, {a, b}, P4, S)

Productions:

·         S → a A

·         A → B b

·         B → a

Mixes right-linear and left-linear rules → Not Regular

8. Converting Regular Grammars to Finite Automata

·         Regular grammars are equivalent to finite automata (FA)

·         Focus: Convert right-linear grammar to NFA

Conversion Algorithm (Right-Linear Grammar to NFA)

Given G = (V, T, P, S):

·         Q = V ∪ {qf} (qf is new final state)

·         Σ = T (set of terminals)

·         q0 = S (start symbol)

·         F = {qf} (final state)

Transition Function δ:

·         For A → a B → δ(A, a) = B

·         For A → a → δ(A, a) = qf

9. Example: Converting G1 to NFA

G1 = ({S, A}, {a, b}, P1, S)

Productions:

·         S → a S

·         S → b A

·         A → a

·         A → b A

Conversion Details:

·         Q = {S, A, qf}

·         Σ = {a, b}

·         q0 = S

·         F = {qf}

Transition Function δ:

·         δ(S, a) = S

·         δ(S, b) = A

·         δ(A, a) = qf

·         δ(A, b) = A

10. NFA Representation

State S:

·         On ‘a’ → S

·         On ‘b’ → A

State A:

·         On ‘a’ → qf

·         On ‘b’ → A

State qf:

·         Accepting state

11. Important MCQs on regular grammars that are helpful for your NET/SET exam preparation:

Question 1:
Which of the following statements is true regarding regular grammars?

(A) Every regular grammar is context-free
(B) Every context-free grammar is regular
(C) Regular grammars can generate languages that require unbounded memory
(D) Regular grammars can generate palindromes

Answer: (A)

Explanation:
Regular grammars are a subset of context-free grammars. This means every regular grammar is context-free, but not every context-free grammar is regular.

Question 2:
Which of the following production rules indicates that the grammar is NOT regular?

(A) A → a B
(B) A → B a
(C) A → a
(D) A → a S b

Answer: (D)

Explanation:
The production rule A → a S b is not allowed in regular grammars because it is neither strictly right-linear nor left-linear. Regular grammar rules must be of the form:

• A → a B or A → a (right-linear)
• A → B a or A → a (left-linear)

Question 3:
Consider the following grammar:

S → a A
A → b B
B → a

Which language does this grammar generate?

(A) Strings of the form aⁿ bⁿ, n ≥ 1
(B) The string "aba"
(C) The set of strings "a", "b", "a"
(D) The string "ab"

Answer: (B)

Explanation:
Starting with S:
S → a A → a b B → a b a

So, the only string generated is "aba".

Question 4:
Which of the following is equivalent to a regular grammar?

(A) Turing Machine
(B) Pushdown Automaton
(C) Finite Automaton
(D) Context-Free Grammar

Answer: (C)

Explanation:
Regular grammars and finite automata are equivalent in terms of the languages they generate and recognize. Regular grammars generate regular languages, which finite automata can recognize.

Question 5:
Which of the following grammars generates strings with an odd number of ‘a’s? (Assume the alphabet Σ = {a, b})

(A)
S → a A | b S
A → a S | b A | ε

(B)
S → a S | b A | ε
A → a A | b S

(C)
S → a A | b S
A → b A | a

(D)
S → a A | b S | a
A → a S | b A

Answer: (D)

Explanation:
In option (D), the grammar ensures that the strings generated have an odd number of ‘a’s. The transitions between states are designed to track the count of ‘a’s, and only strings with an odd number of ‘a’s are accepted.