Question about CNF

Question about CNF

by MANUEL LOVO -
Number of replies: 1

a) Considering a grammar of this type:

S --> ABA | ABB | BB
A --> aB | BB
B --> bB

a.1) Can I define a single variable C --> a and substitute it in both productions, or do I need to define two variables C --> a and D --> a for the two different productions?
If I already have a variable C --> a in the grammar, can I use that?
a.2) In the breakdown of the production S --> ABA, I create a variable K --> AB. Can I use K in the production S --> ABB, making it S --> KB, or do I need to use another variable, for example, L --> BB?


                        

    
    
    
                            
    
    
                                

                                        
                                

    
                            
                    

                

            

        

    
        

                

                    

                        
                
                        

                            

                                        

                                                
                                        

                                

                                        In reply to MANUEL LOVO
                                        
Re: Question about CNF

                                        

                                            by Giorgio Satta - 
                        

                                

                            

                
                            

                                        

                                        

                
                                

                                    

                                        
My answer is yes to all of your questions.  The sharing of a variable keeps the grammar small and is therefore more efficient.



Keep in mind that the construction in the textbook does not use sharing, sharing is an optimization technique.