If a grammar G is left and right regular, why $||L(G)|| \leq ||P||$?
-
29-09-2020 - |
Question
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
Solution
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.