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

Improve this question
$\endgroup$
2
  • $\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
    Commented Jul 21, 2020 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
    Commented Jul 21, 2020 at 12:27

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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