# If a grammar G is left and right regular, why $||L(G)|| \leq ||P||$?

I was studying automata theory and formal languages and came across this question:

If a grammar $$G$$ is left and right regular, why $$||L(G)|| \leq ||P||$$ ?

I've searched the theory but I am missing something. And I cant find the answer anywhere, so I am asking here.

Definitions:

$$P$$ = set of rules

Right-regular rule: grammar $$G =(N,T,P,S)$$, a rule is in $$P$$ if the rule is in the form: $$A \rightarrow Ba$$ $$(A, B \in N) \wedge (a \in T)$$

Left-regular rule: grammar $$G =(N,T,P,S)$$, a rule is in $$P$$ if the rule is in the form: $$A \rightarrow aB$$ $$(A, B \in N) \wedge (a \in T)$$.

Left-regular grammar: a grammar where all the rules are left-regular rules.

Right-regular grammar: a grammar where all the rules are right-regular rules.

Example of a rule set $$P$$ with both left-regular and right-regular rules: $$P = \{ A \rightarrow a, B \rightarrow b \}$$

And being both left-regular and right-regular makes the grammar regular and type 3

• According to your definition, a context-free grammar which is both left-regular and right-regular cannot contain any rules. Indeed, rules such as $A \to a$ are not allowed under your definition. – Yuval Filmus Jul 21 '20 at 12:27
• Also, you still haven't defined $\|L(G)\|$ and $\|P\|$. I promise you that this is not standard notation. My guess is that you mean $|L(G)|$ (number of words in $L(G)$) and $|P|$ (number of productions in $P$). – Yuval Filmus Jul 21 '20 at 12:27

Your grammar only contains rules of the form $$A \to a$$, for $$A \in N$$ and $$a \in T$$. Therefore $$L(G) = \{ \sigma \in T : S \to \sigma \in P \}$$. You take it from here.