In the theory of formal grammars and automata (TFGiA), an important role is played by the so-called context-free grammars (CS-grammars). A KS-grammar is a quadruple consisting of a set N of non-terminal symbols, a set T of terminal symbols, a set P of rules (productions) and an initial symbol S belonging to the set N.↵
↵
↵
Each production p of P has the form A –> a, where A is a non-terminal symbol (A of N) and a is a string consisting of terminal and non-terminal symbols. The word output process begins with a line containing only the initial character S. After that, at each step, one of the non-terminal characters included in the current line is replaced by the right side of one of the productions in which it is the left side. If after such an operation a string containing only terminal characters is obtained, then the output process ends.↵
↵
↵
The CS grammar is given. We need to find the number of rules containing immediate left recursion.↵
↵
↵
Sample Input:↵
↵
3↵
↵
↵
S->Sabc↵
S->A↵
↵
S->A↵
↵
↵
A->AA↵
↵
Output:↵
↵
2↵
↵
↵
↵
Each production p of P has the form A –> a, where A is a non-terminal symbol (A of N) and a is a string consisting of terminal and non-terminal symbols. The word output process begins with a line containing only the initial character S. After that, at each step, one of the non-terminal characters included in the current line is replaced by the right side of one of the productions in which it is the left side. If after such an operation a string containing only terminal characters is obtained, then the output process ends.↵
↵
↵
The CS grammar is given. We need to find the number of rules containing immediate left recursion.↵
↵
↵
Sample Input:↵
↵
3↵
↵
↵
S->Sabc↵
↵
S->A↵
↵
↵
A->AA↵
↵
Output:↵
↵
2↵
↵
