TransWikia.com

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

Computer Science Asked on November 5, 2021

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

One Answer

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.

Answered by Yuval Filmus on November 5, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP