beecrowd | 1826

Is The Language Infinite?

By Matheus Pimenta, UNB BR Brazil

Timelimit: 2

Context-free grammar – CFG – is a mathematical structure used to generate strings, which are finite sequences of terminal symbols. The set of all strings that can be generated by CFG G is the language of G, written L(G). In this problem, given a CFG G, you must tell if L(G) is an empty set, finite, or infinite.

A CFG is a 4-tuple (V, Σ, R, S), where

  1. V is a finite and non-empty set whose elements are called variables.
  2. Σ is a finite and non-empty set, disjoint of V, whose elements are called terminal symbols.
  3. R is a set of rules. A rule has the form

    A → U1U2...Uk

    where A ∈ V, k ≥ 0 and Ui ∈ V ∪ Σ for i = 1,2,...,k.
  4. S ∈ V is the start variable.

To generate a string using a CFG, we run the following procedure.

First, write the start variable S. Next, choose a rule to substitute S, say, S → U1U2...Uk. After this choice, erase the S and write in its place the string of variables and/or terminals U1U2...Uk. Repeat this process until no variable is left written. If it's not possible to generate a string without variables starting with the start variable, we say that the CFG's language is empty.

For example, let be the CFG below, where S is the start variable.

S → aSa

S → bSb

S → a

S → b

S →

Using the CFG above, we can generate any palindrome made of a's and b's. For example:

S → aSaabSbaabba

Observe that the empty string is a valid string. So, if a CFG G generates, for example, only the empty string, L(G) is finite, but not empty.

In this problem, the variables will be words made only of uppercase letters, that is, characters between A and Z. The terminal symbols will be lowercase letters, that is, characters between a and z. The rules will be in the format described in the next section. The start variable will always be the first variable of the test case.


The input contains many test cases. Each test case describes a context-free grammar.

The first line of a test case contains two integers v and r, where v is the amount of variables of the CFG, r is the amount of rules, 1 ≤ v ≤ 102 and 0 ≤ r ≤ 2·102.

Each one of the next v lines contains a word made of uppercase letters, a variable of the CFG. The variable in the first line is the start variable.

Each one of the next r lines describes a rule of the CFG. A word of uppercase letters is given, an integer 0 ≤ k ≤ 102 and a sequence of k elements, where each element is a variable, or a terminal symbol.


For each test case, print a line with the word "vazia" if the CFG generates no strings of terminals, or the word "finita" if the CFG generates some, but not infinite strings of terminals, or the word "infinita" if the CFG generates infinite strings of terminals.

Input Sample Output Sample

1 0
1 1
S 1 S
1 1
S 0
1 3
S 0
S 2 a a
S 1 b
2 3
S 2 S A
S 1 b
A 0
1 5
S 3 a S a
S 3 b S b
S 1 a
S 1 b
S 0