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

Was it helpful?

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top