0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 21 '20 at 12:27
  • $\begingroup$ 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$). $\endgroup$ – Yuval Filmus Jul 21 '20 at 12:27
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.