Interesting Task

Revision en2, by ArvNor_, 2023-10-20 18:57:43

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

A->AA

Output:

2

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ArvNor_ 2023-10-20 18:57:43 12 Tiny change: 'ut:\n\n3\nS->Sabc\nS->A\nA->AA\n\' -> 'ut:\n\n3\n\n\nS->Sabc\n\n\nS->A\n\n\nA->AA\n\'
en1 English ArvNor_ 2023-10-20 18:57:16 1037 Initial revision (published)