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
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
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP